Extended formulations for vertex cover
type: Item
instance of: scholarly article
title: Extended formulations for vertex cover
zbMATH Open document ID: 1408.90248
author: Austin Buchanan
published in: Operations Research Letters
publication date: 2018-10-02T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C57
zbMATH DE Number: 6946096
zbMATH Keywords: fixed-parameter tractable
zbMATH Keywords: extended formulation
zbMATH Keywords: vertex cover
zbMATH Keywords: independent set
zbMATH Keywords: cardinality constrained
zbMATH Keywords: hitting set
MaRDI profile type: Publication
full work available at URL: j.orl.2016.03.008
OpenAlex ID: W2311829919
cites work: Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
cites work: Disjunctive programming: Properties of the convex hull of feasible points
cites work: Compositions of Graphs and Polyhedra II: Stable Sets
cites work: LP Formulations for Polynomial Optimization Problems
cites work: Polytope des independants d'un graphe série-parallèle
cites work: Average Case Polyhedral Complexity of the Maximum Stable Set Problem
cites work: The matching polytope does not admit fully-polynomial size relaxation schemes
cites work: An information complexity approach to extended formulations
cites work: Nondeterminism within $P^ * $
cites work: Parameterized top-\(K\) algorithms
cites work: Improved upper bounds for vertex cover
cites work: Extended formulations in combinatorial optimization
cites work: Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
cites work: Exponential lower bounds for polytopes in combinatorial optimization
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Symmetry Matters for Sizes of Extended Formulations
cites work: Extended formulation for CSP that is compact for instances of bounded treewidth
cites work: Extension Complexity, MSO Logic, and Treewidth
cites work: Q3601990
cites work: Polyhedral Characterization of Discrete Dynamic Programming
cites work: Properties of vertex packing and independence system polyhedra
cites work: Vertex packings: Structural properties and algorithms
cites work: On the facial structure of set packing polyhedra
cites work: A note on the extension complexity of the knapsack polytope
cites work: The Matching Polytope has Exponential Extension Complexity
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: A class of facet producing graphs for vertex packing polyhedra
cites work: On a cardinality-constrained transportation problem with market choice
cites work: Expressing combinatorial optimization problems by linear programs
cites work: Linear degree extractors and the inapproximability of max clique and chromatic number
DOI: 10.1016/J.ORL.2016.03.008
description: scientific article; zbMATH DE number 6946096