Algorithme d'approximation

En informatique théorique, un algorithme d'approximation est une méthode permettant de calculer une solution approchée à un problème algorithmique d'optimisation. Plus précisément, c'est une heuristique garantissant à la qualité de la solution qui fournit un rapport inférieur (si l'on minimise) à une constante, par rapport à la qualité optimale d'une solution, pour toutes les instances possibles du problème.

L'intérêt de tels algorithmes est qu'il est parfois plus facile de trouver une solution approchée qu'une solution exacte, le problème pouvant par exemple être NP-complet mais admettre un algorithme d'approximation polynomial. Ainsi, dans les situations où l'on cherche une bonne solution, mais pas forcément la meilleure, un algorithme d'approximation peut être un bon outil.

Définitions

Approximation

Selon la nature du problème (maximisation, minimisation, etc.) la définition peut varier, on donne ici la définition classique pour un problème de minimisation avec facteur d'approximation constant.

Pour un problème de minimisation ayant une solution optimale de valeur , un algorithme d'approximation de facteur (i.e. un algorithme -approché) est un algorithme donnant une solution de valeur , avec la garantie que .

Schéma d'approximation

Un schéma d'approximation est un algorithme prenant comme entrée les données du problèmes mais aussi une valeur et calculant une solution approchée avec un facteur . Si le temps de calcul est polynomial en la taille de l'entrée pour chaque valeur , on parle de schéma d'approximation en temps polynomial (abrégé PTAS en anglais). Si de plus, on demande que le temps de calcul soit aussi en , on parle de schéma d'approximation en temps entièrement polynomial (abrégé FPTAS en anglais)[1].

Exemple

Un exemple de tournée du voyageur de commerce en Allemagne.

Par exemple pour le problème du transversal minimum puisque tout transversal formé par les sommets incidents aux arêtes d'un couplage maximal pour l'inclusion a une cardinalité inférieure à deux fois l'optimum.

C'est aussi le cas pour le cas particulier du voyageur de commerce où les poids satisfont les inégalités triangulaires car alors, le poids minimum d'un arbre couvrant est toujours inférieur à deux fois l'optimum. En affinant cette approche en utilisant un couplage bien choisi on peut aussi obtenir un facteur d'approximation de 3/2, avec l'algorithme de Christofides.

Techniques algorithmiques

Parmi les techniques utilisées[2], on compte les méthodes d'algorithmique classique, par exemple un algorithme glouton permet parfois d'obtenir une bonne approximation à défaut de calculer une solution optimale. On peut aussi citer des algorithmes de recherche locale et de programmation dynamique.

Beaucoup d'algorithmes sont basées sur l'optimisation linéaire. On peut par exemple arrondir une solution fractionnaire ou utiliser un schéma primal-dual. Une technique plus avancée est d'utiliser l'optimisation SDP, comme pour le problème de la coupe maximum.

Difficulté d'approximation

Parmi les problèmes NP-complets certains sont dits difficile à approximer, c'est-à-dire qu'ils n'admettent pas d'algorithme d'approximation si l'on suppose certaines hypothèses, par exemple P différent de NP ou bien la conjecture des jeux uniques.

Exemples simples

Le problème du voyageur de commerce dans un graphe avec des poids quelconques (positifs) est un problème qui n'admet pas d'algorithme d'approximation. En effet, tout algorithme d'approximation pour ce problème dans le graphe complet où les arêtes de ont une valeur nulle et les autres la valeur 1 fournit une réponse au problème de décision NP-complet de statuer sur l'hamiltonicité d'un graphe (en l'occurrence est hamiltonien si et seulement si l'algorithme approché fournit une solution de valeur nulle).

Un autre problème est le problème du k-centre métrique qui admet une réduction simple au problème de l'ensemble dominant[3].

Techniques avancées

Il existe des techniques plus complexes pour montrer des résultats de difficulté d'approximation. Elles tournent essentiellement autour du théorème PCP. Plus récemment la conjecture des jeux uniques a été utilisée pour montrer des résultats plus forts.

Historique

Des algorithmes d'approximation ont été découverts avant même la mise en place de la théorie de la NP-complétude[4], par exemple par Paul Erdős dans les années 1960, pour le problème de la coupe maximum[5] ou Ronald Graham, pour les algorithmes d'ordonnancement [6],[7] . Cependant c'est à la suite de cette théorie que le domaine s'est vraiment développé[4]. L'utilisation de l'optimisation linéaire est due à László Lovász dans les années 1970[4], pour le problème de couverture par ensembles[8].

