Approximation algorithms for general packing problems and their application to the multicast congestion problem

DOI10.1007/s10107-007-0106-8zbMath1137.90011OpenAlexW2099335235MaRDI QIDQ925266

Klaus Jansen, Hu Zhang

Publication date: 3 June 2008

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-007-0106-8

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Convex programming (90C25) Linear programming (90C05) Network design and communication in computer systems (68M10) Approximation algorithms (68W25)

Related Items (3)

On routing in VLSI design and communication networks ⋮ Faster min-max resource sharing in theory and practice ⋮ Packing trees in communication networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for scheduling unrelated parallel machines
• Faster and simpler approximation algorithms for mixed packing and covering problems
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• The Steiner problem with edge lengths 1 and 2
• Geometric algorithms and combinatorial optimization
• Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time
• Fast deterministic approximation for the multicommodity flow problem
• Approximate strong separation with application in fractional graph coloring and preemptive scheduling.
• An asymptotic fully polynomial time approximation scheme for bin covering.
• An approximation algorithm for the general max-min resource sharing problem
• Assign ranges in general ad-hoc networks
• Approximate Max-Min Resource Sharing for Structured Concave Optimization
• Proof verification and the hardness of approximation problems
• Randomized metarounding (extended abstract)
• Approximation Algorithm for the Mixed Fractional Packing and Covering Problem
• Fast Approximate Graph Partitioning Algorithms
• Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints
• Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Coordination Complexity of Parallel Price-Directive Decomposition
• Structural Information and Communication Complexity
• Algorithms – ESA 2004
• Fast approximation of minimum multicast congestion – Implementation VERSUS Theory
• Improved Approximation Schemes for Scheduling Unrelated Parallel Machines
• Experimental and Efficient Algorithms
• On PreemptiveResource Constrained Scheduling: Polynomial-Time Approximation Schemes
• Algorithms and Computation

This page was built for publication: Approximation algorithms for general packing problems and their application to the multicast congestion problem