Faster min-max resource sharing in theory and practice

DOI10.1007/s12532-011-0023-yzbMath1242.90200OpenAlexW2151822553MaRDI QIDQ542051

Dirk Müller, Klaus Radke, Jens Vygen

Publication date: 8 June 2011

Published in: Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12532-011-0023-y

zbMATH Keywords

parallelizationglobal routingchip designfractional packingfully polynomial approximation schememin-max resource sharing

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Applications of mathematical programming (90C90) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Programming in abstract spaces (90C48)

Related Items (4)

Faster goal-oriented shortest path search for bulk and incremental detailed routing ⋮ Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results ⋮ Congestion Games with Multi-Dimensional Demands ⋮ An improved approximation algorithm for the uniform cost-distance Steiner tree problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for general packing problems and their application to the multicast congestion problem
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Potential function methods for approximately solving linear programming problems: theory and practice.
• Approximating Fractional Multicommodity Flow Independent of the Number of Commodities
• The maximum concurrent flow problem
• Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Coordination Complexity of Parallel Price-Directive Decomposition
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• Approximating Fractional Packings and Coverings in O(1/epsilon) Iterations
• Integer Programming and Combinatorial Optimization

This page was built for publication: Faster min-max resource sharing in theory and practice