Algoritmy pro grafy malé highway dimension

Vu, Tung Anh

In this work we develop algorithms for the k-Supplier with Outliers problem. In a network, we are given a set of suppliers and a set of clients. The goal is to choose k suppliers so that the distance between every served client and its nearest supplier is minimized. Clients that are not served are called outliers and the number of allowed outliers is given on input. As k-Supplier with Outliers has numerous applications in logistics, we focus on parameters which are suitable for transportation networks. We study graphs with low highway dimension, which was proposed by Abraham et al. [SODA 2010], and low doubling dimension. It is known that unless P = NP, k-Supplier with Outliers does not admit a (3 − ε)-approximation algorithm for any constant ε > 0. The k-Supplier with Outliers problem is W[1]-hard on graphs of constant doubling dimension for parame- ters k and highway dimension. We overcome both of these barriers through the paradigm of parameterized approximation algorithms. In the case of highway dimension, we develop a (1 + ε)-approximation algorithm for any ε > 0 with running time f(k, p, h, ε) · nO(1) where p is the number of allowed outliers, h is the highway dimension of the input graph, and f is some computable function. In the case of doubling dimension, we develop a (1 + ε)-approximation...

host :: přihlásit Digitální repozitář
		Hledej		Nový záznam		Nápověda		O repozitáři