On the Chvátal rank of polytopes in the 0/1 cube
Identifieur interne : 000000 ( PascalFrancis/Curation ); suivant : 000001On the Chvátal rank of polytopes in the 0/1 cube
Auteurs : A. Bockmayr [France] ; F. Eisenbrand [Allemagne] ; M. Hartmann [États-Unis] ; A. S. Schulz [États-Unis]Source :
- Discrete applied mathematics [ 0166-218X ] ; 1999.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
Given a polytope P ⊆ Rn, the Chvátal-Gomory procedure computes iteratively the integer hull P1 of P. The Chvátal rank of P is the minimal number of iterations needed to obtain P1. It is always finite, but already the Chvátal rank of polytopes in R2 can be arbitrarily large. In this paper, we study polytopes in the 0/1 cube, which are of particular interest in combinatorial optimization. We show that the Chvátal rank of any polytope P ⊆ [0,1]n is O(n3 log n) and prove the linear upper and lower bound n for the case P ∩ Zn = Ø.
pA |
|
---|
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000A82
Links to Exploration step
Pascal:00-0001592Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">On the Chvátal rank of polytopes in the 0/1 cube</title>
<author><name sortKey="Bockmayr, A" sort="Bockmayr, A" uniqKey="Bockmayr A" first="A." last="Bockmayr">A. Bockmayr</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Université Henri Poincaré, LORIA, Campus scientifique, B.P. 239</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Eisenbrand, F" sort="Eisenbrand, F" uniqKey="Eisenbrand F" first="F." last="Eisenbrand">F. Eisenbrand</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Max-Planck-Institut für Informatik, Im Stadtwald</s1>
<s2>66123 Saarbrücken</s2>
<s3>DEU</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
</affiliation>
</author>
<author><name sortKey="Hartmann, M" sort="Hartmann, M" uniqKey="Hartmann M" first="M." last="Hartmann">M. Hartmann</name>
<affiliation wicri:level="1"><inist:fA14 i1="03"><s1>University of North Carolina at Chapel Hill, Department of Operations Research</s1>
<s2>Chapel Hill, NC 27599-3180</s2>
<s3>USA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Schulz, A S" sort="Schulz, A S" uniqKey="Schulz A" first="A. S." last="Schulz">A. S. Schulz</name>
<affiliation wicri:level="1"><inist:fA14 i1="04"><s1>MIT, Sloan School of Management and Operations Research Center, E53-361</s1>
<s2>Cambridge, MA 02142</s2>
<s3>USA</s3>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">00-0001592</idno>
<date when="1999">1999</date>
<idno type="stanalyst">PASCAL 00-0001592 INIST</idno>
<idno type="RBID">Pascal:00-0001592</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000A82</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000000</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">On the Chvátal rank of polytopes in the 0/1 cube</title>
<author><name sortKey="Bockmayr, A" sort="Bockmayr, A" uniqKey="Bockmayr A" first="A." last="Bockmayr">A. Bockmayr</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Université Henri Poincaré, LORIA, Campus scientifique, B.P. 239</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Eisenbrand, F" sort="Eisenbrand, F" uniqKey="Eisenbrand F" first="F." last="Eisenbrand">F. Eisenbrand</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Max-Planck-Institut für Informatik, Im Stadtwald</s1>
<s2>66123 Saarbrücken</s2>
<s3>DEU</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
</affiliation>
</author>
<author><name sortKey="Hartmann, M" sort="Hartmann, M" uniqKey="Hartmann M" first="M." last="Hartmann">M. Hartmann</name>
<affiliation wicri:level="1"><inist:fA14 i1="03"><s1>University of North Carolina at Chapel Hill, Department of Operations Research</s1>
<s2>Chapel Hill, NC 27599-3180</s2>
<s3>USA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Schulz, A S" sort="Schulz, A S" uniqKey="Schulz A" first="A. S." last="Schulz">A. S. Schulz</name>
<affiliation wicri:level="1"><inist:fA14 i1="04"><s1>MIT, Sloan School of Management and Operations Research Center, E53-361</s1>
<s2>Cambridge, MA 02142</s2>
<s3>USA</s3>
<sZ>4 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Discrete applied mathematics</title>
<title level="j" type="abbreviated">Discrete appl. math.</title>
<idno type="ISSN">0166-218X</idno>
<imprint><date when="1999">1999</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Discrete applied mathematics</title>
<title level="j" type="abbreviated">Discrete appl. math.</title>
<idno type="ISSN">0166-218X</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Chvatal rank</term>
<term>Combinatorial optimization</term>
<term>Cube 0/1</term>
<term>Geometry</term>
<term>Integer hull</term>
<term>Polyhedron</term>
<term>Polytope</term>
<term>Polytope in 01 cube</term>
<term>Rank</term>
<term>Upper bound</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Géométrie</term>
<term>Polytope</term>
<term>Polyèdre</term>
<term>Rang</term>
<term>Borne supérieure</term>
<term>Optimisation combinatoire</term>
<term>Cube 0/1</term>
<term>Polytope dans cube 0/1</term>
<term>Rang Chvatal</term>
<term>Envéloppe entière</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Given a polytope P ⊆ R<sup>n</sup>
, the Chvátal-Gomory procedure computes iteratively the integer hull P<sub>1</sub>
of P. The Chvátal rank of P is the minimal number of iterations needed to obtain P<sub>1</sub>
. It is always finite, but already the Chvátal rank of polytopes in R<sup>2</sup>
can be arbitrarily large. In this paper, we study polytopes in the 0/1 cube, which are of particular interest in combinatorial optimization. We show that the Chvátal rank of any polytope P ⊆ [0,1]<sup>n</sup>
is O(n<sup>3</sup>
log n) and prove the linear upper and lower bound n for the case P ∩ Z<sup>n</sup>
= Ø.</div>
</front>
</TEI>
<inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0166-218X</s0>
</fA01>
<fA02 i1="01"><s0>DAMADU</s0>
</fA02>
<fA03 i2="1"><s0>Discrete appl. math.</s0>
</fA03>
<fA05><s2>98</s2>
</fA05>
<fA06><s2>1-2</s2>
</fA06>
<fA08 i1="01" i2="1" l="ENG"><s1>On the Chvátal rank of polytopes in the 0/1 cube</s1>
</fA08>
<fA11 i1="01" i2="1"><s1>BOCKMAYR (A.)</s1>
</fA11>
<fA11 i1="02" i2="1"><s1>EISENBRAND (F.)</s1>
</fA11>
<fA11 i1="03" i2="1"><s1>HARTMANN (M.)</s1>
</fA11>
<fA11 i1="04" i2="1"><s1>SCHULZ (A. S.)</s1>
</fA11>
<fA14 i1="01"><s1>Université Henri Poincaré, LORIA, Campus scientifique, B.P. 239</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</fA14>
<fA14 i1="02"><s1>Max-Planck-Institut für Informatik, Im Stadtwald</s1>
<s2>66123 Saarbrücken</s2>
<s3>DEU</s3>
<sZ>2 aut.</sZ>
</fA14>
<fA14 i1="03"><s1>University of North Carolina at Chapel Hill, Department of Operations Research</s1>
<s2>Chapel Hill, NC 27599-3180</s2>
<s3>USA</s3>
<sZ>3 aut.</sZ>
</fA14>
<fA14 i1="04"><s1>MIT, Sloan School of Management and Operations Research Center, E53-361</s1>
<s2>Cambridge, MA 02142</s2>
<s3>USA</s3>
<sZ>4 aut.</sZ>
</fA14>
<fA20><s1>21-27</s1>
</fA20>
<fA21><s1>1999</s1>
</fA21>
<fA23 i1="01"><s0>ENG</s0>
</fA23>
<fA43 i1="01"><s1>INIST</s1>
<s2>18287</s2>
<s5>354000080488120020</s5>
</fA43>
<fA44><s0>0000</s0>
<s1>© 2000 INIST-CNRS. All rights reserved.</s1>
</fA44>
<fA45><s0>13 ref.</s0>
</fA45>
<fA47 i1="01" i2="1"><s0>00-0001592</s0>
</fA47>
<fA60><s1>P</s1>
</fA60>
<fA61><s0>A</s0>
</fA61>
<fA64 i1="01" i2="1"><s0>Discrete applied mathematics</s0>
</fA64>
<fA66 i1="01"><s0>NLD</s0>
</fA66>
<fC01 i1="01" l="ENG"><s0>Given a polytope P ⊆ R<sup>n</sup>
, the Chvátal-Gomory procedure computes iteratively the integer hull P<sub>1</sub>
of P. The Chvátal rank of P is the minimal number of iterations needed to obtain P<sub>1</sub>
. It is always finite, but already the Chvátal rank of polytopes in R<sup>2</sup>
can be arbitrarily large. In this paper, we study polytopes in the 0/1 cube, which are of particular interest in combinatorial optimization. We show that the Chvátal rank of any polytope P ⊆ [0,1]<sup>n</sup>
is O(n<sup>3</sup>
log n) and prove the linear upper and lower bound n for the case P ∩ Z<sup>n</sup>
= Ø.</s0>
</fC01>
<fC02 i1="01" i2="X"><s0>001A02F02</s0>
</fC02>
<fC03 i1="01" i2="X" l="FRE"><s0>Géométrie</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="ENG"><s0>Geometry</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="SPA"><s0>Geometría</s0>
<s5>01</s5>
</fC03>
<fC03 i1="02" i2="X" l="FRE"><s0>Polytope</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="ENG"><s0>Polytope</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="SPA"><s0>Politope</s0>
<s5>02</s5>
</fC03>
<fC03 i1="03" i2="X" l="FRE"><s0>Polyèdre</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="ENG"><s0>Polyhedron</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="SPA"><s0>Poliedro</s0>
<s5>03</s5>
</fC03>
<fC03 i1="04" i2="X" l="FRE"><s0>Rang</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="ENG"><s0>Rank</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="SPA"><s0>Rango</s0>
<s5>04</s5>
</fC03>
<fC03 i1="05" i2="X" l="FRE"><s0>Borne supérieure</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="ENG"><s0>Upper bound</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="SPA"><s0>Cota superior</s0>
<s5>05</s5>
</fC03>
<fC03 i1="06" i2="X" l="FRE"><s0>Optimisation combinatoire</s0>
<s5>06</s5>
</fC03>
<fC03 i1="06" i2="X" l="ENG"><s0>Combinatorial optimization</s0>
<s5>06</s5>
</fC03>
<fC03 i1="06" i2="X" l="SPA"><s0>Optimización combinatoria</s0>
<s5>06</s5>
</fC03>
<fC03 i1="07" i2="X" l="FRE"><s0>Cube 0/1</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fC03 i1="07" i2="X" l="ENG"><s0>Cube 0/1</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fC03 i1="08" i2="X" l="FRE"><s0>Polytope dans cube 0/1</s0>
<s4>CD</s4>
<s5>97</s5>
</fC03>
<fC03 i1="08" i2="X" l="ENG"><s0>Polytope in 01 cube</s0>
<s4>CD</s4>
<s5>97</s5>
</fC03>
<fC03 i1="09" i2="X" l="FRE"><s0>Rang Chvatal</s0>
<s4>CD</s4>
<s5>98</s5>
</fC03>
<fC03 i1="09" i2="X" l="ENG"><s0>Chvatal rank</s0>
<s4>CD</s4>
<s5>98</s5>
</fC03>
<fC03 i1="10" i2="X" l="FRE"><s0>Envéloppe entière</s0>
<s4>CD</s4>
<s5>99</s5>
</fC03>
<fC03 i1="10" i2="X" l="ENG"><s0>Integer hull</s0>
<s4>CD</s4>
<s5>99</s5>
</fC03>
<fN21><s1>003</s1>
</fN21>
</pA>
</standard>
</inist>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000000 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Curation/biblio.hfd -nk 000000 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= PascalFrancis |étape= Curation |type= RBID |clé= Pascal:00-0001592 |texte= On the Chvátal rank of polytopes in the 0/1 cube }}
This area was generated with Dilib version V0.6.33. |