Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle

DOI10.1007/978-3-540-68891-4_19zbMath1143.90373OpenAlexW2097509673MaRDI QIDQ3503853

André Berger, Fabrizio Grandoni, Vincenzo Bonifaci, Guido Schäfer

Publication date: 10 June 2008

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://ir.cwi.nl/pub/14736

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

Partial degree bounded edge packing problem for graphs and \(k\)-uniform hypergraphs, Almost exact matchings, A theory and algorithms for combinatorial reoptimization, Interdicting Structured Combinatorial Optimization Problems with {0, 1}-Objectives, Bi-criteria and approximation algorithms for restricted matchings, On Lagrangian Relaxation and Subset Selection Problems, Approximation algorithms for maximum latency and partial cycle cover, Probabilistic analysis of algorithms for cost constrained minimum weighted combinatorial objects

Cites Work

• Real-time scheduling with a budget
• Matching is as easy as matrix inversion
• Generalized polymatroids and submodular flows
• A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• An application of lagrangean decomposition to the resource-constrained minimum weighted arborescence problem
• An algorithm for the resource constrained shortest path problem
• Combinatorial Optimization with Rational Objective Functions
• The complexity of restricted spanning tree problems
• Random pseudo-polynomial algorithms for exact matroid problems
• Bicriteria Network Design Problems
• An Efficient Polynomial Time Approximation Scheme for the Constrained Minimum Spanning Tree Problem Using Matroid Intersection
• The constrained minimum spanning tree problem
• On matroid intersection adjacency
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item