Extended formulations for vertex cover
From MaRDI portal
Publication:1790198
DOI10.1016/j.orl.2016.03.008zbMath1408.90248OpenAlexW2311829919MaRDI QIDQ1790198
Publication date: 2 October 2018
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.orl.2016.03.008
independent setvertex coverfixed-parameter tractableextended formulationcardinality constrainedhitting set
Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Related Items
Parameterized extension complexity of independent set and related problems, Fixed cardinality stable sets, Worst-case analysis of clique MIPs
Cites Work
- Unnamed Item
- Improved upper bounds for vertex cover
- Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
- Extended formulation for CSP that is compact for instances of bounded treewidth
- Polytope des independants d'un graphe série-parallèle
- Expressing combinatorial optimization problems by linear programs
- A class of facet producing graphs for vertex packing polyhedra
- Disjunctive programming: Properties of the convex hull of feasible points
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- On a cardinality-constrained transportation problem with market choice
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Parameterized top-\(K\) algorithms
- A note on the extension complexity of the knapsack polytope
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Average Case Polyhedral Complexity of the Maximum Stable Set Problem
- Polyhedral Characterization of Discrete Dynamic Programming
- Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
- Vertex packings: Structural properties and algorithms
- Nondeterminism within $P^ * $
- Compositions of Graphs and Polyhedra II: Stable Sets
- LP Formulations for Polynomial Optimization Problems
- The Matching Polytope has Exponential Extension Complexity
- Properties of vertex packing and independence system polyhedra
- Symmetry Matters for Sizes of Extended Formulations
- On the facial structure of set packing polyhedra
- The matching polytope does not admit fully-polynomial size relaxation schemes
- Extension Complexity, MSO Logic, and Treewidth
- An information complexity approach to extended formulations
- Extended formulations in combinatorial optimization
