Periodically specified problems: An exponential complexity gap between exact and approximate solutions
Description:
We study both the complexity and approximability of various graph and combinatorial problems specified using two dimensional narrow periodic specifications (see [CM93, HW92, KMW67, KO91, Or84b, Wa93]). The following two general kinds of results are presented. (1) We prove that a number of natural graph and combinatorial problems are NEXPTIME- or EXPSPACE-complete when instances are so specified; (2) In contrast, we prove that the optimization versions of several of these NEXPTIME-, EXPSPACE-com…
more
Date:
November 28, 1994
Creator:
Hunt, H. B., III; Rosenkrantz, D. J.; Stearns, R. E.; Marathe, M. V. & Radhakrishnan, V.
Item Type:
Refine your search to only
Article
Partner:
UNT Libraries Government Documents Department