Browse

Approximability of the k-Server Disconnection Problem

DC Field Value Language
dc.contributor.authorHong, Sung-Pil-
dc.contributor.authorChoi, Byung-Cheon-
dc.date.accessioned2009-07-10T08:19:15Z-
dc.date.available2009-07-10T08:19:15Z-
dc.date.issued2007-09-04-
dc.identifier.citationNetworks 50(2007), 273-282en
dc.identifier.issn0028-3045-
dc.identifier.urihttps://hdl.handle.net/10371/5349-
dc.descriptionThe definitive version is available at www3.interscience.wiley.com.en
dc.description.abstractConsider 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 optimumwhen 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 12 + 1 2k+1−2 -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.en
dc.description.sponsorshipContract grant sponsor: KOSEF;
Contract grant number: R01-2005-000-10271-0
en
dc.language.isoen-
dc.publisherWiley-Blackwellen
dc.subjectserver–network disconnectionen
dc.subjectinapproximabilityen
dc.subjectapproximation algorithmen
dc.subjectfixed-parameter casesen
dc.titleApproximability of the k-Server Disconnection Problemen
dc.typeArticleen
dc.contributor.AlternativeAuthor홍성필-
dc.contributor.AlternativeAuthor최병천-
dc.identifier.doi10.1002/net.20203-
dc.identifier.doi10.1002/net.20203-
dc.citation.journaltitleNetwork-
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Industrial Engineering (산업공학과)Journal Papers (저널논문_산업공학과)
Files in This Item:
There are no files associated with this item.
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse