Approximation Algorithms for Precedence-Constrained Knapsack and Capacitated Covering Integer Programs

Submitted by admin on Sat, 13/03/2021 - 12:53
Antonios Sakrlatos
Date of Defense
Three-member Committee
Archontia C. Giannopoulou
Stavros Kolliopoulos (Advisor)
Dimitris Fotakis

Precedence-constrained knapsack is a generalization of the classical Minimum Knapsack problem in which the items chosen for inclusion in the knapsack must form a prefix (ideal) of a given partial order. We study primal-dual algorithms from the literature and among other results we settle the question of the existence of an approximation algorithm with strongly polynomial bounds for the case where item i can be chosen at most d_i times (as opposed to at most once).

Capacitated covering integer programs generalize Minimum Knapsack in the sense that the items chosen must satisfy simultaneously m covering constraints. For this problem we improve the efficiency of a known approximatio algorithms.

All our positive and negative results rely on linear programming relaxations for the problems.