A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
Identifieur interne : 001175 ( Main/Curation ); précédent : 001174; suivant : 001176A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
Auteurs : Daniel Raible [Allemagne] ; Henning Fernau [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2008.
Abstract
Abstract: In MaxSat, we ask for an assignment which satisfies the maximum number of clauses for a boolean formula in CNF. We present an algorithm yielding a run time upper bound of ${\mathcal{O}}^*({2^{\frac{K}{6.2158}}})$ for Max-2-Sat (each clause contains at most 2 literals), where K is the number of clauses. The run time has been achieved by using heuristic priorities on the choice of the variable on which we branch. The implementation of these heuristic priorities is rather simple, though they have a significant effect on the run time. Also the analysis uses a non-standard measure.
Url:
DOI: 10.1007/978-3-540-85238-4_45
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :001842
- to stream Istex, to step Curation: Pour aller vers cette notice dans l'étape Curation :001726
- to stream Istex, to step Checkpoint: Pour aller vers cette notice dans l'étape Curation :000589
- to stream Main, to step Merge: Pour aller vers cette notice dans l'étape Curation :001277
Links to Exploration step
ISTEX:9C5537D0EC1486E53D2B4631D5B9DE8D69231B2DLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach</title>
<author><name sortKey="Raible, Daniel" sort="Raible, Daniel" uniqKey="Raible D" first="Daniel" last="Raible">Daniel Raible</name>
</author>
<author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name>
<affiliation><country>Allemagne</country>
<placeName><settlement type="city">Trèves (Allemagne)</settlement>
<region type="land" nuts="1">Rhénanie-Palatinat</region>
</placeName>
<orgName type="university">Université de Trèves</orgName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:9C5537D0EC1486E53D2B4631D5B9DE8D69231B2D</idno>
<date when="2008" year="2008">2008</date>
<idno type="doi">10.1007/978-3-540-85238-4_45</idno>
<idno type="url">https://api.istex.fr/document/9C5537D0EC1486E53D2B4631D5B9DE8D69231B2D/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001842</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001842</idno>
<idno type="wicri:Area/Istex/Curation">001726</idno>
<idno type="wicri:Area/Istex/Checkpoint">000589</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000589</idno>
<idno type="wicri:doubleKey">0302-9743:2008:Raible D:a:new:upper</idno>
<idno type="wicri:Area/Main/Merge">001277</idno>
<idno type="wicri:Area/Main/Curation">001175</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach</title>
<author><name sortKey="Raible, Daniel" sort="Raible, Daniel" uniqKey="Raible D" first="Daniel" last="Raible">Daniel Raible</name>
<affiliation wicri:level="4"><country xml:lang="fr">Allemagne</country>
<wicri:regionArea>University of Trier, FB 4—Abteilung Informatik, 54286, Trier</wicri:regionArea>
<orgName type="university">Université de Trèves</orgName>
<placeName><settlement type="city">Trèves (Allemagne)</settlement>
<region type="land" nuts="1">Rhénanie-Palatinat</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name>
<affiliation wicri:level="4"><country xml:lang="fr">Allemagne</country>
<wicri:regionArea>University of Trier, FB 4—Abteilung Informatik, 54286, Trier</wicri:regionArea>
<orgName type="university">Université de Trèves</orgName>
<placeName><settlement type="city">Trèves (Allemagne)</settlement>
<region type="land" nuts="1">Rhénanie-Palatinat</region>
</placeName>
<placeName><settlement type="city">Trèves (Allemagne)</settlement>
<region type="land" nuts="1">Rhénanie-Palatinat</region>
</placeName>
<orgName type="university">Université de Trèves</orgName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country>
<placeName><settlement type="city">Trèves (Allemagne)</settlement>
<region type="land" nuts="1">Rhénanie-Palatinat</region>
</placeName>
<orgName type="university">Université de Trèves</orgName>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s">Lecture Notes in Computer Science</title>
<imprint><date>2008</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
<idno type="istex">9C5537D0EC1486E53D2B4631D5B9DE8D69231B2D</idno>
<idno type="DOI">10.1007/978-3-540-85238-4_45</idno>
<idno type="ChapterID">45</idno>
<idno type="ChapterID">Chap45</idno>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass></textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: In MaxSat, we ask for an assignment which satisfies the maximum number of clauses for a boolean formula in CNF. We present an algorithm yielding a run time upper bound of ${\mathcal{O}}^*({2^{\frac{K}{6.2158}}})$ for Max-2-Sat (each clause contains at most 2 literals), where K is the number of clauses. The run time has been achieved by using heuristic priorities on the choice of the variable on which we branch. The implementation of these heuristic priorities is rather simple, though they have a significant effect on the run time. Also the analysis uses a non-standard measure.</div>
</front>
</TEI>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001175 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Curation/biblio.hfd -nk 001175 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Rhénanie |area= UnivTrevesV1 |flux= Main |étape= Curation |type= RBID |clé= ISTEX:9C5537D0EC1486E53D2B4631D5B9DE8D69231B2D |texte= A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach }}
![]() | This area was generated with Dilib version V0.6.31. | ![]() |