Premium
Approximability of the k ‐server disconnection problem
Author(s) -
Hong SungPil,
Choi ByungCheon
Publication year - 2007
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20203
Subject(s) - approximation algorithm , server , disconnection , computer science , constant (computer programming) , time complexity , set (abstract data type) , polynomial , limit (mathematics) , enhanced data rates for gsm evolution , combinatorics , binary logarithm , mathematics , discrete mathematics , computer network , telecommunications , mathematical analysis , political science , law , programming language
Consider a network of k servers and their users. Each server provides a unique service that has a certain utility for each user. Now comes an attacker who wishes to destroy a set of network edges to maximize his net gain, namely the total disconnected utilities of the users minus the total edge‐destruction cost. This k ‐server disconnection problem is N P ‐hard and, furthermore, cannot be approximated within a polynomially computable factor of the optimum when k is part of the input. Even for any fixed k ≥ 2, there is a constant ϵ > 0 such that approximation of the problem within a factor 1/(1 + ϵ) of the optimum is NP‐hard. However, a ( ${1\over 2}+{{1}\over {2^{k+1}-2}}$ )‐approximation can be created in the time of O (2 k ) applications of a min‐cut algorithm. The main idea is to approximate the optimum with special solutions computable in polynomial time due to supermodularity. Therefore, when the the network has, as is usual in most cases, only a few servers, a 0.5‐approximation can be carried out in polynomial time. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(4), 273–282 2007