Lift-and-Project Methods for Set Cover and Knapsack

DOI10.1007/978-3-642-40104-6_23zbMath1391.68123OpenAlexW119341521MaRDI QIDQ2842162

Konstantinos Georgiou, Zachary Friggstad, Eden Chlamtáč

Publication date: 12 August 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-40104-6_23

zbMATH Keywords

approximation algorithmsknapsackset coverlift-and-project methodssub-exponential algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (6)

Fair Colorful k-Center Clustering ⋮ Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines ⋮ Integrality gaps for colorful matchings ⋮ Lift-and-project methods for set cover and knapsack ⋮ Semidefinite and linear programming integrality gaps for scheduling identical machines ⋮ Fair colorful \(k\)-center clustering

This page was built for publication: Lift-and-Project Methods for Set Cover and Knapsack