<?xml version="1.0" encoding="utf-8"?>
<TEI xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:hal="http://hal.archives-ouvertes.fr/" xmlns:gml="http://www.opengis.net/gml/3.3/" xmlns:gmlce="http://www.opengis.net/gml/3.3/ce" version="1.1" xsi:schemaLocation="http://www.tei-c.org/ns/1.0 http://api.archives-ouvertes.fr/documents/aofr-sword.xsd">
  <teiHeader>
    <fileDesc>
      <titleStmt>
        <title>HAL TEI export of hal-01320412</title>
      </titleStmt>
      <publicationStmt>
        <distributor>CCSD</distributor>
        <availability status="restricted">
          <licence target="https://creativecommons.org/publicdomain/zero/1.0/">CC0 1.0 - Universal</licence>
        </availability>
        <date when="2026-05-17T21:51:53+02:00"/>
      </publicationStmt>
      <sourceDesc>
        <p part="N">HAL API Platform</p>
      </sourceDesc>
    </fileDesc>
  </teiHeader>
  <text>
    <body>
      <listBibl>
        <biblFull>
          <titleStmt>
            <title xml:lang="en">Improved compact formulations for metric and cut polyhedra</title>
            <author role="aut">
              <persName>
                <forename type="first">Viet Hung</forename>
                <surname>Nguyen</surname>
              </persName>
              <idno type="halauthorid">20692-0</idno>
              <affiliation ref="#struct-394573"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Michel</forename>
                <surname>Minoux</surname>
              </persName>
              <email type="md5">23784359b19345768a10a50e0eeac2cd</email>
              <email type="domain">lip6.fr</email>
              <idno type="idhal" notation="numeric">846863</idno>
              <idno type="halauthorid" notation="string">235504-846863</idno>
              <idno type="IDREF">https://www.idref.fr/027031241</idno>
              <affiliation ref="#struct-394573"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Dang Phuong</forename>
                <surname>Nguyen</surname>
              </persName>
              <idno type="halauthorid">956177-0</idno>
              <affiliation ref="#struct-40217"/>
            </author>
            <editor role="depositor">
              <persName>
                <forename>Viet Hung</forename>
                <surname>Nguyen</surname>
              </persName>
              <email type="md5">e641c0050502355d3a2eaa4d21509966</email>
              <email type="domain">uca.fr</email>
            </editor>
          </titleStmt>
          <editionStmt>
            <edition n="v1" type="current">
              <date type="whenSubmitted">2016-05-23 19:00:43</date>
              <date type="whenModified">2024-12-12 10:28:44</date>
              <date type="whenReleased">2016-05-23 19:00:43</date>
              <date type="whenProduced">2016-06</date>
            </edition>
            <respStmt>
              <resp>contributor</resp>
              <name key="430623">
                <persName>
                  <forename>Viet Hung</forename>
                  <surname>Nguyen</surname>
                </persName>
                <email type="md5">e641c0050502355d3a2eaa4d21509966</email>
                <email type="domain">uca.fr</email>
              </name>
            </respStmt>
          </editionStmt>
          <publicationStmt>
            <distributor>CCSD</distributor>
            <idno type="halId">hal-01320412</idno>
            <idno type="halUri">https://hal.sorbonne-universite.fr/hal-01320412</idno>
            <idno type="halBibtex">nguyen:hal-01320412</idno>
            <idno type="halRefHtml">&lt;i&gt;Electronic Notes in Discrete Mathematics&lt;/i&gt;, 2016, 52, pp.125-132. &lt;a target="_blank" href="https://dx.doi.org/10.1016/j.endm.2016.03.017"&gt;&amp;#x27E8;10.1016/j.endm.2016.03.017&amp;#x27E9;&lt;/a&gt;</idno>
            <idno type="halRef">Electronic Notes in Discrete Mathematics, 2016, 52, pp.125-132. &amp;#x27E8;10.1016/j.endm.2016.03.017&amp;#x27E9;</idno>
            <availability status="restricted"/>
          </publicationStmt>
          <seriesStmt>
            <idno type="stamp" n="CEA">CEA - Commissariat à l'énergie atomique</idno>
            <idno type="stamp" n="UPMC" corresp="SORBONNE-UNIVERSITE">Université Pierre et Marie Curie</idno>
            <idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
            <idno type="stamp" n="LIP6" corresp="SORBONNE-UNIVERSITE">Laboratoire d'Informatique de Paris 6</idno>
            <idno type="stamp" n="DRT" corresp="CEA">Direction de la recherche technologique</idno>
            <idno type="stamp" n="TDS-MACS">Réseau de recherche en Théorie des Systèmes Distribués, Modélisation, Analyse et Contrôle des Systèmes</idno>
            <idno type="stamp" n="UPMC_POLE_1" corresp="UPMC">UPMC Pôle 1</idno>
            <idno type="stamp" n="LIST" corresp="CEA">Laboratoire d'Intégration des Systèmes et des Technologies</idno>
            <idno type="stamp" n="SORBONNE-UNIVERSITE">Sorbonne Université</idno>
            <idno type="stamp" n="SU-SCIENCES" corresp="SORBONNE-UNIVERSITE">Faculté des Sciences de Sorbonne Université</idno>
            <idno type="stamp" n="GS-ENGINEERING">Graduate School Sciences de l'Ingénierie et des Systèmes</idno>
            <idno type="stamp" n="GS-COMPUTER-SCIENCE">Graduate School Computer Science</idno>
            <idno type="stamp" n="GS-SPORT-HUMAN-MOVEMENT">Graduate School Sport, Mouvement, Facteurs Humains</idno>
            <idno type="stamp" n="ALLIANCE-SU"> Alliance Sorbonne Université</idno>
          </seriesStmt>
          <notesStmt>
            <note type="audience" n="2">International</note>
            <note type="popular" n="0">No</note>
            <note type="peer" n="1">Yes</note>
          </notesStmt>
          <sourceDesc>
            <biblStruct>
              <analytic>
                <title xml:lang="en">Improved compact formulations for metric and cut polyhedra</title>
                <author role="aut">
                  <persName>
                    <forename type="first">Viet Hung</forename>
                    <surname>Nguyen</surname>
                  </persName>
                  <idno type="halauthorid">20692-0</idno>
                  <affiliation ref="#struct-394573"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Michel</forename>
                    <surname>Minoux</surname>
                  </persName>
                  <email type="md5">23784359b19345768a10a50e0eeac2cd</email>
                  <email type="domain">lip6.fr</email>
                  <idno type="idhal" notation="numeric">846863</idno>
                  <idno type="halauthorid" notation="string">235504-846863</idno>
                  <idno type="IDREF">https://www.idref.fr/027031241</idno>
                  <affiliation ref="#struct-394573"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Dang Phuong</forename>
                    <surname>Nguyen</surname>
                  </persName>
                  <idno type="halauthorid">956177-0</idno>
                  <affiliation ref="#struct-40217"/>
                </author>
              </analytic>
              <monogr>
                <idno type="halJournalId" status="VALID">114022</idno>
                <idno type="issn">1571-0653</idno>
                <title level="j">Electronic Notes in Discrete Mathematics</title>
                <imprint>
                  <publisher>Elsevier</publisher>
                  <biblScope unit="volume">52</biblScope>
                  <biblScope unit="pp">125-132</biblScope>
                  <date type="datePub">2016-06</date>
                  <date type="dateEpub">2016-06</date>
                </imprint>
              </monogr>
              <idno type="doi">10.1016/j.endm.2016.03.017</idno>
            </biblStruct>
          </sourceDesc>
          <profileDesc>
            <langUsage>
              <language ident="en">English</language>
            </langUsage>
            <textClass>
              <keywords scheme="author">
                <term xml:lang="en"> extended formulation</term>
                <term xml:lang="en"> maxcut problem</term>
                <term xml:lang="en"> triangle inequalities</term>
                <term xml:lang="en">   metric polytope</term>
              </keywords>
              <classCode scheme="halDomain" n="info.info-dm">Computer Science [cs]/Discrete Mathematics [cs.DM]</classCode>
              <classCode scheme="halDomain" n="info">Computer Science [cs]</classCode>
              <classCode scheme="halDomain" n="math.math-oc">Mathematics [math]/Optimization and Control [math.OC]</classCode>
              <classCode scheme="halTypology" n="ART">Journal articles</classCode>
              <classCode scheme="halOldTypology" n="ART">Journal articles</classCode>
              <classCode scheme="halTreeTypology" n="ART">Journal articles</classCode>
            </textClass>
            <abstract xml:lang="en">
              <p>Given a graph G=(V,E)G=(V,E) with |V|=n|V|=n and |E|=m|E|=m, we consider the metric cone MET(G) and the metric polytope METP(G  ) defined on RERE. These polyhedra are relaxations of several important problems in combinatorial optimization such as the max-cut problem and the multicommodity flow problem. They are known to have non-compact formulations via the cycle inequalities in the original space RERE and compact (i.e. polynomial size) extended formulations via the triangle inequalities defined on the complete graph KnKn. In this paper, we show that one can reduce the number of triangle inequalities to O(nm)O(nm) and still have extended formulations for MET(G) and METP(G  ). This is particularly interesting for sparse graphs when m=O(n)m=O(n).</p>
            </abstract>
          </profileDesc>
        </biblFull>
      </listBibl>
    </body>
    <back>
      <listOrg type="structures">
        <org type="researchteam" xml:id="struct-394573" status="OLD">
          <orgName>DECISION</orgName>
          <date type="start">2004-01-01</date>
          <date type="end">2017-12-31</date>
          <desc>
            <address>
              <country key="FR"/>
            </address>
          </desc>
          <listRelation>
            <relation active="#struct-233" type="direct"/>
            <relation active="#struct-93591" type="indirect"/>
            <relation name="UMR7606" active="#struct-441569" type="indirect"/>
          </listRelation>
        </org>
        <org type="laboratory" xml:id="struct-40217" status="VALID">
          <idno type="IdRef">156836882</idno>
          <idno type="ISNI">0000 0004 0405 1788</idno>
          <idno type="RNSR">200118591H</idno>
          <idno type="ROR">https://ror.org/000dbcc61</idno>
          <idno type="Wikidata">Q30299467</idno>
          <orgName>Laboratoire d'Intégration des Systèmes et des Technologies</orgName>
          <orgName type="acronym">LIST (CEA)</orgName>
          <desc>
            <address>
              <addrLine>DRT/LISTNano-INNOVAvenue de la Vauve91120 Palaiseau</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www-list.cea.fr/</ref>
          </desc>
          <listRelation>
            <relation name="DRT/LIST" active="#struct-440043" type="direct"/>
            <relation name="DRT" active="#struct-300016" type="indirect"/>
          </listRelation>
        </org>
        <org type="laboratory" xml:id="struct-233" status="OLD">
          <idno type="RNSR">199712651U</idno>
          <idno type="ROR">https://ror.org/05krcen59</idno>
          <orgName>Laboratoire d'Informatique de Paris 6</orgName>
          <orgName type="acronym">LIP6</orgName>
          <date type="start">1997-01-01</date>
          <date type="end">2017-12-31</date>
          <desc>
            <address>
              <addrLine>4 Place JUSSIEU 75252 PARIS CEDEX 05</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.lip6.fr/</ref>
          </desc>
          <listRelation>
            <relation active="#struct-93591" type="direct"/>
            <relation name="UMR7606" active="#struct-441569" type="direct"/>
          </listRelation>
        </org>
        <org type="institution" xml:id="struct-93591" status="OLD">
          <idno type="ROR">https://ror.org/02en5vm52</idno>
          <orgName>Université Pierre et Marie Curie - Paris 6</orgName>
          <orgName type="acronym">UPMC</orgName>
          <date type="end">2017-12-31</date>
          <desc>
            <address>
              <addrLine>4 place Jussieu - 75005 Paris</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.upmc.fr/</ref>
          </desc>
        </org>
        <org type="regroupinstitution" xml:id="struct-441569" status="VALID">
          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <idno type="ROR">https://ror.org/02feahw73</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>
            <address>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.cnrs.fr/</ref>
          </desc>
        </org>
        <org type="regrouplaboratory" xml:id="struct-440043" status="VALID">
          <idno type="IdRef">067087930</idno>
          <idno type="ISNI">0000000121157881</idno>
          <idno type="RNSR">199018589D</idno>
          <idno type="ROR">https://ror.org/02ggzyd20</idno>
          <idno type="Wikidata">Q30299418</idno>
          <orgName>Direction de Recherche Technologique (CEA)</orgName>
          <orgName type="acronym">DRT (CEA)</orgName>
          <desc>
            <address>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.drt-cea.com/</ref>
          </desc>
          <listRelation>
            <relation name="DRT" active="#struct-300016" type="direct"/>
          </listRelation>
        </org>
        <org type="institution" xml:id="struct-300016" status="VALID">
          <idno type="IdRef">026372061</idno>
          <idno type="ISNI">0000000122998025</idno>
          <idno type="ROR">https://ror.org/00jjx8s55</idno>
          <idno type="Wikidata">Q868550</idno>
          <orgName>Commissariat à l'énergie atomique et aux énergies alternatives</orgName>
          <orgName type="acronym">CEA</orgName>
          <desc>
            <address>
              <addrLine>Centre de SaclayCentre de GrenobleCentre de Cadaracheetc</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.cea.fr/</ref>
          </desc>
        </org>
      </listOrg>
    </back>
  </text>
</TEI>