A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
Identifieur interne : 001F14 ( Main/Merge ); précédent : 001F13; suivant : 001F15A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
Auteurs : Eran Halperin [Israël] ; Uri Zwick [Israël]Source :
- 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 toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001899
- to stream Istex, to step Curation: 001783
- to stream Istex, to step Checkpoint: 000B74
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>
</author>
<author><name sortKey="Zwick, Uri" sort="Zwick, Uri" uniqKey="Zwick U" first="Uri" last="Zwick">Uri Zwick</name>
</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>
<idno type="wicri:Area/Istex/Curation">001783</idno>
<idno type="wicri:Area/Istex/Checkpoint">000B74</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000B74</idno>
<idno type="wicri:doubleKey">1042-9832:2002:Halperin E:a:unified:framework</idno>
<idno type="wicri:Area/Main/Merge">001F14</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 wicri:level="1"><country xml:lang="fr">Israël</country>
<wicri:regionArea>Department of Computer Science, Tel‐Aviv University, Tel‐Aviv 69978</wicri:regionArea>
<wicri:noRegion>Tel‐Aviv 69978</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Zwick, Uri" sort="Zwick, Uri" uniqKey="Zwick U" first="Uri" last="Zwick">Uri Zwick</name>
<affiliation wicri:level="1"><country xml:lang="fr">Israël</country>
<wicri:regionArea>Department of Computer Science, Tel‐Aviv University, Tel‐Aviv 69978</wicri:regionArea>
<wicri:noRegion>Tel‐Aviv 69978</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country xml:lang="fr">Israël</country>
<wicri:regionArea>Department of Computer Science, Tel‐Aviv University, Tel‐Aviv 69978</wicri:regionArea>
<wicri:noRegion>Tel‐Aviv 69978</wicri:noRegion>
</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>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001F14 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 001F14 | 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= Merge |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. |