Abstrakt. Min-kostnadsmatchning problemet lider av att vara mycket känslig för små förändringar av inmatningen. Även i en enkel inställning, t.ex., när kostnaderna kommer från metriska på linjen, lägga till två noder till inmatningen kan ändra den optimala lösningen helt. Å andra sidan förväntar man sig att små förändringar i inmatningen endast bör medföra små förändringar på de konstruerade lösningarna, mätt som antalet modifierade kanter. Vi introducerar en tvåstegsmodell där vi studerar avvägningen mellan kvalitet och robusta lösningar. I det första steget får vi en uppsättning noder i ett metriska utrymme och vi måste beräkna en perfekt matchning. I den andra etappen visas 2k nya noder och vi måste anpassa lösningen till en perfekt matchning för den nya instansen. Vi säger att en algoritm är (α, β)-robust om de lösningar som konstrueras i båda stegen är α-ungefärliga med avseende på min-kostnad perfekta matchningar, och om antalet kanter som tas bort från det första steget matchning är som mest βk. Därför mäter α kvaliteten på algoritmen och β dess robusthet. I denna miljö strävar vi efter att balansera båda åtgärderna genom att härleda algoritmer för konstant α och β. Vi visar att det finns en algoritm som är (3, 1)-robust för någon metrisk om man känner till nummer 2k av anlända noder i förväg. För det fall k är okänt är situationen betydligt mer involverad. Vi studerar denna inställning under metrisken på linjen och utformar en (19, 2)-robust algoritm som konstruerar en lösning med en rekursiv struktur som noggrant balanserar kostnader och redundans.
Såvitt vi vet är det enda arbete som överväger att använda sig av min-kostnadsmatchning online det senaste arbetet REF där författarna anser en tvåstegsversion av det enkromatiska problemet (där det inte finns någon skillnad mellan servrar och kunder): I det första steget måste en perfekt matchning mellan 2n givna noder väljas; i det andra steget införs 2k nya noder.
Maintaining Perfect Matchings at Low Cost
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}