{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,10]],"date-time":"2023-01-10T08:31:01Z","timestamp":1673339461042},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2000,7]]},"abstract":"\n We present a novel divide-and-conquer paradigm for approximating NP-hard graph optimization problems. The paradigm models graph optimization problems that satisfy two properties: First, a divide-and-conquer approach is applicable. Second, a fractional spreading metric is computable in polynomial time. The spreading metric assigns lengths to either edges or vertices of the input graph, such that all subgraphs for which the optimization problem is nontrivial have large diameters. In addition, the spreading metric provides a lower bound, \u03c4, on the cost of solving the optimization problem. We present a polynomial time approximation algorithm for problems modeled by our paradigm whose approximation factor is\n O<\/jats:italic>\n (min{log \u03c4, log log \u03c4, log\n k<\/jats:italic>\n log log\n k<\/jats:italic>\n }) where\n k<\/jats:italic>\n denotes the number of \u201cinteresting\u201d vertices in the problem instance, and is at most the number of vertices.\n <\/jats:p>\n \n We present seven problems that can be formulated to fit the paradigm. For all these problems our algorithm improves previous results. The problems are: (1) linear arrangement; (2) embedding a graph in a\n d<\/jats:italic>\n -dimensional mesh; (3) interval graph completion; (4) minimizing storage-time product; (5) subset feedback sets in directed graphs and multicuts in circular networks; (6) symmetric multicuts in directed networks; (7) balanced partitions and\n p<\/jats:italic>\n -separators (for small values of\n p<\/jats:italic>\n ) in directed graphs.\n <\/jats:p>","DOI":"10.1145\/347476.347478","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:26:13Z","timestamp":1027769173000},"page":"585-616","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":72,"title":["Divide-and-conquer approximation algorithms via spreading metrics"],"prefix":"10.1145","volume":"47","author":[{"given":"Guy","family":"Even","sequence":"first","affiliation":[{"name":"Tel-Aviv Univ., Tel-Aviv, Israel"}]},{"given":"Joseph Seffi","family":"Naor","sequence":"additional","affiliation":[{"name":"Technion\u2013Israel Institute of Technology, Haifa, Israel"}]},{"given":"Satish","family":"Rao","sequence":"additional","affiliation":[{"name":"Univ. of California, Berkeley"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[{"name":"IBM T. J. Watson Research Center, Yorktown Heights, NY"}]}],"member":"320","published-online":{"date-parts":[[2000,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794285983"},{"key":"e_1_2_1_2_1","unstructured":"BAR-YEHUDA R. EVEN G. AND NAOR J. 1998. Computing an optimal orientation of a balanced decomposition tree for linear arrangement problems. Manuscript. BAR-YEHUDA R. EVEN G. AND NAOR J. 1998. Computing an optimal orientation of a balanced decomposition tree for linear arrangement problems. Manuscript."},{"key":"e_1_2_1_3_1","first-page":"100","volume-title":"Proceedings of the 30th ACM Symposium on Theory of Computing. ACM","author":"BLUM A.","year":"1998","unstructured":"BLUM , A. , KONJEVOD , G. , RAVI , R. , AND VEMPALA , S. 1998 . Semi-definite relaxations for minimum bandwidth and other vertex ordering problems . In Proceedings of the 30th ACM Symposium on Theory of Computing. ACM , New York , pp. 100 - 105 . 10.1145\/276698.276717 BLUM, A., KONJEVOD, G., RAVI, R., AND VEMPALA, S. 1998. Semi-definite relaxations for minimum bandwidth and other vertex ordering problems. In Proceedings of the 30th ACM Symposium on Theory of Computing. ACM, New York, pp. 100-105. 10.1145\/276698.276717"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","article-title":"A framework for solving VLSI graph layout problems","volume":"28","author":"BHATT S. N.","year":"1984","unstructured":"BHATT , S. N. , AND LEIGHTON , F.T. 1984 . A framework for solving VLSI graph layout problems . J. Comput. Syst. Sci. 28 , 300 - 343 . BHATT, S. N., AND LEIGHTON, F.T. 1984. A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci. 28, 300-343.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_5_1","first-page":"62","volume-title":"Proceedings of the 35th IEEE Symposium on Foundations of Computer Science. IEEE Computer Science Press, Los Alamitos, Calif.","author":"EVEN G.","year":"1998","unstructured":"EVEN , G. , NAOR , J. , RAO , S. , AND SCHIEBER , B. 1998 . Divide-and-conquer approximation algorithms via spreading metrics . In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science. IEEE Computer Science Press, Los Alamitos, Calif. , pp. 62 - 71 . EVEN, G., NAOR, J., RAO, S., AND SCHIEBER, B. 1998. Divide-and-conquer approximation algorithms via spreading metrics. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science. IEEE Computer Science Press, Los Alamitos, Calif., pp. 62-71."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796308217"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/PL00009191","article-title":"Approximating minimum feedback sets and multicuts in directed graphs","volume":"20","author":"EVEN G.","year":"1998","unstructured":"EVEN , G. , NAOR , J. , SCHIEBER , B. , AND SUDAN , M. 1998 . Approximating minimum feedback sets and multicuts in directed graphs . Algorithmica 20 , 151 - 174 . EVEN, G., NAOR, J., SCHIEBER, B., AND SUDAN, M. 1998. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20, 151-174.","journal-title":"Algorithmica"},{"key":"e_1_2_1_8_1","first-page":"90","volume-title":"Proceedings of the 30th ACM Symposium on Theory of Computing. ACM","author":"FEIGE U.","year":"1998","unstructured":"FEIGE , U. 1998 . Approximating the bandwidth via volume respecting embeddings . In Proceedings of the 30th ACM Symposium on Theory of Computing. ACM , New York , pp. 90 - 99 . 10.1145\/276698.276716 FEIGE, U. 1998. Approximating the bandwidth via volume respecting embeddings. In Proceedings of the 30th ACM Symposium on Theory of Computing. ACM, New York, pp. 90-99. 10.1145\/276698.276716"},{"key":"e_1_2_1_9_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"GAREY M. R.","unstructured":"GAREY , M. R. , AND JOHNSON , D.S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman , San Francisco , Calif. GAREY, M. R., AND JOHNSON, D.S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, Calif."},{"key":"e_1_2_1_10_1","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"GROTSCHEL M.","unstructured":"GROTSCHEL , M. , LOVASZ , L. , AND SCHRIJVER , A. 1988. Geometric Algorithms and Combinatorial Optimization . Springer-Verlag , New York . GROTSCHEL, M., LOVASZ, L., AND SCHRIJVER, A. 1988. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, New York."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793243016"},{"key":"e_1_2_1_12_1","first-page":"604","volume-title":"Proceedings of the 30th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif.","author":"HANSEN M.","year":"1989","unstructured":"HANSEN , M. 1989 . Approximation algorithms for geometric embeddings in the plane with applications to parallel processing problems . In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. , pp. 604 - 609 . HANSEN, M. 1989. Approximation algorithms for geometric embeddings in the plane with applications to parallel processing problems. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 604-609."},{"key":"e_1_2_1_13_1","first-page":"512","volume-title":"Proceedings of the 34th ACM-IEEE Design Automation Conference (Anaheim, Calif., June 9-11)","author":"CHENG C.-K.","year":"1997","unstructured":"Kuo, M.-T., AND CHENG , C.-K. 1997 . A network flow approach for hierarchical tree partitioning . In Proceedings of the 34th ACM-IEEE Design Automation Conference (Anaheim, Calif., June 9-11) . ACM, New York , pp. 512 - 517 . 10.1145\/266021.266269 Kuo, M.-T., AND CHENG, C.-K. 1997. A network flow approach for hierarchical tree partitioning. In Proceedings of the 34th ACM-IEEE Design Automation Conference (Anaheim, Calif., June 9-11). ACM, New York, pp. 512-517. 10.1145\/266021.266269"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0833"},{"key":"e_1_2_1_15_1","first-page":"2866","volume-title":"Proceedings of the IEEE International Symposium on Circuits and Systems. IEEE Computer Society Press, Los Alamitos, Calif.","author":"LEIGHTON F. T.","year":"1990","unstructured":"LEIGHTON , F. T. , MAKEDON , F. , AND TRAGOUDAS , S. 1990 . Approximation algorithms for VLSI partition problems . In Proceedings of the IEEE International Symposium on Circuits and Systems. IEEE Computer Society Press, Los Alamitos, Calif. pp. 2866 - 2868 . LEIGHTON, F. T., MAKEDON, F., AND TRAGOUDAS, S. 1990. Approximation algorithms for VLSI partition problems. In Proceedings of the IEEE International Symposium on Circuits and Systems. IEEE Computer Society Press, Los Alamitos, Calif. pp. 2866-2868."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01200757","article-title":"The geometry of graphs and some of its algorithmic applications","volume":"15","author":"LINIAL N.","year":"1995","unstructured":"LINIAL , N. , LONDON , E. , AND RABINOVICH , Y. 1995 . The geometry of graphs and some of its algorithmic applications . Combinatorica 15 , 215 - 245 . LINIAL, N., LONDON, E., AND RABINOVICH, Y. 1995. The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 215-245.","journal-title":"Combinatorica"},{"key":"e_1_2_1_18_1","volume-title":"Interior-Point Polynomial Algorithms in Convex Programming","author":"NESTEROV Y.","unstructured":"NESTEROV , Y. , AND NEMIROVSKII , A. 1994. Interior-Point Polynomial Algorithms in Convex Programming . SIAM , Philadelphia . NESTEROV, Y., AND NEMIROVSKII, A. 1994. Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"751","DOI":"10.1007\/3-540-54233-7_180","volume-title":"Proceedings of the 18th International Colloquium on Automata, Languages and Programming.","author":"RAVI R.","year":"1991","unstructured":"RAVI , R. , AGRAWAL , A. , AND KLEIN , P. 1991 . Ordering problems approximated: Single processor scheduling and interval graph completion . In Proceedings of the 18th International Colloquium on Automata, Languages and Programming. pp. 751 - 762 . RAVI, R., AGRAWAL, A., AND KLEIN, P. 1991. Ordering problems approximated: Single processor scheduling and interval graph completion. In Proceedings of the 18th International Colloquium on Automata, Languages and Programming. pp. 751-762."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90091-9"},{"key":"e_1_2_1_21_1","first-page":"211","volume-title":"Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"RAO S.","year":"1998","unstructured":"RAO , S. , AND RICHA , A. 1998 . New approximation techniques for some ordering problems . In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms. ACM , New York , pp. 211 - 219 . RAO, S., AND RICHA, A. 1998. New approximation techniques for some ordering problems. In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 211-219."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"SAGAN H. 1994. Space-Filling Curves. Springer-Verlag New York. SAGAN H. 1994. Space-Filling Curves. Springer-Verlag New York.","DOI":"10.1007\/978-1-4612-0871-6"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF01200760","article-title":"Packing directed circuits fractionally","volume":"15","author":"SEYMOUR P.D.","year":"1995","unstructured":"SEYMOUR , P.D. 1995 . Packing directed circuits fractionally . Combinatorica 15 , 281 - 288 . SEYMOUR, P.D. 1995. Packing directed circuits fractionally. Combinatorica 15, 281-288.","journal-title":"Combinatorica"},{"key":"e_1_2_1_24_1","volume-title":"Approximation algorithms for NP-hard problems","author":"HMOYS D.B.","unstructured":"HMOYS , D.B. 1997. Cut problems and their application to divide-and-conquer . In Approximation algorithms for NP-hard problems . D. S. Hochbaum, Ed. PWS Publishing Co . HMOYS, D.B. 1997. Cut problems and their application to divide-and-conquer. In Approximation algorithms for NP-hard problems. D. S. Hochbaum, Ed. PWS Publishing Co."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827593255135"},{"key":"e_1_2_1_26_1","first-page":"389","volume-title":"Proceedings of the 39th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif.","author":"VEMPALA S.","year":"1998","unstructured":"VEMPALA , S. 1998 . Random projection: A new approach to VLSI layout . In Proceedings of the 39th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. , pp. 389 - 395 . VEMPALA, S. 1998. Random projection: A new approach to VLSI layout. In Proceedings of the 39th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 389-395."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/347476.347478","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T23:36:03Z","timestamp":1672616163000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/347476.347478"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,7]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2000,7]]}},"alternative-id":["10.1145\/347476.347478"],"URL":"http:\/\/dx.doi.org\/10.1145\/347476.347478","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2000,7]]},"assertion":[{"value":"2000-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}