Cost preserving dependent rounding for allocation problems

DOI10.4230/LIPICS.ICALP.2025.127MaRDI QIDQ7397584zbMATH OpenFDO

Authors Lars Rohwedder, Arman Rouhani, Leo Wennmann

Publication date 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2025.127

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A new approximation technique for resource-allocation problems
• A Tale of Santa Claus, Hypergraphs and Matroids
• An \(O(\log n/\log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• An approximation algorithm for the generalized assignment problem
• Approximation Schemes for Multi-Budgeted Independence Systems
• Approximation-friendly discrepancy rounding
• Closing the gap for makespan scheduling via sparsification techniques
• Combinatorial algorithm for restricted max-min fair allocation
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Constructive discrepancy minimization by walking on the edges
• Dependent randomized rounding via exchange properties of combinatorial structures
• Dependent rounding and its applications to approximation algorithms
• scientific article; zbMATH DE number 5764883 (Why is no real title available?)
• Multi-budgeted matchings and matroid intersection via dependent rounding
• Santa Claus Meets Hypergraph Matchings
• Santa claus meets makespan and matroids: algorithms and reductions
• The Santa Claus problem

This page was built for publication: Cost preserving dependent rounding for allocation problems

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