Lift-and-project methods for set cover and knapsack
type: Item
instance of: scholarly article
title: Lift-and-project methods for set cover and knapsack
zbMATH Open document ID: 1406.90104
author: Eden Chlamtac
author: Zachary Friggstad
author: Konstantinos Georgiou
published in: Algorithmica
publication date: 2018-10-18T00:00:00Z
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 6958255
zbMATH Keywords: set cover
zbMATH Keywords: sub-exponential algorithms
zbMATH Keywords: approximation algorithms
zbMATH Keywords: lift-and-project methods
zbMATH Keywords: knapsack
MaRDI profile type: Publication
full work available at URL: s00453-018-0427-4
OpenAlex ID: W2794994194
cites work: Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
cites work: A comprehensive analysis of polyhedral lift-and-project methods
cites work: Rounding Semidefinite Programming Hierarchies via Global Correlation
cites work: Hypercontractivity, sum-of-squares proofs, and their applications
cites work: A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
cites work: Lift-and-Project Methods for Set Cover and Knapsack
cites work: Convex Relaxations and Integrality Gaps
cites work: A Greedy Heuristic for the Set-Covering Problem
cites work: Exponential-time approximation of weighted set cover
cites work: Analytical approach to parallel repetition
cites work: A threshold of ln n for approximating set cover
cites work: Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
cites work: Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
cites work: Approximation algorithms for combinatorial problems
cites work: Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
cites work: Reducibility among Combinatorial Problems
cites work: An explicit equivalent positive semidefinite program for nonlinear 0-1 programs
cites work: A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
cites work: On the ratio of optimal integral and fractional covers
cites work: Cones of Matrices and Set-Functions and 0–1 Optimization
cites work: Approximability and proof complexity
cites work: Q3549708
cites work: Q5743406
cites work: A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
DOI: 10.1007/S00453-018-0427-4
Recommended article: Lift-and-Project Methods for Set Cover and Knapsack
Recommended article: Lifting for the integer knapsack cover polyhedron
Recommended article: Simple lifted cover inequalities and hard knapsack problems
Recommended article: Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes
Recommended article: Lifting the knapsack cover inequalities for the knapsack polytope
Recommended article: Lifting cover inequalities for the precedence-constrained knapsack problem
Recommended article: On the complexity of sequentially lifting cover inequalities for the knapsack polytope
Recommended article: Q4735936
Recommended article: Exact methods for the knapsack problem and its generalizations
Recommended article: Q4735035
description: scientific article; zbMATH DE number 6958255