Abstrakt. Vi analyserar lokala sökheuristiker för de metriska k-median- och anläggningslokaliseringsproblemen. Vi definierar det lokala gapet i ett lokalt sökförfarande för ett minimeringsproblem som det maximala förhållandet mellan en lokalt optimal lösning (som erhålls genom detta förfarande) och det globala optimala. För k-median visar vi att lokal sökning med swaps har en lokalitetsklyfta på 5. Dessutom, om vi tillåter upp till p anläggningar att bytas samtidigt, då lokalitet gapet är 3 + 2 / p. Detta är den första analysen av en lokal sökning efter k-median som ger en begränsad prestandagaranti med endast k medianvärden. Detta förbättrar också den tidigare kända 4 approximationen för detta problem. För okapacitet anläggning plats, visar vi att lokal sökning, som tillåter att lägga till, släppa, och byta en anläggning, har en lokalitet gap på 3. Detta förbättrar gränsen av 5 ges av M. Korupolu, C. Plaxton, och R. Rajaraman [Analys av en lokal sökning Heuristic för anläggningsproblem, Technical Report 98-30, DIMACS, 1998]. Vi anser också att en kapacierad anläggning plats problem där varje anläggning har en kapacitet och vi får öppna flera kopior av en anläggning. För detta problem introducerar vi en ny lokal sökoperation som öppnar en eller flera kopior av en anläggning och släpper noll eller fler anläggningar. Vi bevisar att denna lokala sökning har en lokal klyfta mellan 3 och 4.
Arya m.fl. Analysera i REF en lokal sökheuristik för anläggning plats och k-median problem.
Local search heuristics for k-median and facility location problems
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}