{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:51:08Z","timestamp":1742914268221,"version":"3.40.3"},"publisher-location":"New York, NY","reference-count":107,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781461411673"},{"type":"electronic","value":"9781461411680"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-1-4614-1168-0_15","type":"book-chapter","created":{"date-parts":[[2011,12,2]],"date-time":"2011-12-02T05:18:38Z","timestamp":1322803118000},"page":"349-384","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Numerical Thinking in Algorithm Design and Analysis"],"prefix":"10.1007","author":[{"given":"Shang-Hua","family":"Teng","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,10,22]]},"reference":[{"key":"15_CR1_15","doi-asserted-by":"crossref","unstructured":"I. Abraham, Y. Bartal, O. Neiman. Nearly Tight Low Stretch Spanning Trees. FOCS 2008, Pages 781-790.","DOI":"10.1109\/FOCS.2008.62"},{"issue":"1","key":"15_CR2_15","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1137\/S0097539792224474","volume":"24","author":"N Alon","year":"1995","unstructured":"N. Alon, R.\u00a0M. Karp, D. Peleg, and D. West. A graph-theoretic game and its application to the k-server problem. SIAM Journal on Computing, 24(1):78\u2013100, February 1995.","journal-title":"SIAM Journal on Computing"},{"key":"15_CR3_15","doi-asserted-by":"crossref","unstructured":"C.\u00a0J. Alpert and S.-Z. Yao. Spectral partitioning: the more eigenvectors, the better. In DAC \u201995: Proceedings of the 32nd ACM\/IEEE conference on Design automation, pages 195\u2013200. ACM, 1995.","DOI":"10.1145\/217474.217529"},{"key":"15_CR4_15","doi-asserted-by":"crossref","unstructured":"R. Andersen, C. Borgs, J. T. Chayes, J. E. Hopcroft, K. Jain, and V. S. Mirrokni, and S.-H. Teng. Robust PageRank and locally computable spam detection features. In Fourth International Workshop on Adversarial Information Retrieval on the Web, ACM International Conference Proceeding Series, 2008 69\u201376.","DOI":"10.1145\/1451983.1452000"},{"key":"15_CR5_15","doi-asserted-by":"crossref","unstructured":"R. Andersen, C. Borgs, J.\u00a0T. Chayes, J.\u00a0E. Hopcraft, V.\u00a0S. Mirrokni, and S.-H. Teng. Local computation of pagerank contributions. In Anthony Bonato and Fan R.\u00a0K. Chung, editors, WAW, volume 4863 of Lecture Notes in Computer Science, pages 150\u2013165. Springer, 2007.","DOI":"10.1007\/978-3-540-77004-6_12"},{"key":"15_CR6_15","doi-asserted-by":"crossref","unstructured":"R. Andersen, F. Chung, and K. Lang. Local graph partitioning using pagerank vectors. Proceedings: 47th Annual Symposium on Foundations of Computer Science, pages 475\u2013486, 2006.","DOI":"10.1109\/FOCS.2006.44"},{"key":"15_CR7_15","doi-asserted-by":"crossref","unstructured":"R. Andersen, Y. Peres. Finding sparse cuts locally using evolving sets. STOC, 2009: 235\u2013244.","DOI":"10.1145\/1536414.1536449"},{"issue":"5","key":"15_CR8_15","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"S.\u00a0Arora. Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM, 45(5):753\u2013782, 1998.","journal-title":"J. ACM"},{"key":"15_CR9_15","unstructured":"S. Arora, E. Hazan, and S. Kale. 0(sqrt (log n)) approximation to Sparsest Cut in \u00f5(n2) time. In IEEE FOCS\u2019 04, pages 238\u2013247, 2004."},{"key":"15_CR10_15","doi-asserted-by":"crossref","unstructured":"S. Arora and S. Kale. A combinatorial, primal-dual approach to semidefinite programs. In ACM STOC \u201907, pages 227\u2013236, 2007.","DOI":"10.1145\/1250790.1250823"},{"key":"15_CR11_15","doi-asserted-by":"crossref","unstructured":"S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings and graph partitioning. In ACM STOC \u201904, pages 222\u2013231, 2004.","DOI":"10.1145\/1007352.1007355"},{"key":"15_CR12_15","doi-asserted-by":"crossref","unstructured":"D.\u00a0Arthur and S.\u00a0Vassilvitskii. Worst-case and smoothed analysis of the icp algorithm, with an application to the k-means method. In IEEE FOCS \u201906, pages 153\u2013164, 2006.","DOI":"10.1109\/FOCS.2006.79"},{"key":"15_CR13_15","doi-asserted-by":"crossref","unstructured":"D.\u00a0Arthur and B. Manthey and H. R\u00f6glin. k-Means Has Polynomial Smoothed Complexity. In IEEE FOCS, pages 405\u2013414, 2009.","DOI":"10.1109\/FOCS.2009.14"},{"key":"15_CR14_15","doi-asserted-by":"crossref","unstructured":"Nina Balcan and Avrim Blum and Anupam Gupta Approximate clustering without the approximation. SIAM\/ACM SODA 2009: 1068\u20131077.","DOI":"10.1137\/1.9781611973068.116"},{"key":"15_CR15_15","doi-asserted-by":"crossref","unstructured":"J. Batson, D.\u00a0A. Spielman, and N. Srivastava. Twice-Ramanujan sparsifiers. Available at http:\/\/arxiv.org\/abs\/0808.0163, 2008.","DOI":"10.1145\/1536414.1536451"},{"issue":"1","key":"15_CR16_15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00211-002-0445-6","volume":"95","author":"M Bebendorf","year":"2003","unstructured":"M. Bebendorf and W. Hackbusch. Existence of H-matrix approximants to the inverse FE-matrix of elliptic operators with L \u221e -coefficients. Numerische Mathematik, 95(1):1\u201328, July 2003.","journal-title":"Numerische Mathematik"},{"key":"15_CR17_15","unstructured":"A.\u00a0A. Bencz\u00far and D.\u00a0R. Karger. Approximating s-t minimum cuts in O(n2) time. In ACM STOC \u201996,"},{"key":"15_CR18_15","doi-asserted-by":"crossref","unstructured":"M. Bern, J.Gilbert, B. Hendrickson, N. Nguyen, and S. Toledo. Support-graph preconditioners. In SIAM. J. Matrix Anal. and Appl. 27(4), 930\u2013951, 2006.","DOI":"10.1137\/S0895479801384019"},{"key":"15_CR19_15","unstructured":"Avrim Blum and John Dunagan. Smoothed analysis of the perceptron algorithm for linear programming. In SIAM\/ACM SODA \u201902, pages 905\u2013914, 2002."},{"issue":"3","key":"15_CR20_15","doi-asserted-by":"publisher","first-page":"694","DOI":"10.1137\/S0895479801390637","volume":"25","author":"EG Boman","year":"2003","unstructured":"E. G. Boman and B. Hendrickson. Support theory for preconditioning. SIAM Journal on Matrix Analysis and Applications, 25(3):694\u2013717, 2003.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"15_CR21_15","unstructured":"E. G. Boman, B. Hendrickson, S. Vavasis. Solving epplitic finite element systems in nearly-linear time with support preconditioners."},{"key":"15_CR22_15","doi-asserted-by":"crossref","unstructured":"W.\u00a0L. Briggs, V.\u00a0E. Henson, and S.\u00a0F. McCormick. A Multigrid Tutorial, 2nd Edition. SIAM, 2001.","DOI":"10.1137\/1.9780898719505"},{"key":"15_CR23_15","first-page":"107","volume":"7","author":"S Brin","year":"1998","unstructured":"S. Brin and L. Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, 107\u2013117, 1998.","journal-title":"Proceedings of the seventh international conference on World Wide Web"},{"key":"15_CR24_15","doi-asserted-by":"crossref","unstructured":"J.\u00a0Cheeger. A lower bound for smallest eigenvalue of laplacian. In Problems in Analysis, pages 195\u2013199, In R.C. Gunning editor,, Princeton University Press, 1970.","DOI":"10.1515\/9781400869312-013"},{"key":"15_CR25_15","doi-asserted-by":"crossref","unstructured":"X.\u00a0Chen, X.\u00a0Deng, and S.-H. Teng. Settling the complexity of computing two-player Nash equilibria. In J. ACM, 56(3): (2009a)","DOI":"10.1145\/1516512.1516516"},{"key":"15_CR26_15","doi-asserted-by":"crossref","unstructured":"X.\u00a0Chen, D. Dai, Y. Du, and S.-H. Teng. Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities. In IEEE FOCS, 273\u2013282, 2009b.","DOI":"10.1109\/FOCS.2009.29"},{"key":"15_CR27_15","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1145\/355483.355487","volume":"47","author":"S-W Cheng","year":"2000","unstructured":"Siu-Wing Cheng, Tamal\u00a0K. Dey, Herbert Edelsbrunner, Michael\u00a0A. Facello, and Shang-Hua Teng. Sliver exudation. Journal of ACM, 47:883\u2013904, 2000.","journal-title":"Journal of ACM"},{"key":"15_CR28_15","doi-asserted-by":"crossref","unstructured":"P\u00a0Chew. There is a planar graph almost as good as the complete graph. In SCG \u201986: Proceedings of the second annual symposium on Computational geometry, pages 169\u2013177. ACM, 1986.","DOI":"10.1145\/10515.10534"},{"key":"15_CR29_15","unstructured":"P. Christiano, J. A. Kelner, A. Madry, D. A. Spielman, and S.-H. Teng. Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs http:\/\/arxiv.org\/abs\/1010.2921."},{"key":"15_CR30_15","unstructured":"T. Cormen. C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms, 3rd edition."},{"key":"15_CR31_15","unstructured":"S.\u00a0I. Daitch and D.\u00a0A. Spielman. Support-graph preconditioners for 2-dimensional trusses."},{"key":"15_CR32_15","doi-asserted-by":"crossref","unstructured":"S.\u00a0I. Daitch and D.\u00a0A. Spielman. Faster approximate lossy generalized flow via interior point algorithms. In ACM STOC\u201908, pages 451\u2013460, 2008.","DOI":"10.1145\/1374376.1374441"},{"key":"15_CR33_15","doi-asserted-by":"crossref","unstructured":"Valentina Damerow, Friedhelm Meyer auf\u00a0der Heide, Harald R\u00e4cke, Christian Scheideler, and Christian Sohler. Smoothed motion complexity. In Proc. 11th Annual European Symposium on Algorithms (ESA\u201903), pages 161\u2013171, 2003.","DOI":"10.1007\/978-3-540-39658-1_17"},{"key":"15_CR34_15","doi-asserted-by":"crossref","unstructured":"I. Daubechies, Ten Lectures on Wavelets, Society for Industrial and Applied Mathematics, 1992","DOI":"10.1137\/1.9781611970104"},{"key":"15_CR35_15","doi-asserted-by":"crossref","unstructured":"P. Debevec, T. Hawkins, C. Tchou, H.-P. Duiker, W. Sarokin, and M. Sagar Acquiring the Reflectance Field of a Human Face SIGGRAPH Conference Proceedings, 2000","DOI":"10.1145\/344779.344855"},{"issue":"6","key":"15_CR36_15","doi-asserted-by":"crossref","first-page":"391407","DOI":"10.1002\/(SICI)1097-4571(199009)41:6<391::AID-ASI1>3.0.CO;2-9","volume":"41","author":"S. Deerwester","year":"1990","unstructured":"S. Deerwester, S. T. Dumais, G. W. Furnas, T. K. Landauer, and R. Harshman. Indexing by latent semantic analysis Journal of the American Society for Information Science, 41 (6), 391407, 1990.","journal-title":"Journal of the American Society for Information Science"},{"key":"15_CR37_15","doi-asserted-by":"crossref","unstructured":"James Demmel. Applied Numerical Linear Algebra. SIAM, 1997.","DOI":"10.1137\/1.9781611971446"},{"key":"15_CR38_15","doi-asserted-by":"crossref","unstructured":"Jian Ding, James R. Lee, and Yuval Peres. Cover times, blanket times, and majorizing measures. ACM STOC\u2019 11, 2011.","DOI":"10.1145\/1993636.1993646"},{"key":"15_CR39_15","first-page":"938","volume":"15","author":"WE Donath","year":"1972","unstructured":"W.\u00a0E. Donath and A.\u00a0J. Hoffman. Algorithms for partitioning of graphs and computer logic based on eigenvectors of connection matrices. IBM Technical Disclosure Bulletin, 15:938\u2013944, 1972.","journal-title":"IBM Technical Disclosure Bulletin"},{"issue":"4","key":"15_CR40_15","doi-asserted-by":"crossref","first-page":"12891306","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"D. L. Donoho","year":"2006","unstructured":"D. L. Donoho, Compressed Sensing, IEEE Transactions on Information Theory, 52(4), 12891306, 2006.","journal-title":"IEEE Transactions on Information Theory"},{"key":"15_CR41_15","doi-asserted-by":"crossref","unstructured":"S. Dughmi and T. Roughgarden Black-Box Randomized Reductions in Algorithmic Mechanism Design. IEEE FOCS 2010: 775\u2013784","DOI":"10.1109\/FOCS.2010.79"},{"key":"15_CR42_15","doi-asserted-by":"crossref","unstructured":"Herbert Edelsbrunner, Xiang-Yang Li, Gary Miller, Andreas Stathopoulos, Dafna Talmor, Shang-Hua Teng, Alper \u00dcng\u00f6r, and Noel Walkington. Smoothing and cleaning up slivers. In STOC \u201900, pages 273\u2013277, 2000.","DOI":"10.1145\/335305.335338"},{"issue":"2","key":"15_CR43_15","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1137\/050641661","volume":"32","author":"M Elkin","year":"2008","unstructured":"M. Elkin, Y. Emek, D.\u00a0A. Spielman, and S.-H. Teng. Lower-stretch spanning trees. SIAM Journal on Computing, 32(2):608\u2013628, 2008.","journal-title":"SIAM Journal on Computing"},{"key":"15_CR44_15","unstructured":"Matthias Englert, Heiko R\u00f6glin, and Berthold V\u00f6cking. Worst case and probabilistic analysis of the 2-opt algorithm for the tsp: extended abstract. In SIAM\/ACM SODA \u201907, pages 1295\u20131304, 2007."},{"issue":"4","key":"15_CR45_15","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1137\/0204043","volume":"4","author":"S Even","year":"1975","unstructured":"S. Even and R. E. Tarjan. Network flow and testing graph connectivity. SIAM Journal on Computing, 4(4):507\u2013518, Dec. 1975.","journal-title":"SIAM Journal on Computing"},{"issue":"98","key":"15_CR46_15","doi-asserted-by":"crossref","first-page":"298","DOI":"10.21136\/CMJ.1973.101168","volume":"23","author":"M Fiedler","year":"1973","unstructured":"M.\u00a0Fiedler. Algebraic connectibity of graphs. Czechoslovak Mathematical Journal, 23(98):298\u2013305, 1973.","journal-title":"Czechoslovak Mathematical Journal"},{"key":"15_CR47_15","doi-asserted-by":"crossref","unstructured":"A. M. Frieze, G. L. Miller, and S.-H. Teng. Separator Based Parallel Divide and Conquer in Computational Geometry. ACM SPAA 1992: 420-429","DOI":"10.1145\/140901.141934"},{"key":"15_CR48_15","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1137\/0710032","volume":"10","author":"JA George","year":"1973","unstructured":"J.\u00a0A. George. Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal., 10:345\u2013363, 1973.","journal-title":"SIAM J. Numer. Anal."},{"issue":"4","key":"15_CR49_15","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/BF01396660","volume":"50","author":"JR Gilbert","year":"1987","unstructured":"J.\u00a0R. Gilbert and R.\u00a0E. Tarjan. The analysis of a nested dissection algorithm. Numerische Mathematik, 50(4):377\u2013404, February 1987.","journal-title":"Numerische Mathematik"},{"issue":"5","key":"15_CR50_15","doi-asserted-by":"crossref","first-page":"783797","DOI":"10.1145\/290179.290181","volume":"45","author":"A. V. Goldberg","year":"1998","unstructured":"A. V. Goldberg and S. Rao. Beyond the ow decomposition barrier. J. ACM, 45(5):783797, 1998.","journal-title":"J. ACM"},{"key":"15_CR51_15","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1007\/BF01397553","volume":"53","author":"GH Golub","year":"1988","unstructured":"G.\u00a0H. Golub and M.\u00a0Overton. The convergence of inexact Chebychev and Richardson iterative methods for solving linear systems. Numerische Mathematik, 53:571\u2013594, 1988.","journal-title":"Numerische Mathematik"},{"key":"15_CR52_15","unstructured":"G.\u00a0H. Golub and C.\u00a0F.\u00a0Van Loan. Matrix Computations. second edition, 1989."},{"key":"15_CR53_15","unstructured":"K. Gremban. Combinatorial Preconditioners for Sparse, Symmetric, Diagonall\u00a0y Dominant Linear Systems. PhD thesis, Carnegie Mellon University, CMU-CS-96-123, 1996."},{"key":"15_CR54_15","doi-asserted-by":"crossref","unstructured":"A.\u00a0Gulli and A.\u00a0Signorini. The indexable web is more than 11.5 billion pages. In WWW \u201905: Special interest tracks and posters of the 14th international conference on World Wide Web, pages 902\u2013903. ACM, 2005.","DOI":"10.1145\/1062745.1062789"},{"key":"15_CR55_15","doi-asserted-by":"crossref","unstructured":"Li-Sha Huang and Shang-Hua Teng. On the approximation and smoothed complexity of leontief market equilibria. In FAW: Frontiers of Algorithms Workshop, pages 96\u2013107, 2007.","DOI":"10.1007\/978-3-540-73814-5_9"},{"key":"15_CR56_15","unstructured":"A. Joshi. Topics in Optimization and Sparse Linear Systems, Ph.D. thesis, UIUC, 1997."},{"key":"15_CR57_15","doi-asserted-by":"crossref","unstructured":"A. T. Kalai and A. Samorodnitsky and S.-H. Teng Learning and Smoothed Analysis. In IEEE FOCS\u201909, 395\u2013404, 2009.","DOI":"10.1109\/FOCS.2009.60"},{"key":"15_CR58_15","doi-asserted-by":"crossref","unstructured":"J.\u00a0A. Kelner and E.\u00a0Nikolova. On the hardness and smoothed complexity of quasi-concave minimization. In IEEE FOCS\u201907, pages 552\u2013563, 2007.","DOI":"10.1109\/FOCS.2007.68"},{"key":"15_CR59_15","doi-asserted-by":"crossref","unstructured":"J.\u00a0A. Kelner and D\u00a0A. Spielman. A randomized polynomial-time simplex algorithm for linear programming. In ACM STOC \u201906, pages 51\u201360, 2006.","DOI":"10.1145\/1132516.1132524"},{"key":"15_CR60_15","doi-asserted-by":"crossref","unstructured":"R. Khandekar, S. Rao, and U. Vazirani. Graph partitioning using single commodity flows. In ACM STOC \u201906, pages 385\u2013390, 2006.","DOI":"10.1145\/1132516.1132574"},{"issue":"5","key":"15_CR61_15","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1145\/324133.324140","volume":"46","author":"J Kleinberg","year":"1999","unstructured":"J. Kleinberg. Authoritative sources in a hyperlinked environment. J. ACM, 46 (5), 1999, 604\u2013632.","journal-title":"J. ACM"},{"key":"15_CR62_15","unstructured":"A. Kolla, Y. Makarychev, A. Saberi, and S.-H. Teng Subgraph Sparsification. ACM STOC\u201910 2010."},{"key":"15_CR63_15","unstructured":"I. Koutis. G. Miller, and R. Peng. Solving SDD linear systems in time \u00d5(mlognlog(1\u2009\/\u2009\u03b5)). arXiv:1102.4842."},{"key":"15_CR64_15","doi-asserted-by":"crossref","unstructured":"I. Koutis. G. Miller, and D. Tolliver. Combinatorial preconditioners and multilevel solvers for problems in computer vision and image prcessing. International Symp. of Visual Computing, 1067\u20131078, 2009.","DOI":"10.1007\/978-3-642-10331-5_99"},{"key":"15_CR65_15","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1287\/mnsc.11.7.681","volume":"11","author":"CE Lemke","year":"1965","unstructured":"C.E. Lemke. Bimatrix equilibrium points and mathematical programming. Management Science, 11:681\u2013689, 1965.","journal-title":"Management Science"},{"key":"15_CR66_15","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1137\/0112033","volume":"12","author":"C.E. Lemke","year":"1964","unstructured":"C.E. Lemke and JR. J.T.\u00a0Howson. Equilibrium points of bimatrix games. J. Soc. Indust. Appl. Math., 12:413\u2013423, 1964.","journal-title":"J. Soc. Indust. Appl. Math."},{"key":"15_CR67_15","unstructured":"X.-Y. Li and S.-H. Teng. Generate sliver free three dimensional meshes. In ACM-SIAM SODA\u201901, pages 28\u201337, 2001."},{"issue":"2","key":"15_CR68_15","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"RJ Lipton","year":"1979","unstructured":"R.\u00a0J. Lipton, D.\u00a0J. Rose, and R.\u00a0E. Tarjan. Generalized nested dissection. SIAM Journal on Numerical Analysis, 16(2):346\u2013358, April 1979.","journal-title":"SIAM Journal on Numerical Analysis"},{"issue":"6","key":"15_CR69_15","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"T Leighton","year":"1999","unstructured":"T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM, 46(6):787\u2013832, November 1999.","journal-title":"Journal of the ACM"},{"key":"15_CR70_15","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1002\/rsa.3240040402","volume":"4","author":"L Lovasz","year":"1993","unstructured":"L. Lovasz and M. Simonovits. Random walks in a convex body and an improved volume algorithm. RSA: Random Structures & Algorithms, 4:359\u2013412, 1993.","journal-title":"RSA: Random Structures & Algorithms"},{"key":"15_CR71_15","doi-asserted-by":"crossref","unstructured":"B. Maggs, G. Miller, O. Parekh, R. Ravi, and S. M. Woo. Finding effective support-tree preconditioners. ACM SPAA 176\u2013185, 2005.","DOI":"10.1145\/1073970.1073996"},{"key":"15_CR72_15","unstructured":"A. Madry and J. Kelner Faster generation of random spanning trees. IEEE FOCS\u201909, 2009."},{"key":"15_CR73_15","doi-asserted-by":"crossref","unstructured":"Gary\u00a0L. Miller, Dafna Talmor, Shang-Hua Teng, and Noel Walkington. A delaunay based numerical method for three dimensions: generation, formulation, and partition. In ACM STOC \u201995, pages 683\u2013692, 1995.","DOI":"10.1145\/225058.225286"},{"issue":"1","key":"15_CR74_15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/256292.256294","volume":"44","author":"GL Miller","year":"1997","unstructured":"G. L. Miller, S.-H. Teng, W. P. Thurston, and S. A. Vavasis. Separators for sphere-packings and nearest neighbor graphs. J. ACM, 44(1): 1\u201329 (1997)","journal-title":"J. ACM"},{"issue":"2","key":"15_CR75_15","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/S1064827594262613","volume":"19","author":"GL Miller","year":"1998","unstructured":"G. L. Miller, S.-H. Teng, W. P. Thurston, and S. A. Vavasis. Geometric Separators for Finite-Element Meshes. SIAM J. Scientific Computing, 19(2): 364\u2013386 (1998)","journal-title":"SIAM J. Scientific Computing"},{"key":"15_CR76_15","doi-asserted-by":"crossref","unstructured":"Joseph S.\u00a0B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric tsp, k-mst, and related problems. SIAM J. Comput., 28(4):1298\u20131309, 1999.","DOI":"10.1137\/S0097539796309764"},{"key":"15_CR77_15","unstructured":"Michael Mitzenmacher and Salil P. Vadhan. Why simple hash functions work: exploiting the entropy in a data stream. SIAM-ACM SODA 2008:746\u2013755."},{"key":"15_CR78_15","doi-asserted-by":"publisher","first-page":"289","DOI":"10.2307\/1969529","volume":"54","author":"J Nash","year":"1951","unstructured":"J.\u00a0Nash. Noncooperative games. Annals of Mathematics, 54:289\u2013295, 1951,.","journal-title":"Annals of Mathematics"},{"key":"15_CR79_15","doi-asserted-by":"crossref","unstructured":"E.\u00a0Nikolova, J.\u00a0A. Kelner, M.\u00a0Brand, and M.\u00a0Mitzenmacher. Stochastic shortest paths via quasi-convex maximization. In ESA\u201906: Proceedings of the 14th conference on Annual European Symposium, pages 552\u2013563, 2006.","DOI":"10.1007\/11841036_50"},{"key":"15_CR80_15","doi-asserted-by":"crossref","unstructured":"L. Orecchia, L.\u00a0J. Schulman, U.\u00a0V. Vazirani, and N.\u00a0K. Vishnoi. On partitioning graphs via single commodity flows. In ACM STOC \u201908, pages 461\u2013470, 2008.","DOI":"10.1145\/1374376.1374442"},{"issue":"9","key":"15_CR81_15","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0898-1221(98)00191-6","volume":"36","author":"J Rief","year":"1998","unstructured":"J. Rief. Efficient approximate solution of sparse linear systems. Computer and Mathematics with Applications, 36 (9): 37\u201358, 1998.","journal-title":"Computer and Mathematics with Applications"},{"key":"15_CR82_15","doi-asserted-by":"crossref","unstructured":"H.\u00a0R\u00f6glin and S.-H. Teng. Smoothed analysis of multiobjective optimization. IEEE FOCS, 681\u2013690, 2009.","DOI":"10.1109\/FOCS.2009.21"},{"issue":"1","key":"15_CR83_15","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s10107-006-0055-7","volume":"110","author":"H R\u00f6lin","year":"2007","unstructured":"H.\u00a0R\u00f6glin and B.\u00a0V\u00f6cking. Smoothed analysis of integer programming. Math. Program., 110(1):21\u201356, 2007.","journal-title":"Math. Program."},{"key":"15_CR84_15","unstructured":"M.\u00a0Rudelson and R.\u00a0Vershynin. The littlewood-offord problem and invertibility of random matrices. UC Davis, 2006."},{"key":"15_CR85_15","doi-asserted-by":"crossref","unstructured":"Arvind Sankar, Daniel\u00a0A. Spielman, and Shang-Hua Teng. Smoothed analysis of the condition numbers and growth factors of matrices. SIAM Journal on Matrix Analysis and Applications, to appear, 2005.","DOI":"10.1137\/S0895479803436202"},{"key":"15_CR86_15","doi-asserted-by":"crossref","unstructured":"Guido Sch\u00e4fer, Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, and Tjark Vredeveld. Average case and smoothed competitive analysis of the multi-level feedback algorithm. In IEEE FOCS \u201903, page 462, 2003.","DOI":"10.1109\/SFCS.2003.1238219"},{"key":"15_CR87_15","doi-asserted-by":"crossref","unstructured":"A. Sharma, X. Liu, P. Miller, A. Nakano, R.\u00a0K. Kalia, P. Vashishta, W. Zhao, T.\u00a0J. Campbell, and A. Haas. Immersive and interactive exploration of billion-atom systems. In VR \u201902: Proceedings of the IEEE Virtual Reality Conference 2002, page 217. IEEE Computer Society, 2002.","DOI":"10.1109\/VR.2002.996525"},{"key":"15_CR88_15","doi-asserted-by":"crossref","unstructured":"J.\u00a0R. Shewchuk. Tetrahedral mesh generation by Delaunay refinement. In Proc. 14th Annual ACM Symposium on Computational Geometry, pages 86\u201395, 1998.","DOI":"10.1145\/276884.276894"},{"issue":"1","key":"15_CR89_15","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1137\/060650295","volume":"30","author":"G Shklarski","year":"2008","unstructured":"G. Shklarski and S. Toledo. Rigidity in finite-element matrices: Sufficient conditions for the rigidity of structures and substructures. SIAM J. Matrix Anal. and Appl. 30(1): 7\u201340, 2008.","journal-title":"SIAM J. Matrix Anal. and Appl."},{"key":"15_CR90_15","unstructured":"D.\u00a0Spielman. Graphs and networks: Random walks and spectral graph drawing. Computer Science, Yale, http:\/\/www.cs.yale.edu\/homes\/spielman\/462\/lect4-07.pdf, Sept. 18, 2007."},{"key":"15_CR91_15","doi-asserted-by":"crossref","unstructured":"D. A. Spielman and N. Srivastava. Graph sparsification by effective resistances. In ACM STOC, pages 563\u2013568, 2008.","DOI":"10.1145\/1374376.1374456"},{"key":"15_CR92_15","doi-asserted-by":"crossref","unstructured":"D.\u00a0Spielman and S.-H. Teng. Spectral partitioning works: planar graphs and finite element meshes. In IEEE FOCS \u201996, pages 96\u2013105, 1996.","DOI":"10.1109\/SFCS.1996.548468"},{"key":"15_CR93_15","doi-asserted-by":"crossref","unstructured":"Daniel\u00a0A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM, 51(3):385\u2013463, 2004.","DOI":"10.1145\/990308.990310"},{"issue":"10","key":"15_CR94_15","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1145\/1562764.1562785","volume":"52","author":"DA Spielman","year":"2009","unstructured":"Daniel\u00a0A. Spielman and Shang-Hua Teng. Smoothed Analysis: An attempt to explain the behavior of algorithms in practice. CACM, 52(10):77\u201384, 2009.","journal-title":"CACM"},{"key":"15_CR95_15","doi-asserted-by":"crossref","unstructured":"D.\u00a0A. Spielman and S.-H. Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. ACM STOC, 81\u201390, 2003.","DOI":"10.1145\/1007352.1007372"},{"key":"15_CR96_15","unstructured":"D.\u00a0A. Spielman and S.-H. Teng. A local clustering algorithm for massive graphs and its application to nearly-linear time graph partitioning. CoRR, abs\/0809.3232, 2008. Available at http:\/\/arxiv.org\/abs\/0809.3232."},{"key":"15_CR97_15","unstructured":"D.\u00a0A. Spielman and S.-H. Teng. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs\/cs\/0607105, 2008. Available at http:\/\/www.arxiv.org\/abs\/cs.NA\/0607105."},{"key":"15_CR98_15","unstructured":"D.\u00a0A. Spielman and S.-H. Teng. Spectral sparsification of graphs. CoRR, abs\/0808.4134, 2008. Available at http:\/\/arxiv.org\/abs\/0808.4134."},{"key":"15_CR99_15","unstructured":"G.\u00a0Strang. Linear Algebra and its Application, 2nd. Ed. Academic Press, New York, San Francisco, London, 1980."},{"key":"15_CR100_15","unstructured":"D.\u00a0A. Tolliver. Spectral rounding and image segmentation. PhD thesis, Pittsburgh, PA, USA, 2006. Adviser-Miller,, Gary L. and Adviser-Collins,, Robert T."},{"key":"15_CR101_15","unstructured":"D.\u00a0A. Tolliver and G.\u00a0L. Miller. Graph partitioning by spectral rounding: Applications in image segmentation and clustering. In CVPR \u201906: Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 1053\u20131060. IEEE Computer Society, 2006."},{"key":"15_CR102_15","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719574","volume-title":"Numerical Linear Algebra","author":"LN Trefethen","year":"1997","unstructured":"L.\u00a0N. Trefethen and D.\u00a0Bau. Numerical Linear Algebra. SIAM, Philadelphia, PA, 1997."},{"key":"15_CR103_15","unstructured":"P. Vaidya. Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. An invited at IMA, U. Minnesota, Oct. 1991."},{"key":"15_CR104_15","doi-asserted-by":"crossref","unstructured":"R.\u00a0Vershynin. Beyond hirsch conjecture: Walks on random polytopes and smoothed complexity of the simplex method. In IEEE FOCS \u201906, pages 133\u2013142, 2006.","DOI":"10.1109\/FOCS.2006.19"},{"key":"15_CR105_15","doi-asserted-by":"crossref","unstructured":"Van\u00a0H. Vu and Terence Tao. The condition number of a randomly perturbed matrix. In ACM STOC \u201907, pages 248\u2013255, 2007.","DOI":"10.1145\/1250790.1250828"},{"key":"15_CR106_15","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1145\/321075.321076","volume":"8","author":"JH Wilkinson","year":"1961","unstructured":"J.\u00a0H. Wilkinson. Error analysis of direct methods of matrix inversion. J. Assoc. Comput. Mach., 8:261\u2013330, 1961.","journal-title":"J. Assoc. Comput. Mach."},{"key":"15_CR107_15","doi-asserted-by":"crossref","unstructured":"D. Zhou, J. Huang and B. Schlkopf. Learning from Labeled and Unlabeled Data on a Directed Graph. the 22nd International Conference on Machine Learning, 1041\u20131048. 2005.","DOI":"10.1145\/1102351.1102482"}],"container-title":["Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4614-1168-0_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,14]],"date-time":"2025-03-14T17:58:23Z","timestamp":1741975103000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-1-4614-1168-0_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9781461411673","9781461411680"],"references-count":107,"URL":"https:\/\/doi.org\/10.1007\/978-1-4614-1168-0_15","relation":{},"subject":[],"published":{"date-parts":[[2011]]},"assertion":[{"value":"22 October 2011","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}