K-médiane

Le problème k-médiane, ou k-median en anglais[1], est un problème d'optimisation combinatoire, une branche de l'algorithmique. Le problème peut se décrire de façon informelle ainsi : étant donné n villes, il faut ouvrir un magasin dans k villes, tel que la moyenne des distances entre les villes et leurs plus proches magasins soit minimisée. Ce problème, proche du problème des k-moyennes, permet entre autres de faire du partitionnement de données.

Une formalisation du problème est la suivante. Étant donné un ensemble de points V, de choisir un sous-ensemble de k points, appelés centres, tel que la moyenne des distances des points de V au plus proche centre soit minimisée. Le problème est le plus souvent exprimé dans un espace métrique. Il s'exprime alors naturellement comme un problème sur un graphe dont les arêtes ont des poids respectant l'inégalité triangulaire. On peut aussi considérer que les sommets sont divisés en deux catégories : les sommets ouvrables, et les sommets à couvrir.

Ce problème est surtout étudié du point de vue de l'approximation. Il en existe plusieurs variantes, avec des métriques particulières, ou d'autres coûts à minimiser.

Définition formelle

Le problème s'exprime de la façon suivante.

Étant donné un entier k et un graphe complet non-orienté G = (V, E) dont les distances d(vi, vj) ∈ N respectent l'inégalité triangulaire, trouver un sous-ensemble S ⊆ V avec |S| = k qui minimise: . Autrement dit on considère le problème d'optimisation dont la fonction objectif est .

Approximation

Le problème k-médiane est NP-difficile même dans le cas métrique. Il possède une assez large littérature pour l'approximation dans le cas métrique (le cas général n'est pas dans APX).

Plusieurs méthodes ont été utilisées, notamment l'optimisation linéaire[2] et la recherche locale[3].

Variantes, problèmes liés et applications

Une façon classique de modifier le problème est de rajouter des capacités différentes aux centres. Ainsi un certain nœud, s'il est choisi comme centre, ne pourra servir qu'un nombre restreint de voisins.

Le problème k-centre, utilise le même cadre, mais avec une autre fonction à minimiser. Dans le problème de l'emplacement d'installations (facility location problem[1]), on remplace le paramètre k par des coûts d'ouverture et de liaison.

La calcul d'une k-médiane peut permettre de faire du partitionnement de données. Les distances représentent alors des similarités.

Notes et références

  1. ↑ a et b La traduction en français provient de la traduction par Nicolas Shabanel de (en) Vijay Vazirani, Approximation algorithms, Springer Verlag, 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), voir « Algorithmes d'approximation : table des matières », sur le site de Nicolas Schabanel.
  2. ↑ Kamal Jain et Vijay Vazirani, « Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation, », Journal of the ACM (JACM), vol. 48, no 2,‎ , p. 274-296
  3. ↑ Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala et Vinayaka Pandit, « Local search heuristics for k-median and facility location problems », SIAM Journal on Computing, vol. 33, no 3,‎ , p. 544-562

Liens externes

Read other articles:

Eugen York

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada November 2022. Eugen YorkLahir(1912-11-26)26 November 1912Rybinsk, Kekaisaran RusiaMeninggal18 November 1991(1991-11-18) (umur 78)Berlin, JermanPekerjaanSutradaraPenulis naskahTahun aktif1938-1984 Eugen York (26 November 1912 – 18 November ...

 

Kha dengan diakritik penurun

Artikel ini bukan mengenai Huruf Kiril Kha dengan kait (Ӽ). Huruf KirilKha dengan diakritik penurun Alfabet KirilHuruf SlaviaАА́А̀А̂А̄ӒБВГҐДЂЃЕЕ́ÈЕ̂ЁЄЖЗЗ́ЅИИ́ЍИ̂ЙІЇЈКЛЉМНЊОŌПРСС́ТЋЌУУ́ У̀У̂ӮЎФХЦЧЏШЩЪЫЬЭЮЯHuruf non-SlaviaӐА̊А̃Ӓ̄ӔӘӘ́Ә̃ӚВ̌ҒГ̑Г̣Г̌ҔӺҒ̌ӶД̌Д̣Д̆ӖЕ̄Е̃Ё̄Є̈ӁҖӜҘӞЗ̌З̱З̣ԐԐ̈ӠӢИ̃ҊӤҚӃҠҞҜК̣ԚӅԮԒӍӉҢԨӇҤО́О̀О̆О̂О̃ӦӦ̄ӨӨ̄Ө́Ө...

 

Gina Lollobrigida

Gina LollobrigidaOMRILollobrigida pada tahun 1960-anLahirLuigia Lollobrigida(1927-07-04)4 Juli 1927Subiaco, Kerajaan ItaliaMeninggal16 Januari 2023(2023-01-16) (umur 95)Roma, ItaliaPekerjaanAktris, jurnalis fotoTahun aktif1946–1997Suami/istriMilko Škofič ​ ​(m. 1949; c. 1971)​PasanganJavier Rigau i Ràfols (1984–2006)Anak1PenghargaanOrder of Merit of the Italian RepublicLegion of HonourOrdre des Arts et des Lettres Luigia Gina L...

Gurita pasifik utara

gurita pasifik utara di perairan california Gurita Pasifik Utara (Octopus dofleini) adalah salah satu mahluk laut terbesar di Samudra Pasifik utara dan barat laut, kepulauan Aleutian – Jepang hingga California Selatan – Alaska. Berat 10kg – 50kg (22-110lbs) dan panjang 3-5 meter (9.75-16ft). Umur rata-rata 3-5 tahun. Gurita pasifik terbesar tangan/tentakel dapat mencapai 10 meter (33-60ft) dan berat 272kg (600lbs). Merupakan hewan tak bertulang belakang (Invertebrata) dan pemakan daging...

 

Mars 7

1973–74 USSR unmanned space mission consisting of a Mars orbiter and lander Mars 7Mission typeMars flyby/lander[1]OperatorLavochkinCOSPAR IDBus: 1973-053ALander: 1973-053D[2]SATCAT no.Bus: 6776Lander: 7224[2]Mission duration7 months (launch to nearest approach) Spacecraft propertiesSpacecraft3MP No.51PManufacturerLavochkinLaunch mass3,260 kg (fueled lander and bus)[2] Start of missionLaunch date9 August 1973, 17:00:17 (1973-08-09UTC17:00:17Z) UTC ...

 

العلاقات الجزائرية الكورية الشمالية

العلاقات الجزائرية الكورية الشمالية الجزائر كوريا الشمالية   الجزائر   كوريا الشمالية تعديل مصدري - تعديل   العلاقات الجزائرية الكورية الشمالية هي العلاقات الثنائية التي تجمع بين الجزائر وكوريا الشمالية.[1][2][3][4][5] مقارنة بين البلدين هذه �...

Cultural influence of Star Trek

Star Trek influence on society A group photo of people costumed as Star Trek characters at San Diego Comic-Con 2008 The science fiction multimedia franchise of Star Trek since its original debut in 1966 has been one of the most successful television series in science fiction television history and has been considered by many to have had a large influence in popular culture as a result.[1][2][3] The original series, which aired in the late 1960s, has since spawned ten s...

 

محمد الجسر

محمد الجسر رئيس مجلس النواب اللبناني في المنصب18 أكتوبر 1927 – 10 مايو 1932 معلومات شخصية الميلاد سنة 1881   طرابلس  تاريخ الوفاة سنة 1934 (52–53 سنة)  الحياة العملية المهنة عالم مسلم،  وسياسي  تعديل مصدري - تعديل   محمد بن حسين بن محمد الجسر الصيادي الرفاعي سياسي لبنان...

 

Ace Ventura: When Nature Calls

Ace Ventura: When Nature CallsPoster Ace Ventura: When Nature CallsSutradaraSteve OedekerkProduserGary BarberBob IsraelAndrew G. La MarcaJames G. RobinsonDitulis olehJack Bernstein (karakter)Steve OedekerkPemeranJim CarreyIan McNeiceSimon CallowMaynard EziashiBob GuntonSophie OkonedoTommy DavidsonPenata musikRobert FolkSinematograferDonald E. ThorinPenyuntingMalcom CampbellPerusahaanproduksiMorgan Creek ProductionsO EntertainmentDistributorWarner Bros. PicturesTanggal rilis 10 November ...

Education in Australia

Overview of education in Australia Education in AustraliaAustralian GovernmentMinister for EducationJason ClareNational education budget (2015)BudgetA$111.8 billion[1]5.9 percent of GDPGeneral detailsPrimary languagesEnglishSystem typeState[2]Established compulsory education1830s[3]1870s[3]Literacy (2003)Total99%[4]Male99%[4]Female99%[4]Enrollment (2008)Total20.4% of population[5][6]Primary1.9 million[5]...

 

Love Street (stadium)

Former football stadium in Paisley, Scotland For the current ground of St Mirren F.C. on Greenhill Road, Paisley, see St Mirren Park. This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Love Street stadium – news · newspapers · books · scholar · JSTOR (October 2008) (Learn how and when to remove this messag...

 

Alligator Point, Florida

Unincorporated community in Florida, United StatesAlligator PointUnincorporated communityThe Marina at Alligator Point during the 1960sAlligator PointCoordinates: 29°54′18″N 84°25′01″W / 29.905°N 84.417°W / 29.905; -84.417CountryUnited StatesStateFloridaCountyFranklinGovernment • BodyFranklin County, Florida • District 2 CommissionerBert B. Bolt IIPopulation (2012) • Total447 Rough Estimate; Not Conducted by th...

Daftar kasino Las Vegas yang tak pernah dibuka

Artikel ini tidak memiliki bagian pembuka yang sesuai dengan standar Wikipedia. Mohon tulis paragraf pembuka yang informatif sehingga pembaca dapat memahami maksud dari Daftar kasino Las Vegas yang tak pernah dibuka. Contoh paragraf pembuka Daftar kasino Las Vegas yang tak pernah dibuka adalah .... (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) Bertahun-tahun terdapat beberapa kasino dan resor yang direncanakan di Las Vegas yang tak pernah dibuka. Perencanaan mungkin baru...

 

Jackie (film 2016)

JackieNatalie Portman nei panni di Jackie Kennedy in una scena del filmTitolo originaleJackie Lingua originaleinglese, spagnolo Paese di produzioneStati Uniti d'America, Cile, Francia Anno2016 Durata99 min Rapporto1,66:1 Generedrammatico, biografico RegiaPablo Larraín SceneggiaturaNoah Oppenheim ProduttoreDarren Aronofsky, Juan de Dios Larraín, Mickey Liddell, Scott Franklin, Ari Handel Produttore esecutivoPete Shilaimon, Jennifer Monroe, Jayne Hong, Wei Han, Lin Qi, Josh Stern ...

 

约翰斯顿环礁

此條目可参照英語維基百科相應條目来扩充。 (2021年5月6日)若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。 约翰斯顿环礁Kalama Atoll 美國本土外小島嶼 Johnston Atoll 旗幟颂歌：《星條旗》The Star-Spangled Banner約翰斯頓環礁�...

قراغوز سليم أقا

قراغوز سليم أقا تقسيم إداري البلد إيران  [1] إحداثيات 37°37′57″N 45°03′58″E / 37.6325°N 45.06611111°E / 37.6325; 45.06611111   الرمز الجغرافي 6677417  تعديل مصدري - تعديل   قراغوز سليم‌ أقا هي قرية في مقاطعة أرومية، إيران. عدد سكان هذه القرية هو 182 في سنة 2006.[2] مراجع ^   صف�...

 

Sky plc

Sky LtdJenisAnak perusahaanIndustriMedia massaPendahuluSky TelevisionBritish Satellite BroadcastingDidirikanNovember 1990PendiriRupert MurdochKantorpusatOsterley, London, Britania RayaWilayah operasiEropaTokohkunciNicholas Ferguson (Chairman)Jeremy Darroch (CEO)ProdukTelevisi satelit, televisi berlangganan, penyiaran, akses internet dan layanan teleponPendapatan£6.791 miliar (2012)[1]Laba operasi£1.243 miliar (2012)[1]Laba bersih£970 juta (2012)[1]Kar...

 

Duchy of Magdeburg

Duchy in Central Europe between 1680–1807 Duchy of MagdeburgHerzogtum Magdeburg1680–1807 Coat of arms The Duchy of Magdeburg within Brandenburg-Prussia at the death of the Great Elector (1688)StatusFief of Brandenburg (1680–1701)Fief of Prussia (1701–1807)CapitalMagdeburg, HalleReligion Roman CatholicGovernmentDuchyHistory • Archbishopric of Magdeburgsecularised 1680• Joined Kingdom of Prussia 1701• Disestablished 1807 Preceded by Succeeded by Archbishopric o...

原子力

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）出典検索?: 原子力 – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2015年10月) 原子力 原子原子物理学原子力核兵器 ポータル カテ...

 

Kung Fu Panda: Secrets of the Scroll

2015 American filmKung Fu Panda:Secrets of the ScrollFilm posterDirected byRodolphe GuenodenWritten byPaul McEvoyProduced byKaren FosterStarringJack BlackDustin HoffmanSeth RogenDavid CrossLucy LiuTara MacriJames HongRandall Duk KimNarrated byRandall Duk KimEdited byMark DeimelMusic byLorne BalfeHans ZimmerProductioncompanyDreamWorks AnimationDistributed by20th Century Fox Home EntertainmentRelease date December 15, 2015 (2015-12-15) Running time23 minutesCountryUnited StatesLa...