Combinatorial Optimization
(Selected Papers)
- An Implementation of a Combinatorial Approximation
Algorithm
for Minimum-Cost Multicommodity Flow
A. Goldberg and J. D. Oldham and S. Plotkin and C.
Stein
IPCO-1998
Adding Multiple Cost
Constraints to Combinatorial Optimization Problems,
- with Applications to
Multicommodity Flows.
- D. Karger and S. Plotkin, STOC 95.
- Fast Approximation Algorithm for
Minimum Cost Multicommodity Flow.
- A. Kamath, O. Palmon, and S. Plotkin,
- Tech. Rep. STAN-CS-TN-95-19. Prelim. version in SODA 95.
- Bounds on the Max-Flow Min-Cut
Ratio for Directed Multicommodity Flows.
- P. Klein, S. Plotkin, S. Rao, and E. Tardos.
- Improved approximation
algorithms for network design problems.
- M. Goemans, A. Goldberg, S. Plotkin, D. Shmoys, E.
Tardos, and D. Williamson.
- In SODA 1994.
- Shallow excluded minors and
improved graph decompositions.
- S. Plotkin, S. Rao, and W. Smith.
- In SODA 1994.
- Planar graphs, multicommodity
flow, and network decomposition.
- P. Klein, S. Plotkin, and S. Rao.
- In STOC 1993.
- Improved bounds on the max-flow
min-cut ratio for multicommodity flows.
- S. Plotkin and E. Tardos.
- Combinatorica version. Prelim. version in STOC 93.
- Fast approximation algorithms for
fractional packing and covering problems.
- S. Plotkin, D. Shmoys, and E. Tardos.
- Math of Oper. Res. 1995. Preliminary version in FOCS
1991.
- Fast approximation algorithms for
multicommodity flow problem.
- T. Leighton, F. Makedon, S. Plotkin, C. Stein, E. Tardos,
and S. Tragoudas.
- JCSS version, Preliminary vers. in STOC 1991.
- Faster approximation algorithms for the
unit capacity concurrent flow problem
- with applications to routing and
finding sparse cuts.
- P. Klein, S. Plotkin, C. Stein, and E. Tardos.
- SICOMP, June 1994. Preliminary vers. in STOC 1991.
- Using Separation Algorithms in
Fixed Dimension.
- C. Haibt-Norton, S. Plotkin, and E. Tardos.
- J. Alg., 1992. Prelim. version in SODA 1990.
- Improved Dual Network Simplex.
- J. Orlin, S. Plotkin, and E. Tardos.
- Math. Programming, 1993. Preliminary vers. in SODA 1990.
- Combinatorial Algorithms for the
Generalized Circulation Problem.
- A. Goldberg, S. Plotkin, and E. Tardos.
- Math. of Oper. Res., 1991. Preliminary version in FOCS
1988.