The Demand-Matching Problem

DOI10.1287/MOOR.1070.0254MaRDI QIDQ5388047zbMATH OpenOpenAlexFDO

Authors F. Bruce Shepherd, Adrian Vetta

Publication date 27 May 2008

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.1070.0254

zbMATH Keywords

\(b\)-matchingapproximation algorithmintegrality gaplinear programming

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Linear programming (90C05) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59) Matching models (91B68)

Recommendations

• scientific article; zbMATH DE number 2086940
• Further approximations for demand matching: matroid constraints and minor-closed graphs
• scientific article; zbMATH DE number 2038727
• Perfect matching in bipartite hypergraphs subject to a demand graph
• Iterative packing for demand and hypergraph matching

Cited in

(11)

• Stochastic packing integer programs with few queries
• Iterative packing for demand and hypergraph matching
• Generalized hypergraph matching via iterated packing and local ratio
• Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
• A deterministic PTAS for the commutative rank of matrix spaces
• scientific article; zbMATH DE number 2086940 (Why is no real title available?)
• Symmetric interdiction for matching problems
• Further approximations for demand matching: matroid constraints and minor-closed graphs
• Multicommodity flow in trees: packing via covering and iterated relaxation
• Approximability of sparse integer programs
• The maximin line problem with regional demand

This page was built for publication: The Demand-Matching Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5388047)