How unique is Lovász's theta function?
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | PÊCHER, Arnaud | |
| hal.structure.identifier | Research Group on Graph Theory and Combinatorics [Barcelona] | |
| dc.contributor.author | SERRA, Oriol | |
| hal.structure.identifier | Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes [LIMOS] | |
| dc.contributor.author | WAGLER, Annegret K. | |
| hal.structure.identifier | Department of Mathematics [Hangzhou] | |
| dc.contributor.author | ZHU, Xuding | |
| dc.date.accessioned | 2024-04-04T03:19:50Z | |
| dc.date.available | 2024-04-04T03:19:50Z | |
| dc.date.created | 2014-12-08 | |
| dc.date.issued | 2014-12-08 | |
| dc.date.conference | 2014-12-08 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/194543 | |
| dc.description.abstractEn | The famous Lovász's ϑ function is computable in polynomial time for every graph, as a semi-definite program (Grötschel, Lovász and Schrijver, 1981). The chromatic number and the clique number of every perfect graph G are computable in polynomial time. Despite numerous efforts since the last three decades, stimulated by the Strong Perfect Graph Theo-rem (Chudnovsky, Robertson, Seymour and Thomas, 2006), no combinatorial proof of this result is known. In this work, we try to understand why the "key properties" of Lovász's ϑ function make it so "unique". We introduce an infinite set of convex functions, which includes the clique number ω and ϑ . This set includes a sequence of linear programs which are monotone increasing and converging to ϑ . We provide some evidences that ϑ is the unique function in this setting allowing to compute the chromatic number of perfect graphs in polynomial time. | |
| dc.language.iso | en | |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/ | |
| dc.subject.en | semi-definite programming | |
| dc.subject.en | Theta number | |
| dc.title.en | How unique is Lovász's theta function? | |
| dc.type | Communication dans un congrès | |
| dc.subject.hal | Sciences de l'Homme et Société/Sciences de l'information et de la communication | |
| dc.subject.hal | Informatique [cs]/Mathématique discrète [cs.DM] | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | VIII ALIO/EURO Workshop on Applied Combinatorial Optimization | |
| bordeaux.country | UY | |
| bordeaux.conference.city | Montevideo | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-01095638 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | non | |
| hal.conference.end | 2014-12-10 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-01095638v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2014-12-08&rft.au=P%C3%8ACHER,%20Arnaud&SERRA,%20Oriol&WAGLER,%20Annegret%20K.&ZHU,%20Xuding&rft.genre=unknown |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||