• DocumentCode
    2360377
  • Title

    Weighted NP optimization problems: logical definability and approximation properties

  • Author

    Zimand, Marius

  • Author_Institution
    Dept. of Comput. Sci., Rochester Univ., NY, USA
  • fYear
    1995
  • fDate
    19-22 Jun 1995
  • Firstpage
    12
  • Lastpage
    28
  • Abstract
    It is shown that all NP-optimization problems can be characterized by Π2 first-order formulae and that Π1 formulae are not sufficient for this goal. This generalizes the result of Kolaitis and Thakur (1990). The approximation properties of the weighted versions of MAX NP, MAX SNP, MAX SNP(π), MIN F+Π1 and MIN F+Π2(1) are analyzed and dramatic changes are observed when negative weights are allowed
  • Keywords
    approximation theory; computational complexity; optimisation; approximation properties; first-order formulae; logical definability; negative weights; weighted NP optimization problems; Character generation; Computer science; Constraint optimization; Cost function; Incentive schemes; Joining processes; Law; Legal factors; Optimization methods; Polynomials;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Structure in Complexity Theory Conference, 1995., Proceedings of Tenth Annual IEEE
  • Conference_Location
    Minneapolis, MN
  • ISSN
    1063-6870
  • Print_ISBN
    0-8186-7052-5
  • Type

    conf

  • DOI
    10.1109/SCT.1995.514724
  • Filename
    514724
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2360377