Disconnection Problem (disconnection + problem)

Distribution by Scientific Domains

Selected Abstracts

Approximability of the k -server disconnection problem

Sung-Pil Hong
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 NP -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 ( )-approximation can be created in the time of O(2k) 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 [source]

Network disconnection problems in a centralized network

Young-Soo Myung
Abstract We consider three network disconnection problems in a centralized network where a source node provides service to the other nodes, called demand nodes. In network disconnection problems, each demand node gets a certain benefit when connected to a source node and a network attacker destroys edges to prevent demand nodes from achieving benefits. As destroying edges incurs expenses, an attacker considers the following three different strategies. The first is to maximize the sum of benefits of the disconnected nodes while keeping the total edge destruction cost no more than a given budget. The second is to minimize the total destruction cost needed to make a certain amount of benefits not accomplished. The last is to minimize the ratio of the total destruction cost to the benefits not accomplished. In this paper, we develop exact algorithms to solve the above three problems. 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007 [source]