Top

Journal of Combinatorial Optimization

Published in:

14-07-2018

Client assignment problems for latency minimization

Authors: Gruia Călinescu, Xiaolang Wang

Published in: Journal of Combinatorial Optimization | Issue 3/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

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, is to find an optimum way 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. Previous work showed that it is NP-hard to approximate this problem with a ratio better than 4 / 3 and gave a 3-approximation algorithm. In this paper, we give a (3 / 2)-approximation algorithm for FCSA, and show that it is NP-hard to obtain a better ratio. We also give a (3 / 2)-approximation algorithm when server capacity constraints are considered.

previous article Agreeable sets with matroidal constraints

next article Verifying schedulability of tasks in ROS-based systems

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

A function \(d\,{:}\,V\times V\rightarrow {\mathbb {R}}\) is a semimetric on V iff for every \(i_1,i_2,i_3\in V\), \(d(i_1,i_1) = 0\), \(d(i_1,i_2)\ge 0\), \(d(i_1,i_2) = d(i_2,i_1)\), and \(d(i_1,i_2)+d(i_2,i_3)\ge d(i_1,i_3)\). If, in addition, \(d(i_1,i_2) = 0\) implies \(i_1 = i_2\), then d is a metric.

Archer A (2001) Two \(O(\log ^*k)\)-approximation algorithms for the asymmetric \(k\)-center problem. In: Aardal K, Gerards B (eds) Integer programming and combinatorial optimization, vol 2081. Lecture notes in computer science. Springer, Berlin, pp 1–14

Chuzhoy J, Guha S, Halperin E, Khanna S, Kortsarz G, Krauthgamer R, Naor JS (2005) Asymmetric \(k\)-center is \(\log ^*n\)-hard to approximate. J ACM 52(4):538–551MathSciNetCrossRefMATH

Cygan M, Hajiaghayi MT, Khuller S (2012) LP rounding for \(k\)-centers with non-uniform hard capacities. In: 53rd annual IEEE symposium on foundations of computer science, FOCS 2012, New Brunswick, NJ, USA, October 20–23, 2012. IEEE Computer Society, pp 273–282

Hochbaum DS, Shmoys DB (1985) A best possible heuristic for the \(k\)-center problem. Math Oper Res 10:180–184MathSciNetCrossRefMATH

Hochbaum DS, Shmoys DB (1986) A unified approach to approximation algorithms for bottleneck problems. J ACM 33(3):533–550MathSciNetCrossRef

Hsu W-L, Nemhauser GL (1979) Easy and hard bottleneck location problems. Discrete Appl Math 1(3):209–215MathSciNetCrossRefMATH

Khuller S, Sussmann YJ (2000) The capacitated k-center problem. SIAM J Discrete Math 13(3):403–418MathSciNetCrossRefMATH

Li Gørtz I, Wirth A (2006) Asymmetry in \(k\)-center variants. Theor Comput Sci 361(2–3):188–199MathSciNetCrossRefMATH

Panigrahy R, Vishwanathan S (1998) An \({O}(\log ^* n)\) approximation algorithm for the asymmetric \(p\)-center problem. J. Algorithms 27(2):259–268MathSciNetCrossRefMATH

Vazirani VV (2001) Approximation algorithms. Springer, BerlinMATH

Zhang L, Tang X (2014) The client assignment problem for continuous distributed interactive applications: analysis, algorithms, and evaluation. IEEE Trans Parallel Distrib Syst 25(3):785–795CrossRef

Title: Client assignment problems for latency minimization
Authors: Gruia Călinescu
Xiaolang Wang
Publication date: 14-07-2018
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 3/2019
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-018-0326-2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 3/2019

Restricted power domination and zero forcing problems

Minimum rank and zero forcing number for butterfly networks

Approximation algorithms for the graph balancing problem with two speeds and two job lengths

Accelerating benders decomposition: multiple cuts via multiple solutions

A note on a two-agent scheduling problem related to the total weighted late work

A polynomial algorithm determining cyclic vertex connectivity of k-regular graphs with fixed k

Premium Partner