Vi betraktar K-Center-problemet och några generaliseringar. För kCenter en uppsättning k center hörn måste hittas i en graf G med kant längder, så att avståndet från någon vertex av G till dess närmaste centrum minimeras. Detta problem uppstår naturligtvis i transportnät, och därför modellerar vi ingångarna som grafer med avgränsad motorvägsdimension, som föreslagits av Abraham et al. (ODA, s. 782-793, 2010). Vi visar både approximation och fast-parameter hårdhet resultat, och hur man övervinner dem med fast-parameter approximationer, där de två paradigmerna kombineras. I synnerhet visar vi att för alla ε > 0 computing a (2 − ε) - approximation är W[2] - hård för parameter k, och NP-hard för grafer med motorvägsdimension O(log 2 n). Den senare utesluter inte fasta parameter (2 - ε)- tillnärmningar för vägdimension parameter h, men innebär att en sådan algoritm måste ha minst dubbelt exponentiellt körtid i h om den finns, om inte ETH misslyckas. På den positiva sidan visar vi hur man kommer under approximationsfaktorn 2 genom att kombinera parametrarna k och h: vi utvecklar en fast parameter 3/2-approximation med körtid 2 O(kh log h) · n O(1). Dessutom bevisar vi att om inte P=NP, våra tekniker inte kan användas för att beräkna fast-parameter (2 − ε) - approximationer för endast parameter h. Vi ger också liknande fast-parameter Jag skulle vilja tacka Jochen Könemann för att läsa ett tidigt utkast av detta papper. Jag vill också tacka två anonyma granskare för deras insiktsfulla kommentarer som bidrog till att avsevärt förbättra dokumentet. En preliminär version publicerades på 42nd International Colloquium on Automata, Languages, and Programmering (ICAP 2015).
Feldmann REF visade hårdhetsresultat för k-Center.
Fixed-Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}