Generalized Packing Integer Programs with Rigid and Elastic Capacity and Their Applications

具有剛性和彈性容量的廣義包裝整數規劃以及它們的實際應用

Student thesis: Doctoral Thesis

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Awarding Institution
Supervisors/Advisors
Award date25 Oct 2017

Abstract

Packing Integer Programs (PIPs) are a well-known class of problems that includes many classic NP-hard problems (such as Maximum Independent Set and Maximum Set Packing) in computer science. The general goal of PIPs is to pack as many objects as possible under certain capacity constraints. Normally, the capacities are rigid, i.e., fixed. Motivated by certain applications, we introduce a new variant of PIPs where the capacities are elastic. In the sense that the capacities are increasing functions of the chosen objects. Both the rigid and elastic cases have applications ranging from data mining to social networks; thus, their efficient solutions contribute fundamentally to tackling useful real-world problems.

We first study PIPs with rigid and elastic capacity, which is important to the application of robust frequent itemset mining. It is well-known that frequent itemset mining is one of the core problems in the area of data mining. Robust frequent itemset mining is an important variant, which has attracted much attention due to the necessity to find frequent patterns from noisy data. We focus on a variant of robust frequent itemsets in which a small amount of "faults" is allowed in each item and each supporting transaction. We develop heuristic methods to solve an approximate version of the problem and propose speedup techniques for the exact problem. Experimental results show that our heuristic algorithms are substantially faster than the state-of-the-art exact algorithms while the error is acceptable. In addition, the proposed speedup techniques improve the efficiency of the exact algorithms.

We also study a class of generalized PIPs, which we call PIPs with implicit objects, where the objects are implicitly defined and the total number of objects can be exponential with respect to the input size. This problem has interesting applications in team formation in social networks, i.e., forming multiple teams of experts with diverse skills in social network to accomplish complex tasks of required skills. We focus on the problem of maximizing the total profit of tasks that these teams can complete subject to experts’ capacities. We provide simple and practical algorithms that improve upon previous theoretical results in many situations.