Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy

DOI10.1007/978-3-642-03685-9_20zbMath1255.68306OpenAlexW1870858037MaRDI QIDQ3638882

Mohammad Moharrami, Avner Magen

Publication date: 28 October 2009

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03685-9_20

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (15)

On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy ⋮ Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials ⋮ Max-Cut Under Graph Constraints ⋮ A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time ⋮ Integrality gaps for colorful matchings ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On linear and semidefinite programming relaxations for hypergraph matching ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Convex Relaxations and Integrality Gaps ⋮ Approximating graph-constrained max-cut

This page was built for publication: Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy