@inproceedings{5ca5638994b84a21b20f1ae088b15f02,

title = "An Efficient LP Rounding Scheme for Replica Placement",

abstract = "Large fault-tolerant network systems with high Quality of Service (QoS) guarantee are critical in many real world applications and entail diverse replica placement problems. In this paper, the replica placement problem in terms of minimizing the replica placement cost subject to both QoS and fault-tolerant constraints is formulated as a binary integer linear programming problem first and then relaxed as a linear programming problem. Given the optimal fractional linear programming solution, we propose a two-step rounding algorithm to obtain its integer solution. In the first step, a half rounding algorithm is used to simplify the problem. In the second step, a cheapest amortized cost rounding algorithm uses a novel metric, named amortized cost, to make locally optimal rounding decision for the remaining vertices independently. Furthermore, a conflict resolution algorithm is presented to tackle the situations when different vertices make conflicting rounding decisions. Finally, we prove that the proposed two-step rounding algorithm has a 2-approximation ratio when the additional conflict cost meets a given constraint.",

keywords = "Approximation Ratio, Fault Tolerance, Quality of Service, Replica Placement, Rounding Algorithm",

author = "Zhihui Du and Sen Zhang and Bader, {David A.} and Jingkun Hu",

note = "Publisher Copyright: {\textcopyright} 2020 IEEE.; 2020 IEEE High Performance Extreme Computing Conference, HPEC 2020 ; Conference date: 21-09-2020 Through 25-09-2020",

year = "2020",

month = sep,

day = "22",

doi = "10.1109/HPEC43674.2020.9286163",

language = "English (US)",

series = "2020 IEEE High Performance Extreme Computing Conference, HPEC 2020",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

booktitle = "2020 IEEE High Performance Extreme Computing Conference, HPEC 2020",

address = "United States",

}