𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximability of the k-server disconnection problem

✍ Scribed by Sung-Pil Hong; Byung-Cheon Choi

Book ID
102547030
Publisher
John Wiley and Sons
Year
2007
Tongue
English
Weight
332 KB
Volume
50
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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

📜 SIMILAR VOLUMES

Approximability of the Firefighter Probl
Approximability of the Firefighter Problem
✍ Elliot Anshelevich; Deeparnab Chakrabarty; Ameya Hate; Chaitanya Swamy 📂 Article 📅 2010 🏛 Springer 🌐 English ⚖ 600 KB
On the approximability of the Steiner tr
On the approximability of the Steiner tree problem
✍ Martin Thimm 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 165 KB

We show that it is not possible to approximate the minimum Steiner tree problem within 1 + 1 162 unless RP = NP. The currently best known lower bound is 1 + 1 400 . The reduction is from H astad's nonapproximability result for maximum satisÿability of linear equation modulo 2. The improvement on the

On the approximability of an interval sc
On the approximability of an interval scheduling problem
✍ Frits C. R. Spieksma 📂 Article 📅 1999 🏛 Springer US 🌐 English ⚖ 148 KB 👁 2 views

In this paper we consider a general interval scheduling problem. The problem is a natural generalization of "nding a maximum independent set in an interval graph. We show that, unless P"NP, this maximization problem cannot be approximated in polynomial time within arbitrarily good precision. On the