Vi introducerar kapaciterad metrisk märkning. Som i Metric Labeling, vi får en viktad graf G = (V, E), en etikett som L, en semimetrisk dL på denna etikett uppsättning, och en tilldelning kostnad funktion  på: V × L → +. Målet i Metric Labeling är att hitta ett uppdrag f : V → L som minimerar en viss tvåkostnadsfunktion. Här lägger vi till den ytterligare begränsningen som varje etikett ti får på de flesta li noder, och vi hänvisar till detta problem som kapaciated Metric Labeling. Att tillåta problemet att specificera kapacitet på varje etikett gör det möjligt för problemet att mer troget representera de klassificeringsproblem som Metric Labeling är avsett att modellera. Vårt huvudsakliga positiva resultat är en polynom-tid, O(log  och V)-tillnärmning algoritm när antalet etiketter är fast, vilket är den mest naturliga parameteromfånget för klassificeringsproblem. Vi bevisar också att det är omöjligt att approximera värdet av ett fall av kapaciterad metrisk märkning till inom någon ändlig faktor, om P = N P. Men detta tar inte upp den mer intressanta frågan om hur svårt kapaciterad metrisk märkning är att approximera när vi tillåts bryta kapacitet. För att studera denna fråga introducerar vi begreppet "överbelastning" av ett fall av kapaciterad metrisk märkning. Vi bevisar att (under vissa komplexa antaganden) det finns ingen polynom-tid approximationsalgoritm som kan approximera trängseln till inom O((log  på L) 1/2- ) (för alla > 0) och detta innebär som en följd av att alla polynom-tid approximation algoritm som uppnår en ändlig approximation förhållande måste multiplikativt bryta etikettkapaciteten av  och (log på L) 1/2- ). Vi ger också en O (log  på L)-tillnärmningsalgoritm för trängsel.
År 2011, Andrew m.fl. REF införde kapaciterad metrisk märkning, där det finns ytterligare begränsningar som varje etikett jag får som mest l i noder.
Capacitated Metric Labeling
{'venue': "SODA '11", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}