On linear and semidefinite programming relaxations for hypergraph matching
From MaRDI portal
Publication:715088
DOI10.1007/s10107-011-0451-5zbMath1254.90107OpenAlexW3136714316MaRDI QIDQ715088
Publication date: 15 October 2012
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-011-0451-5
Semidefinite programming (90C22) Linear programming (90C05) Hypergraphs (05C65) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (16)
Online crowdsourced truck delivery using historical information ⋮ Generalized Hypergraph Matching via Iterated Packing and Local Ratio ⋮ Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs ⋮ Unnamed Item ⋮ Integrality gaps for colorful matchings ⋮ Some remarks on hypergraph matching and the Füredi–Kahn–Seymour conjecture ⋮ On the parameterized complexity of compact set packing ⋮ Technical Note—Online Hypergraph Matching with Delays ⋮ Coverage, Matching, and Beyond: New Results on Budgeted Mechanism Design ⋮ Greedy matching: guarantees and limitations ⋮ An axiomatic duality framework for the theta body and related convex corners ⋮ An Approximation Result for Matchings in Partitioned Hypergraphs ⋮ Approximate multi-matroid intersection via iterative refinement ⋮ Three algorithms for graph locally harmonious colouring ⋮ ThIEF: Finding Genome-wide Trajectories of Epigenetics Marks ⋮ Distributed algorithms for matching in hypergraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- On the fractional matching polytope of a hypergraph
- Ryser's conjecture for tripartite 3-graphs
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- Critical hypergraphs and interesting set-pair systems
- The ellipsoid method and its consequences in combinatorial optimization
- Maximum degree and fractional matchings in uniform hypergraphs
- Geometric algorithms and combinatorial optimization
- The sandwich theorem
- Approximating the independence number via the \(\vartheta\)-function
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- On two intersecting set systems and k-continuous Boolean functions
- Tree-width and the Sherali-Adams operator
- An approximation algorithm for maximum triangle packing
- On the complexity of approximating \(k\)-set packing
- On Local Search for Weighted k-Set Packing
- The Santa Claus problem
- Local Global Tradeoffs in Metric Embeddings
- On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
- Santa Claus Meets Hypergraph Matchings
- On Completing Latin Squares
- Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy
- Cones of Matrices and Set-Functions and 0–1 Optimization
- On the Shannon capacity of a graph
- Randomized graph products, chromatic numbers, and Lovasz j-function
- Hall's theorem for hypergraphs
- The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
- Integrality gaps for Sherali-Adams relaxations
- Sherali-adams relaxations of the matching polytope
- CSP gaps and reductions in the lasserre hierarchy
- Non-approximability results for optimization problems on bounded degree instances
- On the facial structure of set packing polyhedra
- Scheduling Split Intervals
- The Lovász Number of Random Graphs
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
- Approximation algorithms and hardness results for the clique packing problem
This page was built for publication: On linear and semidefinite programming relaxations for hypergraph matching
