# LP-based approximation algorithms for reliable resource allocation

Journal article

Liao, Kewen and Shen, Hong. (2014). LP-based approximation algorithms for reliable resource allocation. The Computer Journal. 57(1), pp. 154-164. https://doi.org/10.1093/comjnl/bxs164
Authors Liao, Kewen and Shen, Hong We initiate the study of the reliable resource allocation (RRA) problem. In this problem, we are given a set of sites β± each with an unconstrained number of facilities as resources. Every facility at site i β β± has an opening cost and a service reliability pi. There is also a set of clients π to be allocated to facilities. Every client j β π accesses a facility at i with a connection cost and reliability lij. In addition, every client j has a minimum reliability requirement (MRR) rj for accessing facilities. The objective of the problem is to decide the number of facilities to open at each site and connect these facilities to clients such that all clientsβ MRRs are satisfied at a minimum total cost. The unconstrained fault-tolerant resource allocation problem studied in Liao and Shen [(2011) Unconstrained and Constrained Fault-Tolerant Resource Allocation. Proceedings of the 17th Annual International Conference on Computing and Combinatorics (COCOON), Dallas, Texas, USA, August 14β16, pp. 555β566. Springer, Berlin] is a special case of RRA. Both of these resource allocation problems are derived from the classical facility location theory. In this paper, for solving the general RRA problem, we develop two equivalent primal-dual algorithms where the second one is an acceleration of the first and runs in quasi-quadratic time. In the algorithm's ratio analysis, we first obtain a constant approximation factor of 2+2β2 and then a reduced ratio of 3.722 using a factor revealing program, when lij's are uniform on i (partially uniform) and rj's are uniform above the threshold reliability that a single access to a facility is able to provide. The analysis further elaborates and generalizes the inverse dual-fitting technique introduced in Xu and Shen [(2009) The Fault-Tolerant Facility Allocation Problem. Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC), Honolulu, HI, USA, December 16β18, pp. 689β698. Springer, Berlin]. Moreover, we formalize this technique for analyzing the minimum set cover problem. For a special case of RRA, where all rj's and lij's are uniform, we derive its approximation ratio through a novel reduction to the uncapacitated facility location problem. The reduction demonstrates some useful and generic linear programming techniques. reliable resource allocation; approximation algorithms; time complexity; inverse dual fitting; reduction 2014 The Computer Journal 57 (1), pp. 154-164 Oxford University Press 0010-4620 https://doi.org/10.1093/comjnl/bxs164 2-s2.0-84891526908 Research 154-164 LicenseAll rights reservedFile Access LevelControlled Published 11 Jan 2013 11 Aug 2021

https://acuresearchbank.acu.edu.au/item/8w926/lp-based-approximation-algorithms-for-reliable-resource-allocation

## Restricted files

### Publisher's version

total views
• ##### 1
views this month
• ##### 0
These values are for the period from 19th October 2020, when this repository was created.

## Related outputs

