Lift-and-project methods for set cover and knapsack
From MaRDI portal
Publication:1799231
DOI10.1007/s00453-018-0427-4zbMath1406.90104OpenAlexW2794994194MaRDI QIDQ1799231
Eden Chlamtáč, Konstantinos Georgiou, Zachary Friggstad
Publication date: 18 October 2018
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-018-0427-4
Cites Work
- Unnamed Item
- Unnamed Item
- Exponential-time approximation of weighted set cover
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
- A Comprehensive Analysis of Polyhedral Lift-and-Project Methods
- Convex Relaxations and Integrality Gaps
- Lift-and-Project Methods for Set Cover and Knapsack
- Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
- A threshold of ln n for approximating set cover
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
- A Greedy Heuristic for the Set-Covering Problem
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Reducibility among Combinatorial Problems
- Analytical approach to parallel repetition
- Hypercontractivity, sum-of-squares proofs, and their applications
- A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
- Rounding Semidefinite Programming Hierarchies via Global Correlation
- Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- Approximability and proof complexity
