A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
Identifieur interne : 001899 ( Istex/Corpus ); précédent : 001898; suivant : 001900A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
Auteurs : Eran Halperin ; Uri ZwickSource :
- Random Structures & Algorithms [ 1042-9832 ] ; 2002-05.
Abstract
We obtain improved semidefinite programming based approximation algorithms for all the natural maximum bisection problems of graphs. Among the problems considered are: MAX$n\over 2$‐BISECTION—partition the vertices of the graph into two sets of equal size such that the total weight of edges connecting vertices from different sides is maximized; MAX$n\over 2$‐VERTEX‐COVER—find a set containing half of the vertices such that the total weight of edges touching this set is maximized; MAX$n\over 2$‐DENSE‐SUBGRAPH—find a set containing half of the vertices such that the total weight of edges connecting two vertices from this set is maximized; and MAX$n\over 2$UNCUT—partition the vertices into two sets of equal size such that the total weight of edges that do not cross the cut is maximized. We also consider the directed versions of these problems, such as MAX$n\over 2$‐DIRECTED‐BISECTION and MAX$n\over 2$‐DIRECTED‐UNCUT. These results can be used to obtain improved approximation algorithms for the unbalanced versions of the partition problems mentioned above, where we want to partition the graph into two sets of size $k$ and $n - k$, where $k$ is not necessarily $n\over 2$. Our results improve, extend and unify results of Frieze and Jerrum, Feige and Langberg, Ye, and others. All these results may be viewed as extensions of the MAX CUT algorithm of Goemans and Williamson, and the MAX 2‐SAT and MAX DI‐CUT algorithms of Feige and Goemans. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20:382–402, 2002
Url:
DOI: 10.1002/rsa.10035
Links to Exploration step
ISTEX:9A0E7D1FB07BFC648A04A9C3002088E5F009AB2FLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems</title><author><name sortKey="Halperin, Eran" sort="Halperin, Eran" uniqKey="Halperin E" first="Eran" last="Halperin">Eran Halperin</name><affiliation><mods:affiliation>Department of Computer Science, Tel‐Aviv University, Tel‐Aviv 69978, Israel</mods:affiliation></affiliation></author><author><name sortKey="Zwick, Uri" sort="Zwick, Uri" uniqKey="Zwick U" first="Uri" last="Zwick">Uri Zwick</name><affiliation><mods:affiliation>Department of Computer Science, Tel‐Aviv University, Tel‐Aviv 69978, Israel</mods:affiliation></affiliation><affiliation><mods:affiliation>Department of Computer Science, Tel‐Aviv University, Tel‐Aviv 69978, Israel</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:9A0E7D1FB07BFC648A04A9C3002088E5F009AB2F</idno><date when="2002" year="2002">2002</date><idno type="doi">10.1002/rsa.10035</idno><idno type="url">https://api.istex.fr/document/9A0E7D1FB07BFC648A04A9C3002088E5F009AB2F/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001899</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001899</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems</title><author><name sortKey="Halperin, Eran" sort="Halperin, Eran" uniqKey="Halperin E" first="Eran" last="Halperin">Eran Halperin</name><affiliation><mods:affiliation>Department of Computer Science, Tel‐Aviv University, Tel‐Aviv 69978, Israel</mods:affiliation></affiliation></author><author><name sortKey="Zwick, Uri" sort="Zwick, Uri" uniqKey="Zwick U" first="Uri" last="Zwick">Uri Zwick</name><affiliation><mods:affiliation>Department of Computer Science, Tel‐Aviv University, Tel‐Aviv 69978, Israel</mods:affiliation></affiliation><affiliation><mods:affiliation>Department of Computer Science, Tel‐Aviv University, Tel‐Aviv 69978, Israel</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j">Random Structures & Algorithms</title><title level="j" type="abbrev">Random Struct. Alg.</title><idno type="ISSN">1042-9832</idno><idno type="eISSN">1098-2418</idno><imprint><publisher>Wiley Subscription Services, Inc., A Wiley Company</publisher><pubPlace>New York</pubPlace><date type="published" when="2002-05">2002-05</date><biblScope unit="volume">20</biblScope><biblScope unit="issue">3</biblScope><biblScope unit="page" from="382">382</biblScope><biblScope unit="page" to="402">402</biblScope></imprint><idno type="ISSN">1042-9832</idno></series><idno type="istex">9A0E7D1FB07BFC648A04A9C3002088E5F009AB2F</idno><idno type="DOI">10.1002/rsa.10035</idno><idno type="ArticleID">RSA10035</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">1042-9832</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We obtain improved semidefinite programming based approximation algorithms for all the natural maximum bisection problems of graphs. Among the problems considered are: MAX$n\over 2$‐BISECTION—partition the vertices of the graph into two sets of equal size such that the total weight of edges connecting vertices from different sides is maximized; MAX$n\over 2$‐VERTEX‐COVER—find a set containing half of the vertices such that the total weight of edges touching this set is maximized; MAX$n\over 2$‐DENSE‐SUBGRAPH—find a set containing half of the vertices such that the total weight of edges connecting two vertices from this set is maximized; and MAX$n\over 2$UNCUT—partition the vertices into two sets of equal size such that the total weight of edges that do not cross the cut is maximized. We also consider the directed versions of these problems, such as MAX$n\over 2$‐DIRECTED‐BISECTION and MAX$n\over 2$‐DIRECTED‐UNCUT. These results can be used to obtain improved approximation algorithms for the unbalanced versions of the partition problems mentioned above, where we want to partition the graph into two sets of size $k$ and $n - k$, where $k$ is not necessarily $n\over 2$. Our results improve, extend and unify results of Frieze and Jerrum, Feige and Langberg, Ye, and others. All these results may be viewed as extensions of the MAX CUT algorithm of Goemans and Williamson, and the MAX 2‐SAT and MAX DI‐CUT algorithms of Feige and Goemans. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20:382–402, 2002</div></front></TEI><istex><corpusName>wiley</corpusName><author><json:item><name>Eran Halperin</name><affiliations><json:string>Department of Computer Science, Tel‐Aviv University, Tel‐Aviv 69978, Israel</json:string></affiliations></json:item><json:item><name>Uri Zwick</name><affiliations><json:string>Department of Computer Science, Tel‐Aviv University, Tel‐Aviv 69978, Israel</json:string><json:string>Department of Computer Science, Tel‐Aviv University, Tel‐Aviv 69978, Israel</json:string></affiliations></json:item></author><articleId><json:string>RSA10035</json:string></articleId><language><json:string>eng</json:string></language><originalGenre><json:string>article</json:string></originalGenre><abstract>We obtain improved semidefinite programming based approximation algorithms for all the natural maximum bisection problems of graphs. Among the problems considered are: MAX$n\over 2$‐BISECTION—partition the vertices of the graph into two sets of equal size such that the total weight of edges connecting vertices from different sides is maximized; MAX$n\over 2$‐VERTEX‐COVER—find a set containing half of the vertices such that the total weight of edges touching this set is maximized; MAX$n\over 2$‐DENSE‐SUBGRAPH—find a set containing half of the vertices such that the total weight of edges connecting two vertices from this set is maximized; and MAX$n\over 2$UNCUT—partition the vertices into two sets of equal size such that the total weight of edges that do not cross the cut is maximized. We also consider the directed versions of these problems, such as MAX$n\over 2$‐DIRECTED‐BISECTION and MAX$n\over 2$‐DIRECTED‐UNCUT. These results can be used to obtain improved approximation algorithms for the unbalanced versions of the partition problems mentioned above, where we want to partition the graph into two sets of size $k$ and $n - k$, where $k$ is not necessarily $n\over 2$. Our results improve, extend and unify results of Frieze and Jerrum, Feige and Langberg, Ye, and others. All these results may be viewed as extensions of the MAX CUT algorithm of Goemans and Williamson, and the MAX 2‐SAT and MAX DI‐CUT algorithms of Feige and Goemans. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20:382–402, 2002</abstract><qualityIndicators><score>7.832</score><pdfVersion>1.2</pdfVersion><pdfPageSize>506 x 723 pts</pdfPageSize><refBibsNative>true</refBibsNative><abstractCharCount>1522</abstractCharCount><pdfWordCount>8804</pdfWordCount><pdfCharCount>37378</pdfCharCount><pdfPageCount>21</pdfPageCount><abstractWordCount>236</abstractWordCount></qualityIndicators><title>A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems</title><refBibs><json:item><host><author></author><title>An 0.5‐approximation algorithm for MAX DICUT with given sizes of parts</title></host></json:item><json:item><author><json:item><name>F. Barahona</name></json:item><json:item><name>A. R. Mahjoub</name></json:item></author><host><volume>36</volume><pages><last>173</last><first>157</first></pages><author></author><title>Math Program</title></host><title>On the cut polytope</title></json:item><json:item><host><pages><last>189</last><first>182</first></pages><author></author><title>U. Feige and M. X. Goemans,Approximating the value of two prover proof systems, with applications to MAX‐2SAT and MAX‐DICUT, Proc 3rd Israel Symp Theory and Computing Systems, Tel Aviv, Israel, 1995, pp. 182–189.</title></host></json:item><json:item><host><author></author><title>Approximation algorithms for maximization problems arising in graph partitioning</title></host></json:item><json:item><host><author></author><title>The RPR2 rounding technique for semidefinite programs</title></host></json:item><json:item><host><author></author><title>On the integrality ratio of semidefinite relaxations of MAX CUT</title></host></json:item><json:item><host><author></author><title>Improved approximation of Max‐Cut on graphs of bounded degree</title></host></json:item><json:item><host><author></author><title>A note on approximating MAX‐BISECTION on regular graphs</title></host></json:item><json:item><author><json:item><name>A. M. Frieze</name></json:item><json:item><name>M. Jerrum</name></json:item></author><host><volume>18</volume><pages><last>81</last><first>67</first></pages><author></author><title>Algorithmica</title></host><title>Improved approximation algorithms for MAX k‐CUT and MAX BISECTION</title></json:item><json:item><author><json:item><name>M. X. Goemans</name></json:item><json:item><name>D. P. Williamson</name></json:item></author><host><volume>42</volume><pages><last>1145</last><first>1115</first></pages><author></author><title>J Appl Comput Math</title></host><title>Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming</title></json:item><json:item><author><json:item><name>M. Grötschel</name></json:item><json:item><name>L. Lovász</name></json:item><json:item><name>A. Schrijver</name></json:item></author><host><volume>1</volume><pages><last>197</last><first>169</first></pages><author></author><title>Combinatorica</title></host><title>The ellipsoid method and its consequences in combinatorial optimization</title></json:item><json:item><host><author></author><title>An improved rounding method and semidefinite programming relaxation for graph partition</title></host></json:item><json:item><host><author></author><title>On approximation of Max‐Vertex‐Cover</title></host></json:item><json:item><host><author></author><title>A 7/8‐approximation algorithm for MAX 3SAT?</title></host></json:item><json:item><author><json:item><name>S. Mahajan</name></json:item><json:item><name>H. Ramesh</name></json:item></author><host><volume>28</volume><pages><last>1663</last><first>1641</first></pages><author></author><title>SIAM J Comput</title></host><title>Derandomizing approximation algorithms based on semidefinite programming</title></json:item><json:item><author><json:item><name>Y. E. Nesterov</name></json:item></author><host><volume>9</volume><pages><last>160</last><first>141</first></pages><author></author><title>Optim Methods Software</title></host><title>Semidefinite relaxation and nonconvex quadratic optimization</title></json:item><json:item><author><json:item><name>P. Turán</name></json:item></author><host><volume>48</volume><pages><last>452</last><first>436</first></pages><author></author><title>Mat Fiz Lapok</title></host><title>On an extremal problem in graph theory</title></json:item><json:item><host><author></author><title>H. Wolkowicz, R. Saigal, and L. Vandenberghe (Eds.), Handbook of semidefinite programming, Kluwer, Boston, 2000.</title></host></json:item><json:item><host><author></author><title>A 0.699‐approximation algorithm for Max‐Bisection</title></host></json:item><json:item><host><author></author><title>Y. Ye and J. Zhang,Approximation of dense‐‐subgraph and the complement of min‐bisection, manuscript, 1999.</title></host></json:item><json:item><host><author></author><title>Outward rotations: A tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems</title></host></json:item><json:item><host><author></author><title>Analyzing the MAX 2‐SAT and MAX DI‐CUT approximation algorithms of Feige and Goemans</title></host></json:item><json:item><host><author></author><title>Computer assisted proof of optimal approximability results</title></host></json:item></refBibs><genre><json:string>article</json:string></genre><host><volume>20</volume><publisherId><json:string>RSA</json:string></publisherId><pages><total>21</total><last>402</last><first>382</first></pages><issn><json:string>1042-9832</json:string></issn><issue>3</issue><author><json:item><name>Tibor Jordan</name></json:item><json:item><name>Alessandro Panconesi</name></json:item></author><genre><json:string>journal</json:string></genre><language><json:string>unknown</json:string></language><eissn><json:string>1098-2418</json:string></eissn><title>Random Structures & Algorithms</title><doi><json:string>10.1002/(ISSN)1098-2418</json:string></doi></host><categories><wos><json:string>science</json:string><json:string>mathematics, applied</json:string><json:string>mathematics</json:string><json:string>computer science, software engineering</json:string></wos><scienceMetrix><json:string>applied sciences</json:string><json:string>information & communication technologies</json:string><json:string>computation theory & mathematics</json:string></scienceMetrix></categories><publicationDate>2002</publicationDate><copyrightDate>2002</copyrightDate><doi><json:string>10.1002/rsa.10035</json:string></doi><id>9A0E7D1FB07BFC648A04A9C3002088E5F009AB2F</id><score>0.028070036</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/9A0E7D1FB07BFC648A04A9C3002088E5F009AB2F/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/9A0E7D1FB07BFC648A04A9C3002088E5F009AB2F/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/9A0E7D1FB07BFC648A04A9C3002088E5F009AB2F/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>Wiley Subscription Services, Inc., A Wiley Company</publisher><pubPlace>New York</pubPlace><availability><p>Copyright © 2002 Wiley Periodicals, Inc.</p></availability><date>2002</date></publicationStmt><notesStmt><note type="content">**A preliminary version of this paper is to appear in the proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization (IPCO'01), Utrecht, The Netherlands, 2001.</note></notesStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems</title><author xml:id="author-1"><persName><forename type="first">Eran</forename><surname>Halperin</surname></persName><affiliation>Department of Computer Science, Tel‐Aviv University, Tel‐Aviv 69978, Israel</affiliation></author><author xml:id="author-2"><persName><forename type="first">Uri</forename><surname>Zwick</surname></persName><affiliation>Department of Computer Science, Tel‐Aviv University, Tel‐Aviv 69978, Israel</affiliation><affiliation>Department of Computer Science, Tel‐Aviv University, Tel‐Aviv 69978, Israel</affiliation></author></analytic><monogr><title level="j">Random Structures & Algorithms</title><title level="j" type="abbrev">Random Struct. Alg.</title><idno type="pISSN">1042-9832</idno><idno type="eISSN">1098-2418</idno><idno type="DOI">10.1002/(ISSN)1098-2418</idno><imprint><publisher>Wiley Subscription Services, Inc., A Wiley Company</publisher><pubPlace>New York</pubPlace><date type="published" when="2002-05"></date><biblScope unit="volume">20</biblScope><biblScope unit="issue">3</biblScope><biblScope unit="page" from="382">382</biblScope><biblScope unit="page" to="402">402</biblScope></imprint></monogr><idno type="istex">9A0E7D1FB07BFC648A04A9C3002088E5F009AB2F</idno><idno type="DOI">10.1002/rsa.10035</idno><idno type="ArticleID">RSA10035</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>2002</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>We obtain improved semidefinite programming based approximation algorithms for all the natural maximum bisection problems of graphs. Among the problems considered are: MAX$n\over 2$‐BISECTION—partition the vertices of the graph into two sets of equal size such that the total weight of edges connecting vertices from different sides is maximized; MAX$n\over 2$‐VERTEX‐COVER—find a set containing half of the vertices such that the total weight of edges touching this set is maximized; MAX$n\over 2$‐DENSE‐SUBGRAPH—find a set containing half of the vertices such that the total weight of edges connecting two vertices from this set is maximized; and MAX$n\over 2$UNCUT—partition the vertices into two sets of equal size such that the total weight of edges that do not cross the cut is maximized. We also consider the directed versions of these problems, such as MAX$n\over 2$‐DIRECTED‐BISECTION and MAX$n\over 2$‐DIRECTED‐UNCUT. These results can be used to obtain improved approximation algorithms for the unbalanced versions of the partition problems mentioned above, where we want to partition the graph into two sets of size $k$ and $n - k$, where $k$ is not necessarily $n\over 2$. Our results improve, extend and unify results of Frieze and Jerrum, Feige and Langberg, Ye, and others. All these results may be viewed as extensions of the MAX CUT algorithm of Goemans and Williamson, and the MAX 2‐SAT and MAX DI‐CUT algorithms of Feige and Goemans. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20:382–402, 2002</p></abstract></profileDesc><revisionDesc><change when="2001-02-18">Received</change><change when="2002-01-28">Registration</change><change when="2002-05">Published</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/9A0E7D1FB07BFC648A04A9C3002088E5F009AB2F/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Wiley, elements deleted: body"><istex:xmlDeclaration>version="1.0" encoding="UTF-8" standalone="yes"</istex:xmlDeclaration><istex:document><component version="2.0" type="serialArticle" xml:lang="en"><header><publicationMeta level="product"><publisherInfo><publisherName>Wiley Subscription Services, Inc., A Wiley Company</publisherName><publisherLoc>New York</publisherLoc></publisherInfo><doi registered="yes">10.1002/(ISSN)1098-2418</doi><issn type="print">1042-9832</issn><issn type="electronic">1098-2418</issn><idGroup><id type="product" value="RSA"></id></idGroup><titleGroup><title type="main" xml:lang="en" sort="RANDOM STRUCTURES AND ALGORITHMS">Random Structures & Algorithms</title><title type="short">Random Struct. Alg.</title></titleGroup></publicationMeta><publicationMeta level="part" position="30"><doi origin="wiley" registered="yes">10.1002/rsa.v20:3</doi><titleGroup><title type="specialIssueTitle">Probabilistic Methods in Combinatorial Optimization</title></titleGroup><numberingGroup><numbering type="journalVolume" number="20">20</numbering><numbering type="journalIssue">3</numbering></numberingGroup><creators><creator xml:id="sped1" creatorRole="sponsoringEditor"><personName><givenNames>Tibor</givenNames><familyName>Jordan</familyName></personName></creator><creator xml:id="sped2" creatorRole="sponsoringEditor"><personName><givenNames>Alessandro</givenNames><familyName>Panconesi</familyName></personName></creator></creators><coverDate startDate="2002-05">May 2002</coverDate></publicationMeta><publicationMeta level="unit" type="article" position="60" status="forIssue"><doi origin="wiley" registered="yes">10.1002/rsa.10035</doi><idGroup><id type="unit" value="RSA10035"></id></idGroup><countGroup><count type="pageTotal" number="21"></count></countGroup><copyright ownership="publisher">Copyright © 2002 Wiley Periodicals, Inc.</copyright><eventGroup><event type="manuscriptReceived" date="2001-02-18"></event><event type="manuscriptRevised" date="2002-01-16"></event><event type="manuscriptAccepted" date="2002-01-28"></event><event type="firstOnline" date="2002-04-04"></event><event type="publishedOnlineFinalForm" date="2002-04-04"></event><event type="xmlConverted" agent="Converter:JWSART34_TO_WML3G version:2.3.6 mode:FullText source:HeaderRef result:HeaderRef mathml2tex" date="2010-05-18"></event><event type="xmlConverted" agent="Converter:WILEY_ML3G_TO_WILEY_ML3GV2 version:3.8.8" date="2014-02-08"></event><event type="xmlConverted" agent="Converter:WML3G_To_WML3G version:4.1.7 mode:FullText,remove_FC" date="2014-11-03"></event></eventGroup><numberingGroup><numbering type="pageFirst">382</numbering><numbering type="pageLast">402</numbering></numberingGroup><correspondenceTo>Department of Computer Science, Tel‐Aviv University, Tel‐Aviv 69978, Israel</correspondenceTo><linkGroup><link type="toTypesetVersion" href="file:RSA.RSA10035.pdf"></link></linkGroup></publicationMeta><contentMeta><countGroup><count type="figureTotal" number="4"></count><count type="tableTotal" number="3"></count><count type="referenceTotal" number="23"></count><count type="wordTotal" number="9900"></count></countGroup><titleGroup><title type="main" xml:lang="en">A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems<link href="#fn2"></link></title><title type="short" xml:lang="en">Obtaining Improved Approximation Algorithms</title></titleGroup><creators><creator xml:id="au1" creatorRole="author" affiliationRef="#af1"><personName><givenNames>Eran</givenNames><familyName>Halperin</familyName></personName></creator><creator xml:id="au2" creatorRole="author" affiliationRef="#af1" corresponding="yes"><personName><givenNames>Uri</givenNames><familyName>Zwick</familyName></personName><contactDetails><email>zwick@post.tau.ac.il</email></contactDetails></creator></creators><affiliationGroup><affiliation xml:id="af1" countryCode="IL" type="organization"><unparsedAffiliation>Department of Computer Science, Tel‐Aviv University, Tel‐Aviv 69978, Israel</unparsedAffiliation></affiliation></affiliationGroup><abstractGroup><abstract type="main" xml:lang="en"><title type="main">Abstract</title><p>We obtain improved semidefinite programming based approximation algorithms for <i>all</i> the natural maximum bisection problems of graphs. Among the problems considered are: MAX<span type="tex">$n\over 2$<inlineGraphic alt="equation image" location="equation/tex2gif-ueqn-1.gif" href=""></inlineGraphic></span>‐BISECTION—partition the vertices of the graph into two sets of equal size such that the total weight of edges connecting vertices from different sides is maximized; MAX<span type="tex">$n\over 2$<inlineGraphic alt="equation image" location="equation/tex2gif-ueqn-2.gif" href=""></inlineGraphic></span>‐VERTEX‐COVER—find a set containing half of the vertices such that the total weight of edges touching this set is maximized; MAX<span type="tex">$n\over 2$<inlineGraphic alt="equation image" location="equation/tex2gif-ueqn-3.gif" href=""></inlineGraphic></span>‐DENSE‐SUBGRAPH—find a set containing half of the vertices such that the total weight of edges connecting two vertices from this set is maximized; and MAX<span type="tex">$n\over 2$<inlineGraphic alt="equation image" location="equation/tex2gif-ueqn-4.gif" href=""></inlineGraphic></span>U<sc>N</sc>CUT—partition the vertices into two sets of equal size such that the total weight of edges that do <i>not</i> cross the cut is maximized. We also consider the directed versions of these problems, such as MAX<span type="tex">$n\over 2$<inlineGraphic alt="equation image" location="equation/tex2gif-ueqn-5.gif" href=""></inlineGraphic></span>‐DIRECTED‐BISECTION and MAX<span type="tex">$n\over 2$<inlineGraphic alt="equation image" location="equation/tex2gif-ueqn-6.gif" href=""></inlineGraphic></span>‐DIRECTED‐U<sc>N</sc>CUT. These results can be used to obtain improved approximation algorithms for the unbalanced versions of the partition problems mentioned above, where we want to partition the graph into two sets of size <span type="tex">$k$<inlineGraphic alt="equation image" location="equation/tex2gif-ueqn-7.gif" href=""></inlineGraphic></span> and <span type="tex">$n - k$<inlineGraphic alt="equation image" location="equation/tex2gif-ueqn-8.gif" href=""></inlineGraphic></span>, where <span type="tex">$k$<inlineGraphic alt="equation image" location="equation/tex2gif-ueqn-9.gif" href=""></inlineGraphic></span> is not necessarily <span type="tex">$n\over 2$<inlineGraphic alt="equation image" location="equation/tex2gif-ueqn-10.gif" href=""></inlineGraphic></span>. Our results improve, extend and unify results of Frieze and Jerrum, Feige and Langberg, Ye, and others. All these results may be viewed as extensions of the MAX CUT algorithm of Goemans and Williamson, and the MAX 2‐SAT and MAX DI‐CUT algorithms of Feige and Goemans. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20:382–402, 2002</p></abstract></abstractGroup></contentMeta><noteGroup><note xml:id="fn2"><p>*A preliminary version of this paper is to appear in the proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization (IPCO'01), Utrecht, The Netherlands, 2001.</p></note></noteGroup></header></component></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems</title></titleInfo><titleInfo type="abbreviated" lang="en"><title>Obtaining Improved Approximation Algorithms</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems</title></titleInfo><name type="personal"><namePart type="given">Eran</namePart><namePart type="family">Halperin</namePart><affiliation>Department of Computer Science, Tel‐Aviv University, Tel‐Aviv 69978, Israel</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Uri</namePart><namePart type="family">Zwick</namePart><affiliation>Department of Computer Science, Tel‐Aviv University, Tel‐Aviv 69978, Israel</affiliation><affiliation>Department of Computer Science, Tel‐Aviv University, Tel‐Aviv 69978, Israel</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="article" displayLabel="article"></genre><originInfo><publisher>Wiley Subscription Services, Inc., A Wiley Company</publisher><place><placeTerm type="text">New York</placeTerm></place><dateIssued encoding="w3cdtf">2002-05</dateIssued><dateCaptured encoding="w3cdtf">2001-02-18</dateCaptured><dateValid encoding="w3cdtf">2002-01-28</dateValid><copyrightDate encoding="w3cdtf">2002</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType><extent unit="figures">4</extent><extent unit="tables">3</extent><extent unit="references">23</extent><extent unit="words">9900</extent></physicalDescription><abstract lang="en">We obtain improved semidefinite programming based approximation algorithms for all the natural maximum bisection problems of graphs. Among the problems considered are: MAX$n\over 2$‐BISECTION—partition the vertices of the graph into two sets of equal size such that the total weight of edges connecting vertices from different sides is maximized; MAX$n\over 2$‐VERTEX‐COVER—find a set containing half of the vertices such that the total weight of edges touching this set is maximized; MAX$n\over 2$‐DENSE‐SUBGRAPH—find a set containing half of the vertices such that the total weight of edges connecting two vertices from this set is maximized; and MAX$n\over 2$UNCUT—partition the vertices into two sets of equal size such that the total weight of edges that do not cross the cut is maximized. We also consider the directed versions of these problems, such as MAX$n\over 2$‐DIRECTED‐BISECTION and MAX$n\over 2$‐DIRECTED‐UNCUT. These results can be used to obtain improved approximation algorithms for the unbalanced versions of the partition problems mentioned above, where we want to partition the graph into two sets of size $k$ and $n - k$, where $k$ is not necessarily $n\over 2$. Our results improve, extend and unify results of Frieze and Jerrum, Feige and Langberg, Ye, and others. All these results may be viewed as extensions of the MAX CUT algorithm of Goemans and Williamson, and the MAX 2‐SAT and MAX DI‐CUT algorithms of Feige and Goemans. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20:382–402, 2002</abstract><note type="content">**A preliminary version of this paper is to appear in the proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization (IPCO'01), Utrecht, The Netherlands, 2001.</note><relatedItem type="host"><titleInfo><title>Random Structures & Algorithms</title></titleInfo><titleInfo type="abbreviated"><title>Random Struct. Alg.</title></titleInfo><name type="personal"><namePart type="given">Tibor</namePart><namePart type="family">Jordan</namePart></name><name type="personal"><namePart type="given">Alessandro</namePart><namePart type="family">Panconesi</namePart></name><genre type="journal">journal</genre><identifier type="ISSN">1042-9832</identifier><identifier type="eISSN">1098-2418</identifier><identifier type="DOI">10.1002/(ISSN)1098-2418</identifier><identifier type="PublisherID">RSA</identifier><part><date>2002</date><detail type="title"><title>Probabilistic Methods in Combinatorial Optimization</title></detail><detail type="volume"><caption>vol.</caption><number>20</number></detail><detail type="issue"><caption>no.</caption><number>3</number></detail><extent unit="pages"><start>382</start><end>402</end><total>21</total></extent></part></relatedItem><identifier type="istex">9A0E7D1FB07BFC648A04A9C3002088E5F009AB2F</identifier><identifier type="DOI">10.1002/rsa.10035</identifier><identifier type="ArticleID">RSA10035</identifier><accessCondition type="use and reproduction" contentType="copyright">Copyright © 2002 Wiley Periodicals, Inc.</accessCondition><recordInfo><recordContentSource>WILEY</recordContentSource><recordOrigin>Wiley Subscription Services, Inc., A Wiley Company</recordOrigin></recordInfo></mods></metadata><serie></serie></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 001899 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001899 | 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:9A0E7D1FB07BFC648A04A9C3002088E5F009AB2F
|texte= A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
}}
| This area was generated with Dilib version V0.6.31. |  |