##### Demo : SenShaMart - A sensor sharing marketplace for IoT
Dawod, Anas, Georgakopoulos, Dimitrios, Jayaraman, Prem Prakash, Milovac, Josip Karabotic, Liao, Kewen and Chrysanthis, Panos K.. (2023). Demo : SenShaMart - A sensor sharing marketplace for IoT. 2023 IEEE 43rd International Conference on Distributed Computing Systems (ICDCS). Hong Kong, China 18 - 21 Jul 2023 IEEE Computer Society. pp. 1025-1028 https://doi.org/10.1109/ICDCS57875.2023.00122
##### Fed-SC : One-shot federated subspace clustering over high-dimensional data
Xie, Songjie, Wu, Youlong, Liao, Kewen, Chen, Lu, Liu, Chengfei, Shen, Haifeng, Tang, MingJian and Sun, Lu. (2023). Fed-SC : One-shot federated subspace clustering over high-dimensional data. 2023 IEEE 39th International Conference on Data Engineering (ICDE). Anaheim, California, United States of America 03 - 07 Apr 2023 Institute of Electrical and Electronics Engineers Inc.. pp. 2905-2918 https://doi.org/10.1109/ICDE55515.2023.00222
##### Efficient algorithm for the k-means problem with Must-Link and Cannot-Link constraints
Jia, Chaoqi, Guo, Longkun, Liao, Kewen and Lu, Zhigang. (2023). Efficient algorithm for the k-means problem with Must-Link and Cannot-Link constraints. Tsinghua Science and Technology. 28(6), pp. 1050-1062. https://doi.org/10.26599/TST.2022.9010056
##### Hamstring strain injury risk factors in Australian Football change over the course of the season
Sim, Aylwin, Timmins, Ryan G., Ruddy, Joshua D., Shen, Haifeng, Liao, Kewen, Maniar, Nirav, Hickey, Jack T., Williams, Morgan D. and Opar, David A.. (2023). Hamstring strain injury risk factors in Australian Football change over the course of the season. Medicine and Science in Sports and Exercise. https://doi.org/10.1249/MSS.0000000000003297
##### Submodular maximization over data streams with differential privacy noise
Guo, Longkun, Liao, Kewen, Xiao, Di and Yao, Pei. (2023). Submodular maximization over data streams with differential privacy noise. Theoretical Computer Science. 944, p. Article 113625. https://doi.org/10.1016/j.tcs.2022.11.011
##### A metadata-assisted cascading ensemble classification framework for automatic annotation of open IoT data
Montori, Federico, Liao, Kewen, Giosa, Matteo De, Jayaraman, Prem Prakash, Bononi, Luciano, Sellis, Timos and Georgakopoulos, Dimitrios. (2023). A metadata-assisted cascading ensemble classification framework for automatic annotation of open IoT data. IEEE Internet of Things Journal. 10(15), pp. 13401-13413. https://doi.org/10.1109/JIOT.2023.3263213
##### Fast approximation algorithms for multiple coverage with unit disks
Gao, Xuening, Guo, Longkun and Liao, Kewen. (2022). Fast approximation algorithms for multiple coverage with unit disks. 2022 IEEE 23rd International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM). Belfast, United Kingdom 14 - 17 Jun 2022 IEEE Computer Society. pp. 185-193 https://doi.org/10.1109/WoWMoM54355.2022.00037
##### Do simpler statistical methods perform better in multivariate long sequence time-series forecasting?
Li, Hao, Shao, Jie, Liao, Kewen and Tang, Mingjian. (2022). Do simpler statistical methods perform better in multivariate long sequence time-series forecasting? CIKM '22: The 31st ACM International Conference on Information and Knowledge Management. Atlanta, Georgia, United States of America 17 - 21 Oct 2022 Association for Computing Machinery (ACM). pp. 4168-4172 https://doi.org/10.1145/3511808.3557585
##### CorrDetector : A framework for structural corrosion detection from drone images using ensemble deep learning
Forkan, Abdur Rahim Mohammad, Kang, Yong-Bin, Jayaraman, Prem Prakash, Liao, Kewen, Kaul, Rohit, Morgan, Graham, Ranjan, Rajiv and Sinha, Samir. (2022). CorrDetector : A framework for structural corrosion detection from drone images using ensemble deep learning. Expert Systems with Applications. 193, p. Article 116461. https://doi.org/10.1016/j.eswa.2021.116461
##### CNN attention guidance for improved orthopedics radiographic fracture classification
Liao, Zhibin, Liao, Kewen, Shen, Haifeng, van Boxel, Marouska F, Prijs, Jasper, Jaarsma, Ruurd L., Doornberg, Job N., van den Hengel, Anton and Verjans, Johan W.. (2022). CNN attention guidance for improved orthopedics radiographic fracture classification. IEEE Journal of Biomedical and Health Informatics. 26(7), pp. 3139-3150. https://doi.org/10.1109/JBHI.2022.3152267
##### On finding maximum disjoint paths with different colors : Computational complexity and practical LP-based algorithms
Deng, Yunyun, Guo, Longkun, Liao, Kewen and Chen, Yi. (2021). On finding maximum disjoint paths with different colors : Computational complexity and practical LP-based algorithms. Theoretical Computer Science. 886, pp. 157-168. https://doi.org/10.1016/j.tcs.2021.08.009
##### Understanding the effects of real-time sentiment analysis and morale visualisation in backchannel systems : A case study
Wyeld, Theodor, Jiranantanagorn, Peerumporn, Shen, Haifeng, Liao, Kewen and Bednarz, Tomasz. (2021). Understanding the effects of real-time sentiment analysis and morale visualisation in backchannel systems : A case study. International Journal of Human-Computer Studies. 145, p. Article 102524. https://doi.org/10.1016/j.ijhcs.2020.102524
##### Human-AI interactive and continuous sensemaking : A case study of image classification using scribble attention maps
Shen, Haifeng, Liao, Kewen, Liao, Zhibin, Doornberg, Job, Qiao, Maoying, van den Hengel, Anton and Verjans, Johan W.. (2021). Human-AI interactive and continuous sensemaking : A case study of image classification using scribble attention maps. CHI Conference on Human Factors in Computing Systems. Virtual 08 - 13 May 2021 pp. 1-8 https://doi.org/10.1145/3411763.3451798
##### Inferring location types with geo-social-temporal pattern mining
Anwar, Tarique, Liao, Kewen, Goyal, Angelic, Sellis, Timos, Kayes, A. S. M. and Shen, Haifeng. (2020). Inferring location types with geo-social-temporal pattern mining. IEEE Access. 8, pp. 154789-154799. https://doi.org/10.1109/ACCESS.2020.3018997
##### Temporal betweenness centrality in dynamic graphs
Tsalouchidou, Ioanna, Baeza-Yates, Ricardo, Bonchi, Francesco, Liao, Kewen and Sellis, Timos. (2020). Temporal betweenness centrality in dynamic graphs. International Journal of Data Science and Analytics. 9(3), pp. 257 - 272. https://doi.org/10.1007/s41060-019-00189-x
##### Fast anomaly detection in multiple multi-dimensional data streams
Sun, Hongyu, He, Qiang, Liao, Kewen, Sellis, Timos, Guo, Longkun, Zhang, Xuyun, Shen, Jun and Chen, Feifei. (2019). Fast anomaly detection in multiple multi-dimensional data streams. 2019 IEEE International Conference on Big Data. Los Angeles, California, United States of America 09 - 12 Dec 2019 IEEE Computer Society. pp. 1218-1223 https://doi.org/10.1109/BigData47090.2019.9006354
##### Performance-aware cost-effective resource provisioning for future grid iot-cloud system
Li, Weiling, Liao, Kewen, He, Qiang and Xia, Yunni. (2019). Performance-aware cost-effective resource provisioning for future grid iot-cloud system. Journal of Energy Engineering. 145(5), pp. 2-13. https://doi.org/10.1061/(ASCE)EY.1943-7897.0000611
##### On effective and efficient graph edge labeling
Goonetilleke, Oshini, Koutra, Danai, Liao, Kewen and Sellis, Timos. (2019). On effective and efficient graph edge labeling. Distributed and Parallel Databases. 37(1), pp. 5-38. https://doi.org/10.1007/s10619-018-7234-4
##### Contextual community search over large social networks
Chen, Lu, Liu, Chengfei, Liao, Kewen, Li, Jianxin and Zhou, Rui. (2019). Contextual community search over large social networks. 35th International Conference on Data Engineering (ICDE). Macao, China: IEEE Computer Society. pp. 88 - 99 https://doi.org/10.1109/ICDE.2019.00017
##### System and method for object matching
Liao, K. and Dodballapur, Veena. (2018). System and method for object matching US 10 , 043 , 103 B2
##### Efficient algorithms for flexible sweep coverage in crowdsensing
Huang, Peihuang, Zhu, Wenxing, Liao, Kewen, Sellis, Timos, Yu, Zhiyong and Guo, Longkun. (2018). Efficient algorithms for flexible sweep coverage in crowdsensing. IEEE Access. 6, pp. 50055-50065. https://doi.org/10.1109/ACCESS.2018.2868931
##### Classification and annotation of open internet of things datastreams
Montori, Federico, Liao, Kewen, Jayaraman, Prem Prakash, Bononi, Luciano, Sellis, Timos and Georgakopoulos, Dimitrios. (2018). Classification and annotation of open internet of things datastreams. 19th International Conference, Web Information Systems Engineering, WISE 2018. Dubai, United Arab Emirates 12 2018 - 15 Nov 2019 Springer. pp. 209-224 https://doi.org/10.1007/978-3-030-02925-8_15
##### A fast algorithm for optimally finding partially disjoint shortest paths
Guo, Longkun, Deng, Yunyun, Liao, Kewen, He, Qiang, Sellis, Timos and Hu, Zheshan. (2018). A fast algorithm for optimally finding partially disjoint shortest paths. Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18), Stockholm, Sweden, July 13-19, 2018. Stockholm, Sweden: International Joint Conferences on Artificial Intelligence. pp. 1456 - 1462 https://doi.org/10.24963/ijcai.2018/202
##### A cost model for long-term compressed data retention
Liao, Kewen, Moffat, Alistair, Petri, Matthias and Wirth, Anthony. (2017). A cost model for long-term compressed data retention. 10th International Conference on Web Search and Data Mining. United States of America: Association for Computing Machinery. pp. 241 - 249 https://doi.org/10.1145/3018661.3018738
##### Edge labeling schemes for graph data
Goonetilleke, Oshini, Koutra, Danai, Sellis, Timos and Liao, Kewen. (2017). Edge labeling schemes for graph data. 29th International Conference on Scientific and Statistical Database Management. United States of America: Association for Computing Machinery. pp. 1 - 12 https://doi.org/10.1145/3085504.3085516
##### Effective construction of relative Lempel-Ziv dictionaries
Liao, Kewen, Petri, Matthias, Moffat, Alistair and Wirth, Anthony. (2016). Effective construction of relative Lempel-Ziv dictionaries. WWW '16: 25th International World Wide Web Conference. Switzerland: Association for Computing Machinery. pp. 807 - 816 https://doi.org/10.1145/2872427.2883042
##### Improved approximation algorithms for constrained fault-tolerant resource allocation
Liao, Kewen, Shen, Hong and Guo, Longkun. (2015). Improved approximation algorithms for constrained fault-tolerant resource allocation. Theoretical Computer Science. 590, pp. 118-128. https://doi.org/10.1016/j.tcs.2015.02.029
##### Improved approximation algorithms for computing k disjoint paths subject to two constraints
Guo, Longkun, Shen, Hong and Liao, Kewen. (2015). Improved approximation algorithms for computing k disjoint paths subject to two constraints. Journal of Combinatorial Optimization. 29(1), pp. 153-164. https://doi.org/10.1007/s10878-013-9693-x
##### Brief announcement : Efficient approximation algorithms for computing k disjoint restricted shortest paths
Guo, Longkun, Liao, Kewen, Shen, Hong and Li, Peng. (2015). Brief announcement : Efficient approximation algorithms for computing k disjoint restricted shortest paths. 27th ACM Symposium on Parallelism in Algorithms and Architectures. Portland, Oregon, United States of America 13 - 15 Jun 2015 Association for Computing Machinery. pp. 62β64 https://doi.org/10.1145/2755573.2755608
##### On the shallow-light Steiner tree problem
Guo, Longkun, Liao, Kewen and Shen, Hong. (2014). On the shallow-light Steiner tree problem. 15th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2014). Hong Kong, China 09 - 14 Dec 2014 IEEE Computer Society. pp. 56-60 https://doi.org/10.1109/PDCAT.2014.17
##### Effect of off-zenith observations on reducing the impact of precipitation on ground-based microwave radiometer measurement accuracy
Xu, Guirong, Stick Ware, Randolph, Zhang, Wengang, Feng, Guangliu, Liao, Kewen and Liu, Yibing. (2014). Effect of off-zenith observations on reducing the impact of precipitation on ground-based microwave radiometer measurement accuracy. Atmospheric Research. 140-141, pp. 85 - 94. https://doi.org/10.1016/j.atmosres.2014.01.021