Dans les années 1990, le théorème PCP a été une avancée très importante pour la non-approximabilité.

Notes et références

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, [détail de l’édition], chap. 35.
  2. David P. Williamson et David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press (lire en ligne)
  3. Voir (en) Vijay Vazirani, Approximation algorithms, Springer Verlag, 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), chap. 5 (« k-center »)
  4. a b et c (en) Vijay Vazirani, Approximation algorithms, Springer Verlag, 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), chap. 1.4 (« Introduction : Notes ») p. 10.
  5. Paul Erdős, « Gráfok páros körüljárású részgráfjairól (On bipartite subgraphs of graphs, in Hungarian), », Mat. Lapok, vol. 18,‎ , p. 283-288
  6. R. L. Graham, « Bounds for certain multiprocessing anomalies », Bell System Technical Journal, vol. 45, no 9,‎ , p. 1563–1581 (DOI 10.1002/j.1538-7305.1966.tb01709.x, lire en ligne)
  7. R. L. Graham, « Bounds on multiprocessing timing anomalies », SIAM Journal on Applied Mathematics, vol. 17,‎ , p. 416–429 (DOI 10.1137/0117039, MR 249214, lire en ligne)
  8. László Lovász, « On the ratio of optimal integral and fractional covers », Discrete mathematics, vol. 13, no 4,‎ , p. 383-390

Read other articles:

Labeobarbus varicostoma Varicorhinus varicostoma TaksonomiKerajaanAnimaliaFilumChordataKelasActinopteriOrdoCypriniformesFamiliCyprinidaeGenusVaricorhinusSpesiesVaricorhinus varicostoma Tata namaSinonim takson Varicorhinus varicostoma lbs Labeobarbus varicostoma adalah sebuah spesies ikan bersirip kipas dalam genus Labeobarbus. Spesies tersebut adalah endemik di Sungai Lucalla, Angola.[1] Referensi ^ Froese, Rainer and Pauly, Daniel, eds. (2006). Labeobarbus varicostoma di situs FishBa...

 

« Lyotard » redirige ici. Pour l’article homophone, voir Liotard. Jean-François LyotardJean-François Lyotard en 1995.BiographieNaissance 10 août 1924Versailles (France)Décès 21 avril 1998 (à 73 ans)Paris 15e (France)Sépulture Cimetière du Père-Lachaise, Grave of Jean-François Lyotard (d)Pseudonyme François LabordeÉpoque Philosophie contemporaineNationalité françaiseFormation Lycée Louis-le-GrandAgrégation de philosophieUniversité de ParisUniversité P...

 

Untuk berbagai daftar negara menurut ciri-ciri tertentu, lihat Daftar negara. Berikut ini merupakan daftar yang menampilkan ikhtisar mengenai negara-negara berdaulat di seluruh dunia, beserta informasi mengenai status dan pengakuan atas kedaulatan negara-negara tersebut. Daftar tersebut memuat sejumlah 206 negara berdaulat yang dapat dikelompokkan berdasarkan keanggotaannya dalam Sistem Perserikatan Bangsa-Bangsa, yaitu: 193 negara anggota PBB,[1] dua negara pengamat nonanggota Majeli...

Department of France in Bourgogne-Franche-Comté For other places with the same name, see Jura (disambiguation). Not to be confused with the Swiss Republic and Canton of Jura. Department of France in Bourgogne-Franche-ComtéJuraDepartment of France From top down, left to right: Lac de Vouglans, Baume-les-Messieurs, Poligny, Lac de Bonlieu, Lac de l'Abbaye, Les Planches-près-Arbois, Chancia FlagCoat of armsLocation of Jura in FranceCoordinates: 46°40′31″N 5°33′16″E / ...

 

رابح سعدان معلومات شخصية الاسم الكامل رابح سعدان الميلاد 3 مايو 1946 (العمر 77 سنة)باتنة الطول 1.75 م (5 قدم 9 بوصة) مركز اللعب مدافع الجنسية  الجزائر اللقب الشيخ مسيرة الشباب سنوات فريق مولودية باتنة المسيرة الاحترافية1 سنوات فريق مشاركات (أهداف) 1964–1968 مولودية باتنة 150 ...

 

