Approximate Max-Min Resource Sharing for Structured Concave Optimization

DOI10.1137/S1052623499358689zbMath1010.90060OpenAlexW2050328660MaRDI QIDQ2719242

Lorant Porkolab, Jorge Villavicencio, Michael D. Grigoriadis, Leonid G. Khachiyan

Publication date: 21 June 2001

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s1052623499358689

zbMATH Keywords

approximation algorithmLagrangian decompositionlogarithmic potentialpacking problemresource sharingcovering problemstructured optimization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Large-scale problems in mathematical programming (90C06) Nonconvex programming, global optimization (90C26) Linear programming (90C05) Combinatorial optimization (90C27)

Related Items (18)

APPROXIMATION ALGORITHMS FOR MULTIPLE STRIP PACKING AND SCHEDULING PARALLEL JOBS IN PLATFORMS ⋮ Finding Sparse Solutions for Packing and Covering Semidefinite Programs ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ 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 ⋮ A multiplicative weight updates algorithm for packing and covering semi-infinite linear programs ⋮ Approximation algorithms for general packing problems and their application to the multicast congestion problem ⋮ Scientific contributions of Leo Khachiyan (a short overview) ⋮ An improved approximation scheme for variable-sized bin packing ⋮ An approximation algorithm for the general max-min resource sharing problem ⋮ Improved approximation algorithms for minimum power covering problems ⋮ Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs ⋮ On randomized fictitious play for approximating saddle points over convex sets ⋮ Approximation Schemes for Machine Scheduling with Resource (In-)dependent Processing Times ⋮ A Robust AFPTAS for Online Bin Packing with Polynomial Migration ⋮ On the rate of convergence of deterministic and randomized RAS matrix scaling algorithms ⋮ New approximability results for two-dimensional bin packing

This page was built for publication: Approximate Max-Min Resource Sharing for Structured Concave Optimization