An Efficient LP Rounding Scheme for Replica Placement

Zhihui Du, Sen Zhang, David A. Bader, Jingkun Hu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


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.

Original languageEnglish (US)
Title of host publication2020 IEEE High Performance Extreme Computing Conference, HPEC 2020
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781728192192
StatePublished - Sep 22 2020
Externally publishedYes
Event2020 IEEE High Performance Extreme Computing Conference, HPEC 2020 - Virtual, Waltham, United States
Duration: Sep 21 2020Sep 25 2020

Publication series

Name2020 IEEE High Performance Extreme Computing Conference, HPEC 2020


Conference2020 IEEE High Performance Extreme Computing Conference, HPEC 2020
Country/TerritoryUnited States
CityVirtual, Waltham

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Computer Science Applications
  • Hardware and Architecture


  • Approximation Ratio
  • Fault Tolerance
  • Quality of Service
  • Replica Placement
  • Rounding Algorithm


Dive into the research topics of 'An Efficient LP Rounding Scheme for Replica Placement'. Together they form a unique fingerprint.

Cite this