Approximation Algorithms for Client Assignment Problems for Latency Minimization

Interactivity is a primary performance measure for distributed interactive applications (DIAs). In a network supporting a DIA, interactivity performance depends on both client-to-server network latencies and inter-server network latencies. An optimization problem, which we term FCSA, seeks to find an optimum way of how clients are assigned to servers such that the largest latency on an interactivity path between two clients (client 1 to server 1, server 1 to server 2, then server 2 to client 2) is minimized, using an input of a finite set \(V\), its two subsets “clients” and “servers”, and a semi-metric (``distance”) on \(V\).

Previous work showed that it is NP-hard to approximate FCSA with a ratio better than \(4/3\) and gave a \(3\)-approximation algorithm. In this talk, I will introduce a polynomial time \(3/2\)-approximation algorithm for this problem, and show that is NP-hard to obtain a better ratio. Using the technique of parametric pruning, I will also introduce a \(3/2\)-approximation algorithm for the more general problem, FCSA-SC, where we also have ``capacity", the maximum number of clients that can be assigned to a server, as part of the input. This is joint work with Gruia Calinescu.

Event Topic

Discrete Applied Math Seminar