Combinatorial and algebraic algorithms in set covering and partitioning problems.

摘要

In this dissertation, we focus on using combinatorial and algebraic methods on two classes of NP-hard problems, the set covering problem and the set partitioning problem. The inputs to both problems are a universe of elements U, and a collection S of subsets of U. NP-hard problems are generally believed not to be solvable exactly in polynomial time. One direction to study NP-hard problems is to find polynomial-time approximation algorithms which aim at improving the approximation guarantee.;We study approximation algorithms based on local improvements for the k-Set Packing problem. The k-Set Packing problem asks to find a disjoint collection of sets with size k which have the maximum coverage. We present a local search algorithm which looks for a class of local improvements of O(log n) sets (n = |S|), which we call the canonical improvements with tail changes. The algorithm achieves an approximation ratio 3/k+1 - epsilon in time singly exponential to 1/epsilon2. On the other hand, we construct an instance with locality gap 3/k+1 for any algorithm using local improvements of size O(n1/5). Thus, our approximation guarantee is optimal with respect to results achievable by algorithms based on local improvements.;The k-Set Cover problem asks to find a collection of minimum number of sets which cover the entire universe, where the sets have size at most k. The standard greedy algorithm for the k-Set Cover problem selects i-sets greedily for i from k down to 1. We replace the greedy selection by a set packing algorithm based on local search. Our key contribution is a new k-Set packing heuristic which we call a restricted k-Set Packing algorithm. The algorithm makes a local improvement only when the number of 1-sets needed to complete the cover does not increase. Equipped with the restricted k-Set Packing algorithm, our k-Set Cover algorithm achieves an approximation ratio H k - 0.6690 + epsilon + O(1/k ), where Hk = Sigma k i=1 1/i is the k-th harmonic number. For small k, our results are 1.8583 for k = 6, 1.7143 for k = 5 and 1.5 for k = 4, which are the currently best approximation guarantee for the k-Set Cover problem for any k ≥ 4.;Although these local search algorithms achieve good approximation guarantee, they are usually not applicable for real-world problems especially when we have large-scale data. To obtain an efficient approximate solution to some set covering problems, we propose a one-pass streaming algorithm which produces a prefixoptimal ordering of sets. This algorithm can be easily used to solve the Max-k-Cover and the Partial-Cover problems. The algorithm consumes space linear to the size of the universe of elements. The processing time for a set is linear to the size of the set. We also show with the aid of computer simulation that the approximation ratio of the Max-k-Cover problem is around 0.3. We conduct experiments to compare our algorithm with existing algorithms.;Another direction of studying NP-hard problems is to find efficient exponentialtime algorithms to exactly solve the problem. Dynamic programming is one generic way for this purpose. However, it could have the drawback of requiring exponential space. We consider exact computations based on tree decomposition of graphs using dynamic programming. In this case, the space complexity is usually exponential in the treewidth. We study the problem of designing efficient dynamic programming algorithms based on tree decompositions in polynomial space. We show how to construct a tree decomposition and use algebraic techniques to obtain a dynamic programming algorithm which runs in time O*(2 h), where h is a parameter closely related to the tree-depth of a graph. We apply our algorithm to the problem of counting perfect matchings on grids and show that it outperforms other polynomial-space solutions. We also apply the algorithm to other set covering and partitioning problems.;Finally, we consider one important application of the Set Cover problem, diversifying the subgraph search result. The subgraph search results are typically ordered based on graph similarity score. We design two ranking measures with the "diminishing return" property based on both similarity and diversity. We give two efficient algorithms, the greedy selection and the swapping selection with provable performance guarantee. We also propose a local search heuristic with at least 100 times speedup and a similar solution quality. We demonstrate the efficiency and effectiveness of our approaches via extensive experiments.