Denna uppsats är en teoretisk och experimentell studie av två relaterade anläggnings lokaliseringsproblem som härrörde från nätverkande. Antag att vi får ett nätverk modellerat som en riktad graf G = (V, A), tillsammans med (inte-nödvändigt-avskiljande) undergrupper C och F av V, där C är en uppsättning av kundplatser och F är en uppsättning potentiella anläggningar (och typiskt C  på F ). Vårt mål är att hitta en minsta storlek delmängd F ′ F sådan att för varje kund c  på C finns det två platser f 1, f 2 F ′ sådan att trafiken från c till f 1 och f 2 dirigeras på separata vägar (vanligen kortaste vägar) under nätverkets routing protokoll. Även om vi bevisar att detta problem är omöjligt att approximera i värsta fall även att inom en faktor av 2 log 1- på n för någon  på > 0 (förutsatt att inget NPfullständigt språk kan lösas i kvasipolynom tid), visar vi att situationen är mycket bättre i praktiken. Vi föreslår tre algoritmer som bygger lösningar och bestämmer lägre gränser på den optimala lösningen, och utvärderar dem på flera stora riktiga ISP topologier och på syntetiska nätverk utformade för att spegla verkliga LAN / WAN nätverksstruktur. Våra huvudalgoritmer är (1) en algoritm som utför flera körningar av en enkel randomiserad girig heuristisk och returnerar det bästa resultatet hittades, (2) en genetisk algoritm som använder den giriga algoritmen som en subrutin, och (3) en ny "Double Hitting Set" algoritm. Alla tre tillvägagångssätt presterar överraskande bra, även om den mest kostnadseffektiva metoden i praktiken är multirun girig algoritm. Detta ger genomsnittliga resultat * AT&T Labs - Research, 180 Park Avenue, Florham Park, NJ 07932. † Computer Science Department, University of California, Soda Hall, Berkeley, CA 94720. Detta arbete utfördes när författaren var student vid Columbia University och fick delvis stöd av AT&T. Amazon Web Services, 1200 12th Avenue South, Seattle, WA 98144. Detta arbete utfördes när författaren var student vid University of Massachusetts och fick delvis stöd av AT&T. inom 0,7 % av optimal för våra syntetiska fall och inom 2,9 % för våra verkliga fall, exklusive den största (och mest realistiska) en. För det senare fallet, de andra två algoritmer kommer i sin egen, hitta lösningar som är mer än tre gånger bättre än de i multi-start girig strategi. När det gäller vår motiverande övervakning, där varje kund plats kan vara en anläggning plats, resultaten är ännu bättre. Här ovan Double Hitting Set lösning är 90% bättre än standardlösningen som placerar en monitor på varje kund plats - sådana jämförelser bidrar till att motivera den föreslagna alternativa övervakningssystemet [8]. Våra resultat visar också att vi i genomsnitt för våra verkliga fall skulle kunna spara ytterligare 18 procent genom att själva välja de (kortaste) rutterna, snarare än att ta det enklare tillvägagångssättet att förlita sig på nätverket för att välja dem åt oss.
Detta dokument är delvis tidskriftsversionen av ett konferensdokument REF.
Disjoint-Path Facility Location: Theory and Practice
{'venue': 'ALENEX', 'journal': None, 'mag_field_of_study': ['Computer Science']}