Budgeted matching and budgeted matroid intersection via the gasoline puzzle
DOI10.1007/S10107-009-0307-4zbMATH Open1223.05222OpenAlexW2104399828MaRDI QIDQ543415FDOQ543415
Authors: André Berger, Vincenzo Bonifaci, Fabrizio Grandoni, Guido Schäfer 
Publication date: 17 June 2011
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://ir.cwi.nl/pub/14736
Recommendations
Combinatorial optimization (90C27) Discrete mathematics in relation to computer science (68R99) Combinatorial aspects of matroids and geometric lattices (05B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.
- On certain polytopes associated with graphs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Combinatorial Optimization with Rational Objective Functions
- A Note on Approximation Schemes for Multidimensional Knapsack Problems
- Matching is as easy as matrix inversion
- Generalized polymatroids and submodular flows
- Title not available (Why is that?)
- An Effective Heuristic Algorithm for the Traveling-Salesman Problem
- The complexity of restricted spanning tree problems
- Real-time scheduling with a budget
- The dependence graph for bases in matroids
- Title not available (Why is that?)
- A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
- An algorithm for the resource constrained shortest path problem
- Approximating minimum bounded degree spanning trees to within one of optimal
- Approximating the Minimum-Degree Steiner Tree to within One of Optimal
- Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs
- A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
- Many birds with one stone
- Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
- Exact arborescences, matchings and cycles
- Random pseudo-polynomial algorithms for exact matroid problems
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- An application of lagrangean decomposition to the resource-constrained minimum weighted arborescence problem
- On matroid intersection adjacency
Cited In (26)
- An FPTAS for budgeted laminar matroid independent set
- Polynomial-time approximation schemes for a class of integrated network design and scheduling problems with parallel identical machines
- New approaches to multi-objective optimization
- Socially fair matching: exact and approximation algorithms
- Generalized center problems with outliers
- A constant approximation for colorful \(k\)-center
- The alternating stock size problem and the gasoline puzzle
- Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle
- Budgeted colored matching problems
- Multi-budgeted matching problems
- Discrete representation of the non-dominated set for multi-objective optimization problems using kernels
- Multi-criteria TSP: Min and Max combined
- On the complexity and approximation of the maximum expected value all-or-nothing subset
- Approximate tradeoffs on weighted labeled matroids
- On a cardinality-constrained transportation problem with market choice
- Bulk-robust combinatorial optimization
- Approximation Methods for Multiobjective Optimization Problems: A Survey
- Bi-criteria and approximation algorithms for restricted matchings
- On Lagrangian relaxation for constrained maximization and reoptimization problems
- Generalized center problems with outliers
- Polynomial-time approximation schemes for maximizing gross substitutes utility under budget constraints
- Tight bounds for budgeted maximum weight independent set in bipartite and perfect graphs
- Proportionally Fair Matching with Multiple Groups
- Obtaining approximately optimal and diverse solutions via dispersion
- On Budgeted Optimization Problems
- Bi-objective matchings with the triangle inequality
This page was built for publication: Budgeted matching and budgeted matroid intersection via the gasoline puzzle
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q543415)
