I detta papper studerar vi hårdheten av k-Center-problemet på indata den modellen transportnät. För problemet, en graf G = (V, E) med kantlängder och ett heltal k ges och en center set C  på V måste väljas så att  för att ≤ k. Syftet är att minimera det maximala avståndet av någon vertex i grafen till närmaste centrum. Detta problem uppstår i många tillämpningar av logistik, och därför är det naturligt att överväga ingångar som modell transportnät. Sådana ingångar antas ofta vara plana grafer, låga dubbleringsmått eller avgränsade vägdimensionsdiagram. För var och en av dessa modeller har parameteriserade approximationsalgoritmer visat sig existera. Vi kompletterar dessa resultat genom att bevisa att k-Center problemet är W[1]-hård på plana grafer med konstant dubblering dimension, där parametern är kombinationen av antalet centra k, motorvägsdimensionen h, och vägbredd p. Dessutom, under den exponentiella tidshypotesen finns det ingen f (k, p, h) n o(p+ ε k+h) tid algoritm för någon beräkningsbar funktion f. Således är det osannolikt att den optimala lösningen för k-Center kan hittas effektivt, även om man antar att inmatningsgrafen följer alla ovanstående modeller för transportnät på en gång! Dessutom ger vi en enkel parameteriserad (1 + ) - approximation algoritm för ingångar av dubblering dimension d med körtid (k k  och O (kd) ) n O(1). Detta generaliserar ett tidigare resultat, som beaktade ingångar i D-dimensionella L q-mått.
Detta kan också generaliseras REF till en (1 + ε)-FPA-algoritm för den kombinerade parametern (k, ε, d), där d är dubbleringsdimensionen.
The Parameterized Hardness of the k-Center Problem in Transportation Networks
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}