Fast Approximation Algorithms for Fractional Packing and Covering Problems
From MaRDI portal
Publication:4848416
DOI10.1287/moor.20.2.257zbMath0837.90103OpenAlexW2134422938MaRDI QIDQ4848416
David B. Shmoys, Éva Tardos, Serge A. 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
coveringLagrangian relaxationapproximate solutionstraveling salesmanunrelated parallel machinesmulticommodity flowcutting-stockjob shop problemnetwork embeddingfractional packingminimum-cost multicommodity flow
Integer programming (90C10) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)
Related Items
Max-min fair rate allocation and routing in energy harvesting networks: algorithmic analysis, Distributed Broadcast Revisited: Towards Universal Optimality, A faster combinatorial approximation algorithm for scheduling unrelated parallel machines, Oracle-Based Robust Optimization via Online Learning, Task scheduling in networks, Greedy distributed optimization of multi-commodity flows, Fast First-Order Algorithms for Packing–Covering Semidefinite Programs, Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time, A multiplicative weights update algorithm for MINLP, A simple method for convex optimization in the oracle model, Solving MIPs via scaling-based augmentation, Approximation and online algorithms for multidimensional bin packing: a survey, A note on a variant of the online open end bin packing problem, A sublinear-time randomized approximation algorithm for matrix games, iGreen: green scheduling for peak demand minimization, A faster FPTAS for the unbounded knapsack problem, On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms, Faster and simpler approximation algorithms for mixed packing and covering problems, Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence, A quantization framework for smoothed analysis of Euclidean optimization problems, Dynamic Resource Allocation in the Cloud with Near-Optimal Efficiency, Scheduling multicasts on unit-capacity trees and meshes., Approximating covering integer programs with multiplicity constraints, Vector bin packing with multiple-choice, Barrier subgradient method, Unnamed Item, Approximation algorithms for general packing problems and their application to the multicast congestion problem, Fast approximation of minimum multicast congestion – Implementation VERSUS Theory, Inferring Sparse Preference Lists from Partial Information, Interior-Point-Based Online Stochastic Bin Packing, Fractional Set Cover in the Streaming Model., Register loading via linear programming, On routing in VLSI design and communication networks, Improved parallel approximation of a class of integer programming problems, An improved approximation scheme for variable-sized bin packing, A new approach to computing optimal schedules for the job-shop scheduling problem, On integer balancing of directed graphs, A generalized approximation framework for fractional network flow and packing problems, New error measures and methods for realizing protein graphs from distance data, Mobile facility location: combinatorial filtering via weighted occupancy, On the approximability of robust network design, Faster min-max resource sharing in theory and practice, An improved approximation algorithm for the partial Latin square extension problem., Pricing for fairness: distributed resource allocation for multiple objectives, Dynamic programming based algorithms for set multicover and multiset multicover problems, Faster shortest-path algorithms for planar graphs, Self-concordant barriers for convex approximations of structured convex sets, An approximation algorithm for the general max-min resource sharing problem, Near-linear algorithms for geometric hitting sets and set covers, Rounding of convex sets and efficient gradient methods for linear programming problems, Better Bin Packing Approximations via Discrepancy Theory, Packing trees in communication networks, Unnamed Item, Distributed Approximate Maximum Matching in the CONGEST Model., Adaptive game playing using multiplicative weights, How the Experts Algorithm Can Help Solve LPs Online, Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent, Flows with unit path capacities and related packing and covering problems, Approximability of flow shop scheduling, Hitting sets when the VC-dimension is small, Price-based protocols for fair resource allocation, Flows with Unit Path Capacities and Related Packing and Covering Problems, Approximation algorithms for covering/packing integer programs, I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs, An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries, Unnamed Item, Exponential weight approachability, applications to calibration and regret minimization, A technique for speeding up the solution of the Lagrangean dual, Near-Optimal Distributed Maximum Flow, An approximation algorithm for the generalized assignment problem
