{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:16Z","timestamp":1787337496997,"version":"build-2736575974"},"reference-count":60,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>We study the efficient approximability of basic graph and logic problems in the literature when instances are specified hierarchically as in [T. Lengauer, J. Assoc. Comput. Mach., 36(1989), pp. 474--509] or are specified by one-dimensional finite narrow periodic specifications as in [E. Wanke, Paths and cycles in finite periodic graphs, in Lecture Notes in Comp. Sci. 711, Springer-Verlag, New York, 1993, pp. 751--760]. We show that, for most of the problems $\\Pi$ considered when specified using k-level-restricted hierarchical specifications or k-narrow periodic specifications, the following hold.<\/jats:p>\n                  <jats:p>Let $\\rho$ be any performance guarantee of a polynomial time approximation algorithm for $\\Pi$, when instances are specified using standard specifications. Then $\\forall \\epsilon &gt; 0$, $ \\Pi$ has a polynomial time approximation algorithm with performance guarantee $(1 + \\epsilon) \\rho$. $\\Pi$ has a polynomial time approximation scheme when restricted to planar instances.<\/jats:p>\n                  <jats:p>These are the first polynomial time approximation schemes for PSPACE-hard hierarchically or periodically specified problems. Since several of the problems considered are PSPACE-hard, our results provide the first examples of natural PSPACE-hard optimization problems that have polynomial time approximation schemes. This answers an open question in Condon et al. [Chicago J. Theoret. Comput. Sci., 1995, Article 4].<\/jats:p>","DOI":"10.1137\/s0097539795285254","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1237-1261","source":"Crossref","is-referenced-by-count":17,"title":["Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems"],"prefix":"10.1137","volume":"27","author":[{"given":"Madhav V.","family":"Marathe","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"suffix":"III","given":"Harry B.","family":"Hunt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard E.","family":"Stearns","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Venkatesh","family":"Radhakrishnan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"S. Agarwal and A. Condon,\n                      On approximation algorithms for hierarchical MAX\u2010SAT\n                      , in Proc. 10th Annual IEEE Conference on Structure in Complexity Theory, June 1995, pp. 181\u2013190."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M Szegedy,\n                      Proof verification and hardness of approximation problems\n                      , in Proc. 33rd IEEE Symposium on Foundations of Computer Science (FOCS), 1992, pp. 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174650"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"M. Bellare, O. Goldreich, and M. Sudan,\n                      Free bits, PCPs and non\u2010approximability \u2013 towards tight results\n                      , in Proc. 36rd IEEE Symposium on Foundations of Computer Science (FOCS\u201995), Oct. 1995, pp. 422\u2013431.","DOI":"10.1109\/SFCS.1995.492573"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"J. L. Bentley, T. Ottmann and P. Widmayer,\n                      The complexity of manipulating hierarchically defined sets of rectangles\n                      , in Advances in Computing Research 1, F. P. Preparata, ed., 1983, pp. 127\u2013158.","DOI":"10.1007\/3-540-10856-4_70"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Edith Cohen, Nimrod Megiddo, Recognizing properties of periodic graphs, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 4, Amer. Math. Soc., Providence, RI, 1991, 135\u201314692g:05166","DOI":"10.1090\/dimacs\/004\/10"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/153724.153727"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"A. Condon, J. Feigenbaum, C. Lund, and P. Shor,\n                      Probabilistically checkable debate systems and approximation algorithms for PSPACE\u2010hard functions\n                      , Chicago J. Theoret. Comput. Sci., 1995, Article 4 (http:\/\/www.cs.uchicago.edu\/publications\/cjtcs\/articles\/1995\/4\/contents.html). A preliminary version of the paper appears in Proc. 25th ACM Symposium on Theory of Computing (STOC), 1993, pp. 305\u2013313.","DOI":"10.1145\/167088.167190"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793260738"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1307\/mmj\/1028998140"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80009-2"},{"key":"R12","volume-title":"Computers and intractability","author":"Garey Michael","year":"1979"},{"key":"R13","unstructured":"C. Ghezzi, M. Jazayeri, and D. Mandrioli,\n                      Fundamentals of Software Engineering\n                      , Prentice\u2010Hall, Englewood Cliffs, NJ, 1991."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"A. Habel and H. J. Kreowski,\n                      May we introduce to you: Hypergraph languages generated by hyperedge replacement\n                      , in Proc. 13th International Workshop on Graph\u2010Theoretic Concepts in Computer Science (WG\u201987), Lecture Notes in Comput. Sci. 291, Springer\u2010Verlag, New York, 1987, pp. 15\u201326.","DOI":"10.1007\/3-540-18771-5_41"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/0204019"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0060"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"Franz H\u00f6fting, Thomas Lengauer, Egon Wanke, Processing of hierarchically defined graphs and graph families, Lecture Notes in Comput. Sci., Vol. 594, Springer, Berlin, 1992, 44\u2013691249938","DOI":"10.1007\/3-540-55488-2_21"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792234378"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"H. Hunt, III, M. Marathe, V. Radhakrishnan, S. Ravi, D. Rosenkrantz, R. Stearns, A unified approach to approximation schemes for NP\u2010 and PSPACE\u2010hard problems for geometric graphs, Lecture Notes in Comput. Sci., Vol. 855, Springer, Berlin, 1994, 424\u20134351328860","DOI":"10.1007\/BFb0049428"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"H. B. Hunt III, M. V. Marathe, V. Radhakrishnan, D. J. Rosenkrantz, and R. E. Stearns,\n                      Designing approximation schemes using L\u2010reductions\n                      , in Proc. 14th Annual Foundations of Software Technology and Theoretical Computer Science (FST &TCS), Madras, India, December 1994, pp. 342\u2013353. A complete version of the paper titled\n                      Parallel Approximation Schemes for Planar and Near\u2010Planar Satisfiability and Graph Problems\n                      is available as Technical Report No. LA\u2010UR\u201096\u20102723, Los Alamos National Laboratory, Los Alamos, NM, 1996.","DOI":"10.1007\/3-540-58715-2_136"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"H. B. Hunt III, M. V. Marathe, and R. E. Stearns,\n                      Generalized CNF satisfiability problems and non\u2010efficient approximability\n                      , in Proc. 9th IEEE Conf. on Structure in Complexity Theory, 1994, pp. 356\u2013366. A detailed version of the paper appears as SUNY\u2010Albany Technical Report TR\u201095\u201027, Albany, NY, May 1995.","DOI":"10.1109\/SCT.1994.315789"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"K. Iwano and K. Steiglitz,\n                      Testing for cycles in infinite graphs with periodic structure\n                      , in Proc. 19th Annual ACM Symposium on Theory of Computing (STOC), 1987, pp. 46\u201353.","DOI":"10.1145\/28395.28401"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230180307"},{"key":"R25","unstructured":"V. Kann,\n                      On the Approximability of NP\u2010Complete Optimization Problems\n                      , Ph.D. Thesis, Dept. of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, Sweden, May 1992."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1145\/321406.321418"},{"key":"R27","unstructured":"M. Kodialam and J. B. Orlin,\n                      Recognizing strong connectivity in periodic graphs and its relation to integer programming\n                      , in Proc. 2nd ACM\u2010SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, PA, 1991, pp. 131\u2013135."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1100"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"K. R. Kosaraju and G. F. Sullivan,\n                      Detecting cycles in dynamic graphs in polynomial time\n                      , in Proc. 29th IEEE Symposium on Foundations of Computer Science (FOCS), 1988, pp. 398\u2013406.","DOI":"10.1145\/62212.62251"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"Thomas Lengauer, The complexity of compacting hierarchically specified layouts of integrated circuits, IEEE, New York, 1982, 358\u2013368780417","DOI":"10.1109\/SFCS.1982.92"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"T. Lengauer,\n                      Exploiting hierarchy in VLSI design\n                      , in Proc. AWOC \u201986, Lecture Notes in Comput. Sci. 227, Springer\u2010Verlag, New York, 1986, pp. 180\u2013193.","DOI":"10.1007\/3-540-16766-8_16"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/0217068"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1007\/BF02310101"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90042-3"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65952"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-322-92106-2"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90004-3"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1145\/151261.151268"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1137\/0211025"},{"key":"R40","first-page":"275","volume":"1","author":"Marathe Madhav","year":"1994","journal-title":"Nordic J. Comput."},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00008-4"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"M. V. Marathe, H. B. Hunt III, R. E. Stearns, and V. Radhakrishnan,\n                      Approximation schemes for PSPACE\u2010complete problems for succinct specifications\n                      , in Proc. 26th Annual ACM Symposium on Theory of Computing (STOC), 1994, pp. 468\u2013477.","DOI":"10.1145\/195058.195233"},{"key":"R43","unstructured":"M. V. Marathe,\n                      Complexity and Approximability of NP\u2010 and PSPACE\u2010Hard Optimization Problems\n                      , Ph.D. Thesis, Department of Computer Science, SUNY\u2010Albany, Albany, NY, August 1994."},{"key":"R44","doi-asserted-by":"crossref","unstructured":"Madhav Marathe, Harry Hunt, III, Richard Stearns, Venkatesh Radhakrishnan, Complexity of hierarchically and 1\u2010dimensional periodically specified problems. I. Hardness results, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 35, Amer. Math. Soc., Providence, RI, 1997, 225\u201325999c:68129","DOI":"10.1090\/dimacs\/035\/05"},{"key":"R45","unstructured":"M. V. Marathe, H. B. Hunt III, D. E. Rosenkrantz, and R. E. Stearns,\n                      Theory of Periodically Specified Problems: Complexity & Approximability\n                      , Tech. Report LA\u2010UR\u201096\u20101466, Los Alamos National Laboratory, Los Alamos, NM, 1996."},{"key":"R46","unstructured":"J. O. McClain, L. J. Thomas, and J. B. Mazzola,\n                      Operations Management\n                      , Prentice\u2010Hall, Englewood Cliffs, NJ, 1992."},{"key":"R47","unstructured":"C. Mead and L. Conway,\n                      Introduction to VLSI Systems\n                      , Addison\u2010Wesley, Reading, MA, 1980."},{"key":"R48","doi-asserted-by":"crossref","unstructured":"J. B. Orlin,\n                      The Complexity of Dynamic\/Periodic Languages and Optimization Problems\n                      , Sloan Working Paper No. 1679\u201086, July 1985, Alfred P. Sloan School of Management, MIT, Cambridge, MA. A Preliminary version of the paper appears in Proc. 13th Annual ACM Symposium on Theory of Computing (STOC), 1981, pp. 218\u2013227.","DOI":"10.1145\/800076.802475"},{"key":"R49","doi-asserted-by":"publisher","DOI":"10.1287\/moor.9.2.190"},{"key":"R50","doi-asserted-by":"crossref","unstructured":"James Orlin, Some problems on dynamic\/periodic graphs, Academic Press, Toronto, ON, 1984, 273\u201329386m:90058","DOI":"10.1016\/B978-0-12-566780-7.50022-2"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90259-V"},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80009-2"},{"key":"R53","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"R54","unstructured":"C. Papadimitriou,\n                      Computational Complexity\n                      , Addison\u2010Wesley, Reading, MA, 1994."},{"key":"R55","doi-asserted-by":"publisher","DOI":"10.1137\/0222042"},{"key":"R56","doi-asserted-by":"crossref","unstructured":"Thomas Schaefer, The complexity of satisfiability problems, ACM, New York, 1978, 216\u201322680d:68058","DOI":"10.1145\/800133.804350"},{"key":"R57","doi-asserted-by":"crossref","unstructured":"K. Wagner, The complexity of problems concerning graphs with regularities, Lecture Notes in Comput. Sci., Vol. 176, Springer, Berlin, 1984, 544\u2013552783486","DOI":"10.1007\/BFb0030338"},{"key":"R58","doi-asserted-by":"crossref","unstructured":"Egon Wanke, Paths and cycles in finite periodic graphs, Lecture Notes in Comput. Sci., Vol. 711, Springer, Berlin, 1993, 751\u201376095c:05077","DOI":"10.1007\/3-540-57182-5_66"},{"key":"R59","unstructured":"M. Williams,\n                      Efficient Processing of Hierarchical Graphs\n                      , Tech. Report 90\u201006, Dept. of Computer Science, Iowa Sate University, Ames, IA. (Parts of the report appeared in WADS\u201989, pp. 563\u2013576 and SWAT\u201990, pp. 320\u2013331 coauthored with Fernandez\u2010Baca.)"},{"key":"R60","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1045"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539795285254","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:06Z","timestamp":1787336046000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795285254"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":60,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539795285254"],"URL":"https:\/\/doi.org\/10.1137\/s0097539795285254","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}