A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
Identifieur interne : 001842 ( Istex/Corpus ); précédent : 001841; suivant : 001843A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
Auteurs : Daniel Raible ; Henning FernauSource :
- 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 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><affiliation><mods:affiliation>University of Trier, FB 4—Abteilung Informatik, 54286, Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: raible@informatik.uni-trier.de</mods:affiliation></affiliation></author><author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><affiliation><mods:affiliation>University of Trier, FB 4—Abteilung Informatik, 54286, Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: fernau@informatik.uni-trier.de</mods:affiliation></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></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><mods:affiliation>University of Trier, FB 4—Abteilung Informatik, 54286, Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: raible@informatik.uni-trier.de</mods:affiliation></affiliation></author><author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><affiliation><mods:affiliation>University of Trier, FB 4—Abteilung Informatik, 54286, Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: fernau@informatik.uni-trier.de</mods:affiliation></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><istex><corpusName>springer</corpusName><author><json:item><name>Daniel Raible</name><affiliations><json:string>University of Trier, FB 4—Abteilung Informatik, 54286, Trier, Germany</json:string><json:string>E-mail: raible@informatik.uni-trier.de</json:string></affiliations></json:item><json:item><name>Henning Fernau</name><affiliations><json:string>University of Trier, FB 4—Abteilung Informatik, 54286, Trier, Germany</json:string><json:string>E-mail: fernau@informatik.uni-trier.de</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><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.</abstract><qualityIndicators><score>7.64</score><pdfVersion>1.6</pdfVersion><pdfPageSize>430 x 660 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>593</abstractCharCount><pdfWordCount>7073</pdfWordCount><pdfCharCount>28138</pdfCharCount><pdfPageCount>12</pdfPageCount><abstractWordCount>95</abstractWordCount></qualityIndicators><title>A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach</title><chapterId><json:string>45</json:string><json:string>Chap45</json:string></chapterId><refBibs><json:item><author><json:item><name>J Gramm</name></json:item><json:item><name>E,A Hirsch</name></json:item><json:item><name>R Niedermeier</name></json:item><json:item><name>P Rossmanith</name></json:item></author><host><volume>130</volume><pages><last>155</last><first>139</first></pages><author></author><title>Discrete Applied Mathematics</title><publicationDate>2003</publicationDate></host><title>Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT</title><publicationDate>2003</publicationDate></json:item><json:item><author><json:item><name>J Gramm</name></json:item><json:item><name>R Niedermeier</name></json:item></author><host><pages><last>186</last><first>174</first></pages><author></author><title>CIAC 2000</title><publicationDate>2000</publicationDate></host><title>Faster exact solutions for MAX2SAT</title><publicationDate>2000</publicationDate></json:item><json:item><author><json:item><name>T Hofmeister</name></json:item></author><host><pages><last>312</last><first>301</first></pages><author></author><title>ESA 2003</title><publicationDate>2003</publicationDate></host><title>An approximation algorithm for MAX-2-SAT with cardinality constraint</title><publicationDate>2003</publicationDate></json:item><json:item><author><json:item><name>J Kneis</name></json:item><json:item><name>D Mölle</name></json:item><json:item><name>S Richter</name></json:item><json:item><name>P Rossmanith</name></json:item></author><host><pages><last>396</last><first>385</first></pages><author></author><title>WG 2005</title><publicationDate>2005</publicationDate></host><title>Algorithms based on the treewidth of sparse graphs</title><publicationDate>2005</publicationDate></json:item><json:item><host><pages><last>17</last><first>11</first></pages><author><json:item><name>A Kojevnikov</name></json:item><json:item><name>A,S Kulikov</name></json:item></author><title>A new approach to proving upper bounds for MAX- 2-SAT</title><publicationDate>2006</publicationDate></host></json:item><json:item><author><json:item><name>A,S Kulikov</name></json:item><json:item><name>K Kutzkov</name></json:item></author><host><volume>4649</volume><pages><last>204</last><first>194</first></pages><author></author><title>LNCS</title><publicationDate>2007</publicationDate></host><title>New bounds for max-sat by clause learning</title><publicationDate>2007</publicationDate></json:item><json:item><author><json:item><name>M Lewin</name></json:item><json:item><name>D Livnat</name></json:item><json:item><name>U Zwick</name></json:item></author><host><volume>2337</volume><pages><last>82</last><first>67</first></pages><author></author><title>LNCS</title><publicationDate>2002</publicationDate></host><title>Improved rounding techniques for the MAX 2- SAT and MAX DI-CUT problems</title><publicationDate>2002</publicationDate></json:item><json:item><author><json:item><name>R Niedermeier</name></json:item><json:item><name>P Rossmanith</name></json:item></author><host><volume>36</volume><pages><last>88</last><first>63</first></pages><author></author><title>Journal of Algorithms</title><publicationDate>2000</publicationDate></host><title>New upper bounds for maximum satisfiability</title><publicationDate>2000</publicationDate></json:item><json:item><author><json:item><name>A Scott</name></json:item><json:item><name>G Sorkin</name></json:item></author><host><volume>434</volume><pages><last>287</last><first>260</first></pages><author></author><title>Discrete Optimization</title><publicationDate>2007</publicationDate></host><title>Linear-programming design and analysis of fast algorithms for Max 2-CSP</title><publicationDate>2007</publicationDate></json:item><json:item><author><json:item><name>R Williams</name></json:item></author><host><volume>348</volume><pages><last>365</last><first>357</first></pages><issue>2-3</issue><author></author><title>Theoretical Computer Science</title><publicationDate>2005</publicationDate></host><title>A new algorithm for optimal 2-constraint satisfaction and its implications</title><publicationDate>2005</publicationDate></json:item></refBibs><genre><json:string>conference</json:string></genre><serie><editor><json:item><name>David Hutchison</name></json:item><json:item><name>Takeo Kanade</name></json:item><json:item><name>Josef Kittler</name></json:item><json:item><name>Jon M. Kleinberg</name></json:item><json:item><name>Friedemann Mattern</name></json:item><json:item><name>John C. Mitchell</name></json:item><json:item><name>Moni Naor</name></json:item><json:item><name>Oscar Nierstrasz</name></json:item><json:item><name>C. Pandu Rangan</name></json:item><json:item><name>Bernhard Steffen</name></json:item><json:item><name>Madhu Sudan</name></json:item><json:item><name>Demetri Terzopoulos</name></json:item><json:item><name>Doug Tygar</name></json:item><json:item><name>Moshe Y. Vardi</name></json:item><json:item><name>Gerhard Weikum</name></json:item></editor><issn><json:string>0302-9743</json:string></issn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Lecture Notes in Computer Science</title><copyrightDate>2008</copyrightDate></serie><host><editor><json:item><name>Edward Ochmański</name></json:item><json:item><name>Jerzy Tyszkiewicz</name></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Algorithm Analysis and Problem Complexity</value></json:item><json:item><value>Computation by Abstract Devices</value></json:item><json:item><value>Discrete Mathematics in Computer Science</value></json:item><json:item><value>Data Structures</value></json:item><json:item><value>Logics and Meanings of Programs</value></json:item><json:item><value>Algorithms</value></json:item></subject><isbn><json:string>978-3-540-85237-7</json:string></isbn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Mathematical Foundations of Computer Science 2008</title><bookId><json:string>978-3-540-85238-4</json:string></bookId><volume>5162</volume><pages><last>562</last><first>551</first></pages><issn><json:string>0302-9743</json:string></issn><genre><json:string>book-series</json:string></genre><eisbn><json:string>978-3-540-85238-4</json:string></eisbn><copyrightDate>2008</copyrightDate><doi><json:string>10.1007/978-3-540-85238-4</json:string></doi></host><publicationDate>2008</publicationDate><copyrightDate>2008</copyrightDate><doi><json:string>10.1007/978-3-540-85238-4_45</json:string></doi><id>9C5537D0EC1486E53D2B4631D5B9DE8D69231B2D</id><score>1.1635544</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/9C5537D0EC1486E53D2B4631D5B9DE8D69231B2D/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/9C5537D0EC1486E53D2B4631D5B9DE8D69231B2D/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/9C5537D0EC1486E53D2B4631D5B9DE8D69231B2D/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach</title><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><availability><p>Springer-Verlag Berlin Heidelberg, 2008</p></availability><date>2008</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach</title><author xml:id="author-1"><persName><forename type="first">Daniel</forename><surname>Raible</surname></persName><email>raible@informatik.uni-trier.de</email><affiliation>University of Trier, FB 4—Abteilung Informatik, 54286, Trier, Germany</affiliation></author><author xml:id="author-2"><persName><forename type="first">Henning</forename><surname>Fernau</surname></persName><email>fernau@informatik.uni-trier.de</email><affiliation>University of Trier, FB 4—Abteilung Informatik, 54286, Trier, Germany</affiliation></author></analytic><monogr><title level="m">Mathematical Foundations of Computer Science 2008</title><title level="m" type="sub">33rd International Symposium, MFCS 2008, Toru´n, Poland, August 25-29, 2008. Proceedings</title><idno type="pISBN">978-3-540-85237-7</idno><idno type="eISBN">978-3-540-85238-4</idno><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="DOI">10.1007/978-3-540-85238-4</idno><idno type="book-ID">978-3-540-85238-4</idno><idno type="book-title-ID">177567</idno><idno type="book-sequence-number">5162</idno><idno type="book-volume-number">5162</idno><idno type="book-chapter-count">50</idno><editor><persName><forename type="first">Edward</forename><surname>Ochmański</surname></persName></editor><editor><persName><forename type="first">Jerzy</forename><surname>Tyszkiewicz</surname></persName></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2008"></date><biblScope unit="volume">5162</biblScope><biblScope unit="page" from="551">551</biblScope><biblScope unit="page" to="562">562</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><editor><persName><forename type="first">David</forename><surname>Hutchison</surname></persName></editor><editor><persName><forename type="first">Takeo</forename><surname>Kanade</surname></persName></editor><editor><persName><forename type="first">Josef</forename><surname>Kittler</surname></persName></editor><editor><persName><forename type="first">Jon</forename><forename type="first">M.</forename><surname>Kleinberg</surname></persName></editor><editor><persName><forename type="first">Friedemann</forename><surname>Mattern</surname></persName></editor><editor><persName><forename type="first">John</forename><forename type="first">C.</forename><surname>Mitchell</surname></persName></editor><editor><persName><forename type="first">Moni</forename><surname>Naor</surname></persName></editor><editor><persName><forename type="first">Oscar</forename><surname>Nierstrasz</surname></persName></editor><editor><persName><forename type="first">C.</forename><surname>Pandu Rangan</surname></persName></editor><editor><persName><forename type="first">Bernhard</forename><surname>Steffen</surname></persName></editor><editor><persName><forename type="first">Madhu</forename><surname>Sudan</surname></persName></editor><editor><persName><forename type="first">Demetri</forename><surname>Terzopoulos</surname></persName></editor><editor><persName><forename type="first">Doug</forename><surname>Tygar</surname></persName></editor><editor><persName><forename type="first">Moshe</forename><forename type="first">Y.</forename><surname>Vardi</surname></persName></editor><editor><persName><forename type="first">Gerhard</forename><surname>Weikum</surname></persName></editor><biblScope><date>2008</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="series-Id">558</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></fileDesc><profileDesc><creation><date>2008</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>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.</p></abstract><textClass><keywords scheme="Book-Subject-Collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass><keywords scheme="Book-Subject-Group"><list><label>I</label><label>I16021</label><label>I16013</label><label>I17028</label><label>I15017</label><label>I1603X</label><label>M14018</label><item><term>Computer Science</term></item><item><term>Algorithm Analysis and Problem Complexity</term></item><item><term>Computation by Abstract Devices</term></item><item><term>Discrete Mathematics in Computer Science</term></item><item><term>Data Structures</term></item><item><term>Logics and Meanings of Programs</term></item><item><term>Algorithms</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2008">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2016-11-22">References added</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2017-01-20">References added</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/9C5537D0EC1486E53D2B4631D5B9DE8D69231B2D/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Springer, Publisher found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo SeriesType="Series" TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>David</GivenName><FamilyName>Hutchison</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Takeo</GivenName><FamilyName>Kanade</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Josef</GivenName><FamilyName>Kittler</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Jon</GivenName><GivenName>M.</GivenName><FamilyName>Kleinberg</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Friedemann</GivenName><FamilyName>Mattern</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>John</GivenName><GivenName>C.</GivenName><FamilyName>Mitchell</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Moni</GivenName><FamilyName>Naor</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Oscar</GivenName><FamilyName>Nierstrasz</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>C.</GivenName><FamilyName>Pandu Rangan</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Bernhard</GivenName><FamilyName>Steffen</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Madhu</GivenName><FamilyName>Sudan</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Demetri</GivenName><FamilyName>Terzopoulos</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Doug</GivenName><FamilyName>Tygar</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Moshe</GivenName><GivenName>Y.</GivenName><FamilyName>Vardi</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Weikum</FamilyName></EditorName></Editor></EditorGroup></SeriesHeader><Book Language="En"><BookInfo BookProductType="Proceedings" ContainsESM="No" Language="En" MediaType="eBook" NumberingStyle="Unnumbered" OutputMedium="All" TocLevels="0"><BookID>978-3-540-85238-4</BookID><BookTitle>Mathematical Foundations of Computer Science 2008</BookTitle><BookSubTitle>33rd International Symposium, MFCS 2008, Toru´n, Poland, August 25-29, 2008. Proceedings</BookSubTitle><BookVolumeNumber>5162</BookVolumeNumber><BookSequenceNumber>5162</BookSequenceNumber><BookDOI>10.1007/978-3-540-85238-4</BookDOI><BookTitleID>177567</BookTitleID><BookPrintISBN>978-3-540-85237-7</BookPrintISBN><BookElectronicISBN>978-3-540-85238-4</BookElectronicISBN><BookChapterCount>50</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2008</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I16021" Priority="1" Type="Secondary">Algorithm Analysis and Problem Complexity</BookSubject><BookSubject Code="I16013" Priority="2" Type="Secondary">Computation by Abstract Devices</BookSubject><BookSubject Code="I17028" Priority="3" Type="Secondary">Discrete Mathematics in Computer Science</BookSubject><BookSubject Code="I15017" Priority="4" Type="Secondary">Data Structures</BookSubject><BookSubject Code="I1603X" Priority="5" Type="Secondary">Logics and Meanings of Programs</BookSubject><BookSubject Code="M14018" Priority="6" Type="Secondary">Algorithms</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup></BookInfo><BookHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Edward</GivenName><FamilyName>Ochmański</FamilyName></EditorName><Contact><Email>edoch@mat.uni.torun.pl</Email></Contact></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Jerzy</GivenName><FamilyName>Tyszkiewicz</FamilyName></EditorName><Contact><Email>jty@mimuw.edu.pl</Email></Contact></Editor></EditorGroup></BookHeader><Part ID="Part2"><PartInfo TocLevels="0"><PartID>2</PartID><PartSequenceNumber>2</PartSequenceNumber><PartTitle>Contributed Papers</PartTitle><PartChapterCount>45</PartChapterCount><PartContext><SeriesID>558</SeriesID><BookTitle>Mathematical Foundations of Computer Science 2008</BookTitle></PartContext></PartInfo><Chapter ID="Chap45" Language="En"><ChapterInfo ChapterType="OriginalPaper" ContainsESM="No" NumberingStyle="Unnumbered" TocLevels="0"><ChapterID>45</ChapterID><ChapterDOI>10.1007/978-3-540-85238-4_45</ChapterDOI><ChapterSequenceNumber>45</ChapterSequenceNumber><ChapterTitle Language="En">A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach</ChapterTitle><ChapterFirstPage>551</ChapterFirstPage><ChapterLastPage>562</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2008</CopyrightYear></ChapterCopyright><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><PartID>2</PartID><BookID>978-3-540-85238-4</BookID><BookTitle>Mathematical Foundations of Computer Science 2008</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>Daniel</GivenName><FamilyName>Raible</FamilyName></AuthorName><Contact><Email>raible@informatik.uni-trier.de</Email></Contact></Author><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>Henning</GivenName><FamilyName>Fernau</FamilyName></AuthorName><Contact><Email>fernau@informatik.uni-trier.de</Email></Contact></Author><Affiliation ID="Aff1"><OrgName>University of Trier</OrgName><OrgAddress><Street>FB 4—Abteilung Informatik</Street><Postcode>54286</Postcode><City>Trier</City><Country>Germany</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>In <Emphasis Type="SmallCaps">MaxSat</Emphasis>, 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 <InlineEquation ID="IEq1"><InlineMediaObject><ImageObject FileRef="978-3-540-85238-4_45_Chapter_TeX2GIFIEq1.gif" Format="GIF" Color="BlackWhite" Type="Linedraw" Rendition="HTML"></ImageObject></InlineMediaObject><EquationSource Format="TEX">${\mathcal{O}}^*({2^{\frac{K}{6.2158}}})$</EquationSource></InlineEquation> for <Emphasis Type="SmallCaps">Max-2-Sat</Emphasis> (each clause contains at most 2 literals), where <Emphasis Type="Italic">K</Emphasis> 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.</Para></Abstract></ChapterHeader><NoBody></NoBody></Chapter></Part></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach</title></titleInfo><name type="personal"><namePart type="given">Daniel</namePart><namePart type="family">Raible</namePart><affiliation>University of Trier, FB 4—Abteilung Informatik, 54286, Trier, Germany</affiliation><affiliation>E-mail: raible@informatik.uni-trier.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Henning</namePart><namePart type="family">Fernau</namePart><affiliation>University of Trier, FB 4—Abteilung Informatik, 54286, Trier, Germany</affiliation><affiliation>E-mail: fernau@informatik.uni-trier.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="conference" displayLabel="OriginalPaper"></genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2008</dateIssued><copyrightDate encoding="w3cdtf">2008</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract 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.</abstract><relatedItem type="host"><titleInfo><title>Mathematical Foundations of Computer Science 2008</title><subTitle>33rd International Symposium, MFCS 2008, Toru´n, Poland, August 25-29, 2008. Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Edward</namePart><namePart type="family">Ochmański</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jerzy</namePart><namePart type="family">Tyszkiewicz</namePart><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">2008</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book-Subject-Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I16021">Algorithm Analysis and Problem Complexity</topic><topic authority="SpringerSubjectCodes" authorityURI="I16013">Computation by Abstract Devices</topic><topic authority="SpringerSubjectCodes" authorityURI="I17028">Discrete Mathematics in Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I15017">Data Structures</topic><topic authority="SpringerSubjectCodes" authorityURI="I1603X">Logics and Meanings of Programs</topic><topic authority="SpringerSubjectCodes" authorityURI="M14018">Algorithms</topic></subject><identifier type="DOI">10.1007/978-3-540-85238-4</identifier><identifier type="ISBN">978-3-540-85237-7</identifier><identifier type="eISBN">978-3-540-85238-4</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">177567</identifier><identifier type="BookID">978-3-540-85238-4</identifier><identifier type="BookChapterCount">50</identifier><identifier type="BookVolumeNumber">5162</identifier><identifier type="BookSequenceNumber">5162</identifier><identifier type="PartChapterCount">45</identifier><part><date>2008</date><detail type="part"><title>Contributed Papers</title></detail><detail type="volume"><number>5162</number><caption>vol.</caption></detail><extent unit="pages"><start>551</start><end>562</end></extent></part><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2008</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">David</namePart><namePart type="family">Hutchison</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Takeo</namePart><namePart type="family">Kanade</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Josef</namePart><namePart type="family">Kittler</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jon</namePart><namePart type="given">M.</namePart><namePart type="family">Kleinberg</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Friedemann</namePart><namePart type="family">Mattern</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">John</namePart><namePart type="given">C.</namePart><namePart type="family">Mitchell</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moni</namePart><namePart type="family">Naor</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Oscar</namePart><namePart type="family">Nierstrasz</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">C.</namePart><namePart type="family">Pandu Rangan</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Bernhard</namePart><namePart type="family">Steffen</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Madhu</namePart><namePart type="family">Sudan</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Demetri</namePart><namePart type="family">Terzopoulos</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Doug</namePart><namePart type="family">Tygar</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moshe</namePart><namePart type="given">Y.</namePart><namePart type="family">Vardi</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Weikum</namePart><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><copyrightDate encoding="w3cdtf">2008</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2008</recordOrigin></recordInfo></relatedItem><identifier type="istex">9C5537D0EC1486E53D2B4631D5B9DE8D69231B2D</identifier><identifier type="DOI">10.1007/978-3-540-85238-4_45</identifier><identifier type="ChapterID">45</identifier><identifier type="ChapterID">Chap45</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag Berlin Heidelberg, 2008</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag Berlin Heidelberg, 2008</recordOrigin></recordInfo></mods></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001842 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001842 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Istex
|étape= Corpus
|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. |  |