• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Polynomial time approximation schemes for dense instances of minimum constraint satisfaction

Thumbnail
View/Open
RSA03.pdf (193.5Kb)
Date
2003
Dewey
Recherche opérationnelle
Sujet
Approximation Algorithms; Approximation Ratios; Polynomial Time Approximation Schemes; Minimum Constraint Satisfaction; Nearest Codeword Problem; Dense Instances; Hypergraph Sampling
Journal issue
Random Structures and Algorithms
Volume
23
Number
1
Publication date
2003
Article pages
73-91
Publisher
Wiley
DOI
http://dx.doi.org/10.1002/rsa.10072
URI
https://basepub.dauphine.fr/handle/123456789/16207
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Bazgan, Cristina
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Fernandez de la Vega, Wenceslas
status unknown
Karpinski, Marek
status unknown
Type
Article accepté pour publication ou publié
Abstract (EN)
It is known that large fragments of the class of dense Minimum Constraint Satisfaction (MIN-CSP) problems do not have polynomial time approximation schemes (PTASs) contrary to their Maximum Constraint Satisfaction analogs. In this paper we prove, somewhat surprisingly, that the minimum satisfaction of dense instances of kSAT-formulas, and linear equations mod 2, Ek-LIN2, do have PTASs for any k. The MIN-Ek-LIN2 problems are equivalent to the k-ary versions of the Nearest Codeword problem, the problem which is known to be exceedingly hard to approximate on general instances. The method of solution of the above problems depends on the development of a new density sampling technique for k-uniform hypergraphs which could be of independent interest.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.