Typical properties of winners and losers in discrete optimization. (English) Zbl 1192.90156
Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 343-352, electronic only (2004).
MSC:
| 90C27 | Combinatorial optimization |
| 90C10 | Integer programming |
| 68W40 | Analysis of algorithms |
| 90C60 | Abstract computational complexity for mathematical programming problems |
References:
| [1] | C. Banderier, R. Beier and K. Mehlhorn. Smoothed Analysis of three combinatorial problems. Proc. 28th MFCS, 198-207, 2003.]] · Zbl 1124.68371 |
| [2] | A. Blum and J. Dunagan. Smoothed Analysis of the Perceptron Algorithm. Proc. of the 13th SODA, 905-914, 2003.]] |
| [3] | L. Becchetti, S. Leonardi, A. Marchetti-Spaccamela, G. Schafer and T. Vredeveld. Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm. Proc. of the 44th FOCS, 462-471, 2003.]] |
| [4] | F. Barahona and W. R. Pulleyblank. Exact arborescences, matchings and cycles. Discrete Applied Mathematics, 16, 617-630, 1998.]] 10.1016/0166-218X(87)90067-9 |
| [5] | R. Beier and B. Vocking. Random knapsack in expected polynomial time. Proc. of the 35th STOC, 232-241, 2003.]] 10.1145/780542.780578 · Zbl 1192.90157 |
| [6] | R. Beier and B. Vocking. Probabilistic analysis of knapsack core algorithms. Proc. of the 14th SODA, 2004.]] |
| [7] | J. Dunagan, D. A. Spielman, and S. -H. Teng. Smoothed analysis of Renegar’s condition number for linear programming. Available at http://arxiv. org/abs/cs. DS/0302011, 2002.]] |
| [8] | V. Damerow, F. Meyer auf der Heide, H. Racke, C. Scheideler and C. Sohler. Smoothed motion complexity. Proc. of the 11th ESA, 2003.]] |
| [9] | M. E. Dyer and A. M. Frieze. Probabilistic analysis of the multidimensional knapsack problem. Mathematics of Operations Research 14(1), 162-176, 1989.]] · Zbl 0676.90046 |
| [10] | M. R. Garey and D. S Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, 1979.]] · Zbl 0411.68039 |
| [11] | M. X. Goemans and R. Ravi. The Constrained Minimum Spanning Tree Problem. Fifth Scandinavian Workshop on Algorithm Theory, 66-75, 1996.]] · Zbl 1502.90184 |
| [12] | A. Goldberg and A. Marchetti-Spaccamela. On finding the exact solution to a Zero-One Knapsack Problem. Proc. of the 16th STOC, 359-368, 1984.]] 10.1145/800057.808701 |
| [13] | L. A. Levin. Average Case Complete Problems. SIAM J. Cornput., 15(1):285-286, 1986.]] 10.1137/0215020 · Zbl 0589.68032 |
| [14] | G. S. Lueker. On the average difference between the solutions to linear and integer Knapsack Problems. Applied Probability - Computer Science, the Interface, 1, Birkhauser, 1982.]] · Zbl 0647.90062 |
| [15] | G. S. Lueker. Average-case analysis of Off-Line and On-Line Knapsack Problems. J. of Algorithms, 19, 277-305, 1998.]] 10.1006/jagm.1998.0954 · Zbl 0916.68069 |
| [16] | G. S. Lueker. Exponentially small bounds on the expected optimum of the Partition and Subset Sum Problems. Random Structures and Algorithms, 12, 51-62, 1998.]] 10.1002/(SICI)1098-2418(199801)12:1 · Zbl 0894.90125 |
| [17] | K. Mehlhorn and M. Ziegelmann. Resource Constrained Shortest Paths. Proc. 8th ESA, 326-337, 2000.]] · Zbl 0974.68215 |
| [18] | K. Mulmuley, U. Vazirani and V. V. Vazirani. Matching is as easy as matrix inversion. Combinatorica 7(1):105-113, 1987.]] 10.1007/BF02579206 · Zbl 0632.68041 |
| [19] | C. H. Papadimitriou and M. Yannakakis. The complexity of tradeoffs, and optimal access of web sources. Proc. of the 41st FOCS, 86-92, 2000.]] |
| [20] | J. Renegar. Some perturbation theory for linear programming. Math. Programming, 65(1, Series A), 73-91, 1994.]] · Zbl 0818.90073 |
| [21] | J. Renegar. Incorporating condition measures into the complexity of linear programming. SIAM J. Optim., 5(3):506-524, 1995.]] · Zbl 0838.90139 |
| [22] | J. Renegar. Linear programming, complexity theory and elementary functional analysis. Math. Programming, 70(3, Series A), 279-351, 1995.]] · Zbl 0855.90085 |
| [23] | H. M. Salkin. Integer Programming. Addison-Wesley, Reading, Mass., 1975.]] · Zbl 0319.90038 |
| [24] | D. A. Spielman and S. -H. Teng. Smoothed Analysis of algorithms: why the Simplex Algorithm usually takes polynomial time. Proc. of the 33rd STOC, 296-305, 2001.]] 10.1145/380752.380813 · Zbl 1323.68636 |
| [25] | D. A. Spielman and S. -H. Teng. Smoothed Analysis: Motivation and discrete models. Proc. of WADS 2003, 256-270, 2003.]] · Zbl 1253.68378 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
