Integer Programming as a Framework for Optimization and Approximability

Authors: Barland I.1; Kolaitis P.G.2; Thakur M.N.3

Source: Journal of Computer and System Sciences, Volume 57, Number 2, October 1998 , pp. 144-161(18)

Publisher: Academic Press

Key:
Free Content - Free Content
New Content - New Content
Subscribed Content - Subscribed Content
Free Trial Content - Free Trial Content

Abstract:

Structural approximation theory seeks to provide a framework for expressing optimization problems and isolating structural or syntactic conditions that explain the apparent difference in the approximation properties of different NP-optimization problems. In this paper, we initiate a study of structural approximation using integer programming (an optimization problem in its own right) as a general framework for expressing optimization problems. We isolate three classes of constant-approximable maximization problems, based on restricting appropriately the syntactic form of the integer programs expressing them. The first of these classes subsumes Max Sigma1, which is the syntactic version of the well-studied class Max NP. Moreover, by allowing variables to take on not just 0/1 values but rather values in a polylogarithmic or polynomial range, we obtain syntactic maximization classes that are polylog-approximable and poly-approximable, respectively. The other two classes contain problems, such as Max Matching, for which no previous structural explanation of approximability has been found. We also investigate structurally defined classes of integer programs for minimization problems and show a difference between their maximization counterparts. Copyright 1998 Academic Press.

Language: English

Document Type: Research article

Affiliations: 1: Computer Science Department, Rice University, Houston, Texas, 77005-1892 2: Computer Science Department, University of California, Santa Cruz, California, 95064 3: Interbase Software Corporation, 1800 Green Hills Rd, Suite 150, Scotts Valley, California, 95066

The full text electronic article is available for purchase. You will be able to download the full text electronic article after payment.

$54.38 plus tax      Refund Policy

 

OR

Back to top

Key:
Free Content - Free Content
New Content - New Content
Subscribed Content - Subscribed Content
Free Trial Content - Free Trial Content
Share this item with others: These icons link to social bookmarking sites where readers can share and discover new web pages.
Page Help Click here for Page Help
Shopping cart
Tools
Sign in






Need to register?
Sign up here
Text size: A | A | A | A