Show simple item record

dc.contributor.authorBazgan, Cristina
dc.contributor.authorFernandez de la Vega, Wenceslas
dc.contributor.authorKarpinski, Marek
dc.date.accessioned2017-01-23T16:30:29Z
dc.date.available2017-01-23T16:30:29Z
dc.date.issued2003
dc.identifier.issn1042-9832
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16207
dc.language.isoenen
dc.subjectApproximation Algorithmsen
dc.subjectApproximation Ratiosen
dc.subjectPolynomial Time Approximation Schemesen
dc.subjectMinimum Constraint Satisfactionen
dc.subjectNearest Codeword Problemen
dc.subjectDense Instancesen
dc.subjectHypergraph Samplingen
dc.subject.ddc003en
dc.titlePolynomial time approximation schemes for dense instances of minimum constraint satisfactionen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIt 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.en
dc.relation.isversionofjnlnameRandom Structures and Algorithms
dc.relation.isversionofjnlvol23en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate2003
dc.relation.isversionofjnlpages73-91en
dc.relation.isversionofdoi10.1002/rsa.10072en
dc.contributor.countryeditoruniversityotherFRANCE
dc.contributor.countryeditoruniversityotherGERMANY
dc.relation.isversionofjnlpublisherWileyen
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2017-01-20T17:54:13Z
hal.person.labIds989
hal.person.labIds460398
hal.person.labIds63690
hal.identifierhal-01444205*


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record