Coordination Complexity of Parallel Price-Directive Decomposition

DOI10.1287/moor.21.2.321zbMath0857.90100OpenAlexW2066883826MaRDI QIDQ4895561

Michael D. Grigoriadis, Leonid G. Khachiyan

Publication date: 11 March 1997

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.21.2.321

zbMATH Keywords

block-angular convex resource sharingcoordination complexity of approximate price directive decompositionminimum-cost multicommodity flows

Mathematics Subject Classification ID

Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Deterministic network models in operations research (90B10) Distributed algorithms (68W15)

Related Items (24)

Global convergence of a smooth approximation method for mathematical programs with complementarity constraints ⋮ Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time ⋮ APPROXIMATION ALGORITHMS FOR FLEXIBLE JOB SHOP PROBLEMS ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ 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 ⋮ Unnamed Item ⋮ An asymptotic fully polynomial time approximation scheme for bin covering. ⋮ Approximation algorithms for general packing problems and their application to the multicast congestion problem ⋮ Grouping techniques for scheduling problems: simpler and faster ⋮ On routing in VLSI design and communication networks ⋮ Scientific contributions of Leo Khachiyan (a short overview) ⋮ A generalized approximation framework for fractional network flow and packing problems ⋮ Approximation schemes for job shop scheduling problems with controllable processing times ⋮ Faster min-max resource sharing in theory and practice ⋮ Self-concordant barriers for convex approximations of structured convex sets ⋮ An approximation algorithm for the general max-min resource sharing problem ⋮ Computer science and decision theory ⋮ Approximation schemes for scheduling and covering on unrelated machines ⋮ On randomized fictitious play for approximating saddle points over convex sets ⋮ Packing trees in communication networks ⋮ Regularized smoothing approximations to vertical nonlinear complementarity problems ⋮ Flows with unit path capacities and related packing and covering problems

This page was built for publication: Coordination Complexity of Parallel Price-Directive Decomposition