lagrangian relaxation links
(as of 2000 and very incomplete!)
-
H. W. Kuhn and A. W. Tucker. Review of `A numerical method for determination
of the value and the best strategies of a zero-sum two-person game with
large numbers of strategies', by John von Neumann. In John von Neumann:
Collected Works, volume VI, pages 96--97. Pergamon Press, 1963.
http://citeseer.nj.nec.com/context/1804596/0 -
P. C. Gilmore and R. E. Gomory.
A linear programming approach to the cutting stock problem.
Operations Research, 9:849-859, 1961. -
Dantzig, G.B. and Wolfe, P.
Decomposition principle for linear programs.
Operations Research, 8: 101-111,1960. -
M. Held and R. M. Karp.
The traveling-salesman problem and minimum spanning trees: Part II.
Mathematical Programming, 1:6--25, 1971. -
F. Shahroki and D. W. Matula.
The maximum concurrent flow problem.
Journal of the ACM, 37:318--334, 1990. -
Fast Approximation
Algorithms for Fractional Packing and Covering Problems (1991)
Serge A. Plotkin, David B. Shmoys, Eva Tardos -
Fast Approximation Algorithms
for Multicommodity Flow Problems (1993)
Tom Leighton, Fillia Makedon, Serge Plotkin, Clifford Stein, Eva Tardos, Spyros Tragoudas -
A Simple
Local-Control Approximation Algorithm for Multicommodity Flow (1993)
Baruch Awerbuch, Tom Leighton -
Fast Approximation
Algorithms for Fractional Packing and Covering Problems (1995)
Serge A. Plotkin, David B. Shmoys, Eva Tardos -
Efficient
Approximation Algorithms for Semidefinite Programs.. (1996)
Klein, Lu - Game Theory, On-line Prediction and Boosting - Freund, Schapire (1996)
-
Faster and Simpler
Algorithms for Multicommodity Flow and other Fractional Packing Problems
(1997)
Naveen Garg, Jochen Könemann -
Global
Optimization Using Local Information with Applications to Flow Control
(1997)
Yair Bartal, John W. Byers, Danny Raz -
Condition Number Complexity
of an Elementary Algorithm for Computing a Reliable Solution of a Conic
Linear System (1998)
Epelman, Freund -
Approximating
fractional multicommodity flow independent of the number of commodities
(1999)
Lisa K. Fleischer -
Fast Combinatorial
Algorithms for Packing and Covering Problems (2000)
Jochen Könemann
Miscellaneous related references
-
Local Optimization
of Global Objectives: Competitive Competitive Distributed Deadlock Resolution
and Resource Allocation (1994)
Baruch Awerbuch -
On-Line Routing
of Virtual Circuits with Applications to Load Balancing and Machine Scheduling
(1997)
James Aspnes Yossi Azar Amos Fiat Serge Plotkin Orli Waarts -
Combinatorial
Auctions: A Survey (2001)
Sven de Vries, Rakesh Vohra -
On Combinatorial Auction and Lagrangean Relaxation for Distributed Resource Scheduling
(1998)
Erhan Kutanoglu, S. David Wu -
Network
Flows: Theory, Algorithms, and Applications (chapter 16)
Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin