2 Matching Results

Search Results

Advanced search parameters have been applied.

in creator/contributor: "Hunt, H. B."

open access

Periodically specified problems: An exponential complexity gap between exact and approximate solutions

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: Article

Partner: UNT Libraries Government Documents Department

open access

Bicriteria network design problems

We study several bicriteria network design problems phrased as follows: given an undirected graph and two minimization objectives with a budget specified on one objective, find a subgraph satisfying certain connectivity requirements that minimizes the second objective subject to the budget on the first. Define an ({alpha}, {beta})-approximation algorithm as a polynomial-time algorithm that produces a solution in which the first objective value is at most {alpha} times the budget, and the second… more

Date: December 31, 1994

Creator: Marathe, M. V.; Ravi, R.; Sundaram, R.; Ravi, S. S.; Rosenkrantz, D. J. & Hunt, H. B., III