Fast Approximation Algorithms for Fractional Packing and Covering Problems
From MaRDI portal
Publication:4848416
DOI10.1287/MOOR.20.2.257zbMATH Open0837.90103OpenAlexW2134422938MaRDI QIDQ4848416FDOQ4848416
Authors: David B. Shmoys, Éva Tardos, Serge Plotkin 
Publication date: 17 September 1995
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/8884
Recommendations
- scientific article; zbMATH DE number 1839427
- Faster approximation schemes for fractional multicommodity flow problems
- Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
- Fast approximation algorithms for multicommodity flow problems
- Approximating Fractional Packings and Coverings in O(1/epsilon) Iterations
network embeddingapproximate solutionscoveringLagrangian relaxationtraveling salesmanmulticommodity flowunrelated parallel machinesjob shop problemfractional packingcutting-stockminimum-cost multicommodity flow
Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Integer programming (90C10) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)
Cited In (81)
- Near-optimal distributed maximum flow
- Fast First-Order Algorithms for Packing–Covering Semidefinite Programs
- I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs
- The Lagrangian search method
- Inferring Sparse Preference Lists from Partial Information
- Max-min fair rate allocation and routing in energy harvesting networks: algorithmic analysis
- A simple method for convex optimization in the oracle model
- Minimum cut in \(O(m \log^2 n)\) time
- The entropy rounding method in approximation algorithms
- Flows with Unit Path Capacities and Related Packing and Covering Problems
- Fractional set cover in the streaming model
- Title not available (Why is that?)
- Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence
- Distributed approximate maximum matching in the CONGEST model
- On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms
- An improved approximation algorithm for the partial Latin square extension problem.
- A generalized approximation framework for fractional network flow and packing problems
- Approximating covering integer programs with multiplicity constraints
- Better bin packing approximations via discrepancy theory
- Linear coupling: an ultimate unification of gradient and mirror descent
- A new approach to computing optimal schedules for the job-shop scheduling problem
- Active learning for cost-sensitive classification
- Fast approximation of matroid packing and covering
- Scheduling multicasts on unit-capacity trees and meshes.
- Faster min-max resource sharing in theory and practice
- A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
- Fast approximation of minimum multicast congestion – Implementation VERSUS Theory
- Self-concordant barriers for convex approximations of structured convex sets
- Approximation algorithms for general packing problems and their application to the multicast congestion problem
- Hitting sets when the VC-dimension is small
- Vector bin packing with multiple-choice
- An approximation algorithm for the generalized assignment problem
- Interior-point-based online stochastic bin packing
- On integer balancing of directed graphs
- Price-based protocols for fair resource allocation, convergence time analysis and extension to Leontief utilities
- Approximation algorithms for covering/packing integer programs
- A multiplicative weights update algorithm for MINLP
- Title not available (Why is that?)
- On the approximability of robust network design
- Rounding of convex sets and efficient gradient methods for linear programming problems
- Exponential weight approachability, applications to calibration and regret minimization
- Dynamic programming based algorithms for set multicover and multiset multicover problems
- Approximation and online algorithms for multidimensional bin packing: a survey
- An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
- A sublinear-time randomized approximation algorithm for matrix games
- Solving MIPs via scaling-based augmentation
- Adaptive game playing using multiplicative weights
- Faster and simpler approximation algorithms for mixed packing and covering problems
- Near-linear time approximation schemes for some implicit fractional packing problems
- Oracle-based robust optimization via online learning
- A quantization framework for smoothed analysis of Euclidean optimization problems
- An approximation algorithm for the general max-min resource sharing problem
- Faster shortest-path algorithms for planar graphs
- A simple method for convex optimization in the oracle model
- Barrier subgradient method
- How experts can solve LPs online
- iGreen: green scheduling for peak demand minimization
- A faster FPTAS for the unbounded knapsack problem
- Flows with unit path capacities and related packing and covering problems
- A fast approximation scheme for fractional covering problems with variable upper bounds
- Task scheduling in networks
- Computational Science and Its Applications – ICCSA 2004
- Register loading via linear programming
- Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time
- Approximability of flow shop scheduling
- An improved approximation scheme for variable-sized bin packing
- Near-linear algorithms for geometric hitting sets and set covers
- Distributed Broadcast Revisited: Towards Universal Optimality
- Pricing for fairness: distributed resource allocation for multiple objectives
- Approximating Fractional Packings and Coverings in O(1/epsilon) Iterations
- Approximation Schemes for Covering and Packing
- Mobile facility location: combinatorial filtering via weighted occupancy
- A note on a variant of the online open end bin packing problem
- Greedy distributed optimization of multi-commodity flows
- New error measures and methods for realizing protein graphs from distance data
- On routing in VLSI design and communication networks
- Packing trees in communication networks
- A technique for speeding up the solution of the Lagrangean dual
- Improved parallel approximation of a class of integer programming problems
- Dynamic resource allocation in the cloud with near-optimal efficiency
- Multicommodity network flows: A survey. II: Solution methods
This page was built for publication: Fast Approximation Algorithms for Fractional Packing and Covering Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4848416)