Pour les articles homonymes, voir Bassin minier du Nord-Pas-de-Calais (homonymie). Houillères du bassin du Nord et du Pas-de-Calais Création 1946 Dates clés 1990 : fermeture des Houillères du Nord-Pas-de-Calais2004 : fermeture du dernier charbonnage Disparition 1er janvier 1993 (dissolution administrative) Fondateurs État français Personnages clés Paul Gardent, Max Hecquet... (directeurs généraux), Yvon Morandat ; Pierre Delmon ; Jacques Ragot[1] (Présidents)......

Alessio Vita Nazionalità  Italia Altezza 178 cm Peso 67 kg Calcio Ruolo Centrocampista, difensore Squadra  Cittadella Carriera Giovanili 2009-2012 Torino Squadre di club1 2012-2015 Monza82 (23)[1]2015 Sassuolo0 (0)2015-2017→  Vicenza77 (2)[2]2017-2018 Cesena31 (0)2018-2019 Feralpisalò35 (4)[3]2019- Cittadella155 (12)[4] Nazionale 2013 Italia U-20 Lega Pro4 (0) 1 I due numeri indicano le presenze e le reti segnat...

 

The DaysSingel oleh Aviciidari album mini The Days / Nights EPDirilis03 Oktober 2014 (2014-10-03)Direkam2014GenreFolktronicasoulhouseDurasi4:38LabelPRMDUniversalPenciptaBrandon FlowersSalem Al FakirTim BerglingRobbie WilliamsVincent PontareProduserSalem Al FakirAviciiVincent PontareKronologi singel Avicii Dar um Jeito (We Will Find a Way) (2014) The Days (2014) Divine Sorrow (2014) Kronologi singel Robbie Williams Shine My Shoes(2014) The Days(2014) Party Like a Russian(2016) V...

 

Chinese food often eaten at Ching Ming Festival PopiahCloseup of a popiah roll with a filling of bean sprouts and other ingredientsAlternative namespo̍h-piáⁿPlace of originFujian, ChinaRegion or stateEast Asia (Teochew and Hokkien-speaking communities), Southeast AsiaAssociated cuisineSingapore, Indonesia, Malaysia, Mainland China, Taiwan, Thailand, Vietnam, Philippines, Myanmar, CambodiaMain ingredientsPopiah skin, bean sauce, filling of finely grated and steamed or stir-fried turnip, ji...

Battlefield EarthPoster rilis teatrikalSutradaraRoger ChristianProduserJonathan KraneElie SamahaJohn TravoltaSkenarioCorey MandellJ. D. ShapiroBerdasarkanBattlefield Eartholeh L. Ron HubbardPemeranJohn TravoltaBarry PepperForest WhitakerKim CoatesSabine KarsentiRichard TysonPenata musikElia CmiralSinematograferGiles NuttgensPenyuntingRobin RussellPerusahaanproduksiMorgan Creek ProductionsFranchise PicturesDistributorWarner Bros. PicturesTanggal rilis 12 Mei 2000 (2000-05-12) Durasi...

 

Masjid Langgar Tinggi, tahun 1949 Masjid Langgar Tinggi, 2019 Masjid Langgar Tinggi, lk. tahun 1900, tatkala Kali Angke masih berfungsi sebagai jalur transportasi Masjid Langgar Tinggi adalah salah satu masjid tua di wilayah DKI Jakarta. Masjid yang terletak di Kelurahan Pekojan, Kecamatan Tambora, Jakarta Barat, ini semula dibangun sebagai langgar oleh seorang orang Arab pada tahun 1249 H atau 1829 M. Sejarah Pada papan di atas pintu masuk masjid ditulis bahwa Masjid Langgar Tinggi didirikan...

 

213th Rifle DivisionActive1941–1946CountrySoviet UnionBranchRed ArmyTypeInfantryRoleMotorized InfantrySizeDivisionEngagementsWorld War IIBattle honoursNovoukrainkaCommandersNotablecommandersIvan BuslayevMilitary unit The 213th Rifle Division (Russian: 213-я стрелковая дивизия) was formed as an infantry division of the Red Army during World War II after a motorized division of that same number was destroyed about seven weeks following the start of the German invasion o...

