2018/01/26 by Yuri Faenza, Igor Malinović, Faenza, Yuri +5
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems #cs.DS
paper · pdf · doi:10.48550/arxiv.1801.08850
14 pages
arxiv created 2018/01/26 · openalex publication_date 2018/01/26 · arxiv updated 2018/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the min-knapsack problem one aims at choosing a set of objects with minimum total cost and total profit above a given threshold. In this paper, we study a class of valid inequalities for min-knapsack known as bounded pitch inequalities, which generalize the well-known unweighted cover inequalities. While separating over pitch-1 inequalities is NP-hard, we show that approximate separation over the set of pitch-1 and pitch-2 inequalities can be done in polynomial time. We also investigate integrality gaps of linear relaxations for min-knapsack when these inequalities are added. Among other results, we show that, for any fixed t, the t-th CG closure of the natural linear relaxation has the unbounded integrality gap.