Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle
From MaRDI portal
Publication:3503853
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
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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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