Approximation algorithms for general packing problems and their application to the multicast congestion problem
DOI10.1007/S10107-007-0106-8zbMATH Open1137.90011OpenAlexW2099335235MaRDI QIDQ925266FDOQ925266
Authors: 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
Recommendations
Convex programming (90C25) Linear programming (90C05) Analysis of algorithms (68W40) Approximation algorithms (68W25) Network design and communication in computer systems (68M10)
Cites Work
- Geometric algorithms and combinatorial optimization
- An asymptotic fully polynomial time approximation scheme for bin covering.
- Approximate max-min resource sharing for structured concave optimization
- Proof verification and the hardness of approximation problems
- Approximation algorithms for scheduling unrelated parallel machines
- Title not available (Why is that?)
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Approximate strong separation with application in fractional graph coloring and preemptive scheduling.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fast Approximate Graph Partitioning Algorithms
- The Steiner problem with edge lengths 1 and 2
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- On PreemptiveResource Constrained Scheduling: Polynomial-Time Approximation Schemes
- An approximation algorithm for the general max-min resource sharing problem
- Title not available (Why is that?)
- Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints
- Coordination Complexity of Parallel Price-Directive Decomposition
- Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time
- Experimental and Efficient Algorithms
- Fast deterministic approximation for the multicommodity flow problem
- Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts
- Randomized metarounding (extended abstract)
- Algorithms – ESA 2004
- Improved Approximation Schemes for Scheduling Unrelated Parallel Machines
- Faster and simpler approximation algorithms for mixed packing and covering problems
- Title not available (Why is that?)
- Fast approximation of minimum multicast congestion – Implementation VERSUS Theory
- Approximation Algorithm for the Mixed Fractional Packing and Covering Problem
- Title not available (Why is that?)
- Assign ranges in general ad-hoc networks
- Title not available (Why is that?)
- Structural Information and Communication Complexity
- Algorithms and Computation
Cited In (11)
- Title not available (Why is that?)
- Faster min-max resource sharing in theory and practice
- Fast approximation of minimum multicast congestion – Implementation VERSUS Theory
- Construction algorithms and approximation bounds for the streaming cache placement problem in multicast networks
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fair packing and covering on a relative scale
- Experimental and Efficient Algorithms
- Heuristic algorithms for packing of multiple-group multicasting
- On routing in VLSI design and communication networks
- Packing trees in communication networks
This page was built for publication: Approximation algorithms for general packing problems and their application to the multicast congestion problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q925266)