1966 film by Blake Edwards Not to be confused with Daddy, what did you do in the Great War?. What Did You Do in the War, Daddy?Theatrical release posterDirected byBlake EdwardsScreenplay byWilliam Peter BlattyStory byMaurice RichlinBlake EdwardsProduced byBlake EdwardsStarringJames CoburnAldo RayDick ShawnSergio FantoniGiovanna RalliCarroll O'ConnorHarry MorganCinematographyPhilip H. LathropEdited byRalph E. WintersMusic byRay EvansJay LivingstonHenry ManciniProductioncompanyThe Mirisch Compa...

 

犹太人יהודים‎(Yehudim)雅各耶稣大卫王爱因斯坦马克思迈蒙尼德弗拉维奥·约瑟夫斯弗洛伊德斯宾诺莎本-古里安西奥多·赫茨尔娜塔莉·波特曼弗里茨·哈伯冯诺依曼門德爾頌谢尔盖·布林罗莎·卢森堡莉泽·迈特纳乔姆斯基维特根斯坦大卫·李嘉图尼尔斯·玻尔赛尔曼·瓦克斯曼卡夫卡史翠珊泽连斯基罗莎琳德·富兰克林古斯塔夫·马勒普鲁斯特卡米耶·毕沙罗涂尔干摩西...

 

Seri Dragon BallGambar sampul Tenkaichi Budokai Dimulai.MangaAlbum nomor3EpisodeDrgaon Ball SagaDidahului olehKemelut Dragon BallDiikuti denganPendekar TangguhDiterbitkan di Jepang1984Diterbitkan di Indonesia1992 Tenkaichi Budokai Dimulai adalah jilid ke-3 manga Dragon Ball. Pada jilid ini, Goku ingin menjadi lebih kuat dan meminta Kamesennin mengajarnya. Ia mendapat saingan dari seorang biksu muda yang bernama Krillin. Beberapa bulan kemudian, guru mereka mendaftarkan Goku dan Krillin ke Ten...

土库曼斯坦总统土库曼斯坦国徽土库曼斯坦总统旗現任谢尔达尔·别尔德穆哈梅多夫自2022年3月19日官邸阿什哈巴德总统府(Oguzkhan Presidential Palace)機關所在地阿什哈巴德任命者直接选举任期7年,可连选连任首任萨帕尔穆拉特·尼亚佐夫设立1991年10月27日 土库曼斯坦土库曼斯坦政府与政治 国家政府 土库曼斯坦宪法 国旗 国徽 国歌 立法機關(英语:National Council of Turkmenistan) ...

 

Cet article est une ébauche concernant une équipe nationale de football. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Équipe de France de football à la Coupe des confédérations 2003 Fédération FIFA Organisateur(s) France Participation 2e Meilleure performance Vainqueur en 2001 Sélectionneur Jacques Santini Maillots Domicile Extérieur Équipe de France de football 2001 2021 modifier  Cet article...

 

US-based worldwide management consulting firm McKinsey redirects here. For other uses, see McKinsey (disambiguation). McKinsey & CompanyMcKinsey's New York office are in five floors of 3 World Trade CenterCompany typePrivateIndustryManagement consultingFounded1926; 98 years ago (1926)FounderJames O. McKinseyHeadquartersNew York City[1]Area servedWorldwideKey peopleBob Sternfels,Global Managing Partner[2]Revenue $15+ billion (2021)[3]Number of empl...

Share of crimes which are alcohol-related Criminal activities that involve alcohol use Alcohol-related crime refers to criminal activities that involve alcohol use as well as violations of regulations covering the sale or use of alcohol; in other words, activities violating the alcohol laws.[1][2] Underage drinking and drunk driving are the most prevalent alcohol‐specific offenses in the United States[1] and a major problem in many, if not most, countries worldwide.&...

 

الجوهر المنظم في زيارة القبر المكرم غلاف الكتاب معلومات الكتاب المؤلف ابن حجر الهيتمي( - 974هـ) اللغة العربية الموضوع فقه إسلامي مؤلفات أخرى تحفة الزوار إلى قبر النبي المختار • الإمداد بشرح الإرشاد • فتح الجواد بشرح الإرشاد تعديل مصدري - تعديل   الجوهر المنظم في زيارة الق...