{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T23:16:05Z","timestamp":1761952565936,"version":"build-2065373602"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2008,5,21]],"date-time":"2008-05-21T00:00:00Z","timestamp":1211328000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,4]]},"DOI":"10.1007\/s00453-008-9191-1","type":"journal-article","created":{"date-parts":[[2008,5,20]],"date-time":"2008-05-20T20:11:52Z","timestamp":1211314312000},"page":"577-604","source":"Crossref","is-referenced-by-count":21,"title":["\u2113 2 2 Spreading Metrics for Vertex Ordering Problems"],"prefix":"10.1007","volume":"56","author":[{"given":"Moses","family":"Charikar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad Taghi","family":"Hajiaghayi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Howard","family":"Karloff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Satish","family":"Rao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,5,21]]},"reference":[{"key":"9191_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, A., Charikar, M., Makarychev, K., Makarychev, Y.: $O(\\sqrt{\\log n})$ -approximation algorithms for Min Uncut, Min 2CNF deletion and directed cut problems. In: Proc. of 37th STOC, pp. 573\u2013581 (2005)","DOI":"10.1145\/1060590.1060675"},{"issue":"1","key":"9191_CR2","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1137\/0805002","volume":"5","author":"F. Alizadeh","year":"1995","unstructured":"Alizadeh, F.: Interior-point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5(1), 13\u201351 (1995)","journal-title":"SIAM J. Optim."},{"key":"9191_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Lee, J.R., Naor, A.: Euclidean distortion and the sparsest cut. In: Proc. of 37th STOC, pp. 553\u2013562 (2005)","DOI":"10.1145\/1060590.1060673"},{"key":"9191_CR4","doi-asserted-by":"crossref","unstructured":"Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings, and graph partitioning. In: Proc. of 36th STOC, pp. 222\u2013231 (2004); full version available at http:\/\/www.cs.princeton.edu\/~arora\/pubs\/arvfull.pdf","DOI":"10.1145\/1007352.1007355"},{"issue":"1","key":"9191_CR5","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1137\/S0097539794285983","volume":"27","author":"Y. Aumann","year":"1998","unstructured":"Aumann, Y., Rabani, Y.: An O(log\u2009k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput. 27(1), 291\u2013301 (1998)","journal-title":"SIAM J. Comput."},{"key":"9191_CR6","doi-asserted-by":"crossref","unstructured":"B\u0103doiu, M., Chuzhoy, J., Indyk, P., Sidiropoulos, A.: Low-distortion embeddings of general metrics into the line. In: Proceedings of 37th STOC, pp. 225\u2013233 (2005)","DOI":"10.1145\/1060590.1060624"},{"key":"9191_CR7","doi-asserted-by":"crossref","unstructured":"B\u0103doiu, M., Demaine, E., Hajiaghayi, M., Indyk, P.: Low-dimensional embedding with extra information. In: Symposium on Computational Geometry, pp. 320\u2013329 (2004); to appear in Discrete Comput. Geom.","DOI":"10.1145\/997817.997866"},{"key":"9191_CR8","unstructured":"B\u0103doiu, M., Dhamdhere, K., Gupta, A., Rabinovich, Y., R\u00e4cke, H., Ravi, R., Sidiropoulos, A.: Approximation algorithms for low-distortion embeddings into low-dimensional spaces. In: Proc. of 16th SODA, pp. 119\u2013128 (2005)"},{"issue":"2","key":"9191_CR9","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","volume":"28","author":"S. Bhatt","year":"1984","unstructured":"Bhatt, S., Leighton, F.T.: A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci. 28(2), 300\u2013343 (1984)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20132","key":"9191_CR10","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1007\/BF02776078","volume":"52","author":"J. Bourgain","year":"1985","unstructured":"Bourgain, J.: On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math. 52(1\u20132), 46\u201352 (1985)","journal-title":"Israel J. Math."},{"key":"9191_CR11","unstructured":"Chawla, S., Gupta, A., R\u00e4cke, H.: Embeddings of negative-type metrics and improved approximations to Sparsest Cut. In: Proc. of 16th SODA, pp. 102\u2013111 (2005)"},{"key":"9191_CR12","doi-asserted-by":"crossref","unstructured":"Devanur, N., Khot, S., Saket, R., Vishnoi, N.: Integrality gaps for sparsest cut and minimum linear arrangement problems. In: Proc. of 38th STOC, pp. 537\u2013546 (2006)","DOI":"10.1145\/1132516.1132594"},{"issue":"6","key":"9191_CR13","doi-asserted-by":"crossref","first-page":"2187","DOI":"10.1137\/S0097539796308217","volume":"28","author":"G. Even","year":"1999","unstructured":"Even, G., Naor, J., Rao, S., Schieber, B.: Fast approximate graph partitioning algorithms. SIAM J. Comput. 28(6), 2187\u20132214 (1999)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9191_CR14","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1145\/347476.347478","volume":"47","author":"G. Even","year":"2000","unstructured":"Even, G., Naor, S., Rao, S., Schieber, B.: Divide-and-conquer approximation algorithms via spreading metrics. J. Assoc. Comput. Mach. 47(4), 585\u2013616 (2000)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"2","key":"9191_CR15","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/PL00009191","volume":"20","author":"G. Even","year":"1998","unstructured":"Even, G., Naor, J., Schieber, B., Sudan, M.: Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20(2), 151\u2013174 (1998)","journal-title":"Algorithmica"},{"key":"9191_CR16","doi-asserted-by":"crossref","unstructured":"Feige, U., Hajiaghayi, M.T., Lee, J.R.: Improved approximation algorithms for minimum-weight vertex separators. In: Proceedings of 37th STOC, pp. 563\u2013572 (2005)","DOI":"10.1145\/1060590.1060674"},{"issue":"1","key":"9191_CR17","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1016\/j.ipl.2006.07.009","volume":"101","author":"U. Feige","year":"2007","unstructured":"Feige, U., Lee, J.R.: An improved approximation ratio for the minimum linear arrangement problem. Inf. Process. Lett. 101(1), 26\u201329 (2007)","journal-title":"Inf. Process. Lett."},{"key":"9191_CR18","doi-asserted-by":"crossref","unstructured":"Hansen, M.: Approximation algorithms for geometric embeddings in the plane with applications to parallel processing problems. In: Proc. of 30th FOCS, pp. 604\u2013609 (1989)","DOI":"10.1109\/SFCS.1989.63542"},{"key":"9191_CR19","doi-asserted-by":"crossref","unstructured":"Khot, S., Vishnoi, N.: The unique games conjecture, integrality gap for cut problems, and embeddability of negative-type metrics into \u2113 1. In: Proc. of 46th FOCS, pp. 53\u201362 (2005)","DOI":"10.1109\/SFCS.2005.74"},{"key":"9191_CR20","doi-asserted-by":"crossref","unstructured":"Krauthgamer, R., Lee, J.R., Mendel, M., Naor, A.: Measured descent: A new embedding method for finite metrics. In: Proc. of 45th FOCS, pp. 434\u2013443 (2004)","DOI":"10.1109\/FOCS.2004.41"},{"key":"9191_CR21","unstructured":"Lee, J.: On distance scales, embeddings, and efficient relaxations of the cut cone. In: Proc. of 16th SODA, pp. 92\u2013101 (2005)"},{"key":"9191_CR22","volume-title":"Complexity Issues in VLSI: Optimal Layout for the Shuffle-Exchange Graph and Other Networks","author":"F.T. Leighton","year":"1983","unstructured":"Leighton, F.T.: Complexity Issues in VLSI: Optimal Layout for the Shuffle-Exchange Graph and Other Networks. MIT Press, Cambridge (1983)"},{"issue":"6","key":"9191_CR23","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"F.T. Leighton","year":"1999","unstructured":"Leighton, F.T., Rao, S.: Multi-commodity max-flow min-cut theorems and their use in designing approximation algorithms. J. Assoc. Comput. Mach. 46(6), 787\u2013832 (1999)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9191_CR24","doi-asserted-by":"crossref","unstructured":"Leiserson, C.E.: Area-efficient graph layouts (for VLSI). In: Proc. of 21st FOCS, pp. 270\u2013280 (1980)","DOI":"10.1109\/SFCS.1980.13"},{"issue":"2","key":"9191_CR25","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01200757","volume":"15","author":"N. Linial","year":"1995","unstructured":"Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2), 215\u2013245 (1995)","journal-title":"Combinatorica"},{"issue":"3","key":"9191_CR26","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.J. Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"key":"9191_CR27","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0020-0190(88)90091-9","volume":"27","author":"G. Ramalingam","year":"1988","unstructured":"Ramalingam, G., Pandu Rangan, C.: A unified approach to domination problems on interval graphs. Inf. Process. Lett. 27, 271\u2013274 (1988)","journal-title":"Inf. Process. Lett."},{"key":"9191_CR28","unstructured":"Rao, S., Richa, A.: New approximation techniques for some ordering problems. In: Proc. of 9th SODA, pp. 211\u2013218 (1998)"},{"key":"9191_CR29","doi-asserted-by":"crossref","unstructured":"Ravi, R., Agrawal, A., Klein, P.: Ordering problems approximated: single-processor scheduling and interval graph completion. In: Proc. of 18th ICALP, pp. 751\u2013762 (1991)","DOI":"10.1007\/3-540-54233-7_180"},{"issue":"2","key":"9191_CR30","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF01200760","volume":"15","author":"P.D. Seymour","year":"1995","unstructured":"Seymour, P.D.: Packing directed circuits fractionally. Combinatorica 15(2), 281\u2013288 (1995)","journal-title":"Combinatorica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9191-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9191-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9191-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:02Z","timestamp":1559137502000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9191-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5,21]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,4]]}},"alternative-id":["9191"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9191-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2008,5,21]]}}}