{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:14:34Z","timestamp":1725664474349},"publisher-location":"Berlin, Heidelberg","reference-count":45,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540587156"},{"type":"electronic","value":"9783540490548"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58715-2_133","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:42:21Z","timestamp":1330274541000},"page":"300-317","source":"Crossref","is-referenced-by-count":1,"title":["Randomized approximation algorithms in combinatorial optimization"],"prefix":"10.1007","author":[{"given":"Prabhakar","family":"Raghavan","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"25_CR1","doi-asserted-by":"crossref","unstructured":"F. Alizadeh. Interior point methods in semidefinite programming with applications to combinatorial optimization. To appear in the SIAM Journal on Optimization, 1994.","DOI":"10.1137\/0805002"},{"key":"25_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, pages 14\u201323, 1992.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"25_CR3","doi-asserted-by":"crossref","unstructured":"S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization of NP. In Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, pages 2\u201313, 1992.","DOI":"10.1109\/SFCS.1992.267824"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"M. Bellare and M. Sudan. Improved non-approximability results. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 184\u2013193, 1994.","DOI":"10.1145\/195058.195129"},{"key":"25_CR5","doi-asserted-by":"crossref","first-page":"1026","DOI":"10.1145\/115234.115347","volume":"38","author":"B. Berger","year":"1991","unstructured":"B. Berger and J. Rompel. Simulating (log \u00b0 n)-wise independence in NC. Journal of the ACM, 38: 1026\u20131046, 1991.","journal-title":"Journal of the ACM"},{"key":"25_CR6","unstructured":"D. Bertsimas and R. Vohra. Linear programming relaxations, approximation algorithms and randomization: a unified view of covering problems. Technical Report OR 285-94, MIT, 1994."},{"key":"25_CR7","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1145\/176584.176586","volume":"41","author":"A. Blum","year":"1994","unstructured":"A. Blum. New approximation algorithms for graph coloring. Journal of the ACM, 41: 470\u2013516, 1994.","journal-title":"Journal of the ACM"},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"J. A. Bondy and U.S. R. Murty. Graph Theory With Applications. American Elsevier, 1977.","DOI":"10.1007\/978-1-349-03521-2"},{"key":"25_CR9","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/BF01994876","volume":"32","author":"R.B. Boppana","year":"1992","unstructured":"R.B. Boppana and M.M. Halldorson. Approximating maximum independent sets by excluding subgraphs. BIT, 32: 180\u2013196, 1992.","journal-title":"BIT"},{"key":"25_CR10","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1007\/BF01585184","volume":"62","author":"C. Delorme","year":"1993","unstructured":"C. Delorme and S. Poljak. Laplacian eigenvalues and the maximum cut problem. Mathematical Programming, 62: 557\u2013574, 1993.","journal-title":"Mathematical Programming"},{"key":"25_CR11","unstructured":"G.S. Ditlow and P. Raghavan. Timing-driven partitioning of PLAs. IBM Technical Disclosure Bulletin, 31, 1989."},{"key":"25_CR12","unstructured":"U. Feige and M.X. Goemans. Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT. Submitted for publication, 1994."},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"A. Frieze and M. Jerrum. Improved approximation algorithms for MAX k-CUT and MAX BISECTION. Submitted for publication, 1994.","DOI":"10.1007\/3-540-59408-6_37"},{"key":"25_CR14","doi-asserted-by":"crossref","unstructured":"S. Gao and M. Kaufmann. Channel routing of multiterminal nets. In 28th Annual Symposium on Foundations of Computer Science, pages 316\u2013325, October 1987.","DOI":"10.1109\/SFCS.1987.13"},{"key":"25_CR15","unstructured":"M. X. Goemans and D. P. Williamson. New 3\/4-approximation algorithms for MAX SAT. To appear in SIAM J. Disc. Math., 1993."},{"key":"25_CR16","doi-asserted-by":"crossref","unstructured":"M.X. Goemans and D.P. Williamson. 0.878-approximation algorithms for MAX-CUT and MAX-2SAT. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 422\u2013431, 1994.","DOI":"10.1145\/195058.195216"},{"key":"25_CR17","volume-title":"Matrix Computations","author":"G.H. Golub","year":"1983","unstructured":"G.H. Golub and C.F. van Loan. Matrix Computations. The Johns Hopkins University Press, Baltimore, MD, 1983."},{"key":"25_CR18","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Gr\u00f6tschel","year":"1981","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1: 169\u2013197, 1981.","journal-title":"Combinatorica"},{"key":"25_CR19","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"D.S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9: 256\u2013278, 1974.","journal-title":"Journal of Computer and System Sciences"},{"key":"25_CR20","doi-asserted-by":"crossref","unstructured":"D. Karger, R. Motwani, and M. Sudan. Approximate graph coloring by semidefinite programming. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994.","DOI":"10.1109\/SFCS.1994.365710"},{"key":"25_CR21","doi-asserted-by":"crossref","unstructured":"S. Khanna, N. Linial, and S. Safra. On the hardness of approximating the chromatic number. In Proceedings of the 2nd Israeli Symposium on Theory and Computing Systems, pages 250\u2013260, 1993.","DOI":"10.1109\/ISTCS.1993.253464"},{"key":"25_CR22","doi-asserted-by":"crossref","unstructured":"P.N. Klein and S. Sairam. A parallel randomized approximation scheme for shortest paths. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 750\u2013758, 1992.","DOI":"10.1145\/129712.129785"},{"key":"25_CR23","doi-asserted-by":"crossref","unstructured":"P.N. Klein, C. Stein, and \u00c9. Tardos. Leighton-Rao might be practical: faster approximation algorithms for concurrent flow with uniform capacities. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pages 310\u2013321, 1990.","DOI":"10.1145\/100216.100257"},{"key":"25_CR24","doi-asserted-by":"crossref","unstructured":"G. Kortsarz and D. Peleg. Generating low-degree 2-spanners. Technical Report CS93-07, The Weizmann Institute of Science, 1993.","DOI":"10.1007\/3-540-55706-7_7"},{"key":"25_CR25","doi-asserted-by":"crossref","unstructured":"J.-H. Lin and J.S. Vitter. \u03b5-approximations with minimum packing constraint violation. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 771\u2013782, 1992.","DOI":"10.1145\/129712.129787"},{"key":"25_CR26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"IT-25","author":"L. Lov\u00e1sz","year":"1979","unstructured":"L. Lov\u00e1sz. On the Shannon capacity of a graph. IEEE Trans. Information Theory, IT-25: 1\u20137, 1979.","journal-title":"IEEE Trans. Information Theory"},{"key":"25_CR27","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"L. Lov\u00e1sz","year":"1987","unstructured":"L. Lov\u00e1sz M. Gr\u00f6tschel and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin, 1987."},{"key":"25_CR28","doi-asserted-by":"crossref","unstructured":"R. Motwani, J. Naor, and M. Naor. The probabilistic method yields deterministic parallel algorithms. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, pages 8\u201313, October 1989.","DOI":"10.1109\/SFCS.1989.63448"},{"key":"25_CR29","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1994","unstructured":"R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, New York, 1994. In Press."},{"key":"25_CR30","doi-asserted-by":"crossref","unstructured":"M. Naor and R.M. Roth. Optimal file sharing in distributed networks. In 32nd Annual IEEE Symposium on Foundations of Computer Science, pages 515\u2013525, 1991.","DOI":"10.1109\/SFCS.1991.185414"},{"issue":"3","key":"25_CR31","first-page":"229","volume":"6","author":"A.P-C. Ng","year":"1987","unstructured":"A.P-C. Ng, P. Raghavan, and C.D. Thompson. Experimental results for a linear program global router. Computers and Artificial Intelligence, 6(3): 229\u2013242, 1987.","journal-title":"Computers and Artificial Intelligence"},{"key":"25_CR32","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"C.H. Papadimitriou and M. Yannakakis. Optimization, approximation and complexity classes. Journal of Computer and System Sciences, 43: 425\u2013440, 1991.","journal-title":"Journal of Computer and System Sciences"},{"key":"25_CR33","doi-asserted-by":"crossref","unstructured":"S.A. Plotkin, D.B. Shmoys, and E. Tardos. Fast approximation algorithms for fractional packing and covering problems. In 32nd Annual IEEE Symposium on Foundations of Computer Science, pages 495\u2013504, 1991.","DOI":"10.1109\/SFCS.1991.185411"},{"key":"25_CR34","unstructured":"W.R. Pulleyblank and P. Raghavan, 1994. Personal communication, IBM Yorktown Heights."},{"key":"25_CR35","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","volume":"37","author":"P. Raghavan","year":"1988","unstructured":"P. Raghavan. Probabilistic construction of deterministic algorithms: Approximating packing integer programs. Journal of Computer and System Sciences, 37: 130\u2013143, October 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"25_CR36","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"P. Raghavan and C.D. Thompson. Randomized rounding. Combinatorica, 7: 365\u2013374, 1987.","journal-title":"Combinatorica"},{"key":"25_CR37","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S. Sahni","year":"1976","unstructured":"S. Sahni and T. Gonzalez. P-complete approximation problems. Journal of the ACM, 23: 555\u2013565, 1976.","journal-title":"Journal of the ACM"},{"key":"25_CR38","unstructured":"J.P. Schmidt, A. Siegel, and A. Srinivasan. Chernoff-Hoeffdmg bounds for applications with limited independence. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 331\u2013340, 1993."},{"key":"25_CR39","volume-title":"Algorithms for Random Generation and Counting: A Markov Chain Approach","author":"A. Sinclair","year":"1992","unstructured":"A. Sinclair. Algorithms for Random Generation and Counting: A Markov Chain Approach. Progress in Theoretical Computer Science. Birkhauser, Boston, 1992."},{"issue":"2","key":"25_CR40","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1090\/S0002-9947-1985-0784009-0","volume":"289","author":"J. Spencer","year":"1985","unstructured":"J. Spencer. Six standard deviations suffice. Transactions of the American Mathematical Society, 289(2): 679\u2013706, June 1985.","journal-title":"Transactions of the American Mathematical Society"},{"key":"25_CR41","unstructured":"J. Spencer. Ten Lectures on the Probabilistic Method, SIAM, 1987."},{"key":"25_CR42","doi-asserted-by":"crossref","unstructured":"M. Szegedy. A note on the \u03b8 number of Lov\u00e1sz and the generalized Delsarte bound. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994.","DOI":"10.1109\/SFCS.1994.365707"},{"key":"25_CR43","doi-asserted-by":"crossref","unstructured":"P.J.M. van Laarhoven and E.H.L. Aarts. Simulated Annealing: Theory and Applications. Mathematics and its Applications. Reidel Publishing Company, 1987.","DOI":"10.1007\/978-94-015-7744-1"},{"key":"25_CR44","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1145\/2157.2158","volume":"30","author":"A. Wigderson","year":"1983","unstructured":"A. Wigderson. Improving the performance guarantee for approximate graph coloring. Journal of the ACM, 30: 729\u2013735, 1983.","journal-title":"Journal of the ACM"},{"key":"25_CR45","unstructured":"M. Yannakakis. On the approximation of maximum satisfiability. In Proceedings of the 3rd ACM-SIAM Symposium on Discrete Algorithms, pages 1\u20139, 1992."}],"container-title":["Lecture Notes in Computer Science","Foundation of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58715-2_133.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T08:23:42Z","timestamp":1640939022000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58715-2_133"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540587156","9783540490548"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/3-540-58715-2_133","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}