K-中位问题（k-median problem）是最经典的组合优化问题之一，在设施选址、网络设计、聚类分析等实际问题中都有重要的应用价值。背包中位问题（knapsack median problem）是k-中位问题的一个重要变形，其将基数约束换成背包约束，具有更宽广的应用范围。在气象卫星遥感、股票市场分析、网络通信量监测等领域中，数据往往是海量且高速动态，我们称这样的数据形态为数据流。对于数据流模型，我们需要按顺序即时地处理数据，并且只能使用比整个流小很多的存储空间，这样的算法被称为流算法。虽然关于流算法的研究已有近20年的历史，但是对于背包中位问题，流算法尚不存在，有待我们的研究。本项目拟针对背包中位问题及其变形，研究数据流模型下的近似算法或高效的启发式算法。项目的研究对于促进组合优化领域的理论发展和实际应用都有重要的意义。

K-median problem is one of the most classical combinatorial optimization problems, which has important application value in facility location, network design, clustering analysis and other practical problems. Knapsack median problem, an important variant of k-median problem, replaces the cardinality constraint with the knapsack constraint, so that it is useful for more cases. In many fields such as meteorological satellite remote sensing, stock market analysis, and network traffic monitoring, the data is massive and generated at rapid rate. Such type of data is called data stream. For the data stream model, we need to develop so-called streaming algorithms which process the data in order and real-time, and have to use limited memory that is much smaller than the whole streams. Although the streaming algorithm is studied for nearly 20 years, but it does not exist for the knapsack median problem, so it needs our research. This project investigates into approximation algorithms or efficient heuristic algorithms under the data streaming model for the knapsack median problem and its variants. The research of the project has great significance for both theoretical development and practical application of combinatorial optimization.