Approximation algorithm for the balanced 2-correlation clustering problem on well-proportional graphs. (English) Zbl 1482.68176
Zhang, Zhao (ed.) et al., Algorithmic aspects in information and management. 14th international conference, AAIM 2020, Jinhua, China, August 10–12, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12290, 97-107 (2020).
Summary: In this paper, we consider the balanced 2-correlation clustering problem on well-proportional graphs, which has applications in protein interaction networks, cross-lingual link detection, communication networks, among many others. Given a complete graph \(G=(V,E)\) with each edge \((u,v)\in E\) labeled by \(+\) or \(-\), the goal is to partition the vertices into two clusters of equal size to minimize the number of positive edges whose endpoints lie in different clusters plus the number of negative edges whose endpoints lie in the same cluster. We provide a \((3,\max\{4(M+1),16\})\)-balanced approximation algorithm for the balanced 2-correlation clustering problem on \(M\)-proportional graphs. Namely, the cost of the vertex partition \(\{V_1, V_2\}\) returned by the algorithm is at most \(\max \{4(M+1),16\}\) times the optimum solution, and \(\min \{|V_1|,|V_2|\} \le 3\max\{|V_1|, |V_2|\}\).
For the entire collection see [Zbl 1464.68025].
For the entire collection see [Zbl 1464.68025].
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 68W25 | Approximation algorithms |
References:
| [1] | Achtert, E., \(B \ddot{\rm o}\) hm, C., David, J., \(Kr \ddot{\rm o}\) ger, P., Zimek, A.: Global correlation clustering based on the Hough transform. Stat. Anal. Data Mining 1, 111-127 (2010) |
| [2] | Ahmadian, S., Norouzi-Fard, A., Svensson, O., Ward, J.: Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms. In: Proceedings of FOCS, pp. 61-72 (2017) · Zbl 1450.90005 |
| [3] | Ahn, K.J., Cormode, G., Guha, S., Mcgregor, A., Wirth, A.: Correlation clustering in data streams. In: Proceedings of ICML, pp. 2237-2246 (2015) · Zbl 1515.68281 |
| [4] | Ailon, N.; Avigdor-Elgrabli, N.; Liberty, E.; Zuylen, AV, Improved approximation algorithms for bipartite correlation clustering, SIAM J. Comput., 41, 1110-1121 (2012) · Zbl 1257.68076 · doi:10.1137/110848712 |
| [5] | Ailon, N., Charikar, M., Newman, A.: Aggregating inconsistent information: ranking and clustering. J. ACM 55(5) (2008). Article No. 23 · Zbl 1325.68102 |
| [6] | Amit, N.: The bicluster graph editing problem. Diss, Tel Aviv University (2004) |
| [7] | Arthur, D., Vassilvitskii, S.: \(k\)-Means++: the advantages of careful seeding. In: Proceedings of SODA, pp. 1027-1035 (2007) · Zbl 1302.68273 |
| [8] | Bansal, N.; Blum, A.; Chawla, S., Correlation clustering, Mach. Learn., 56, 89-113 (2004) · Zbl 1089.68085 · doi:10.1023/B:MACH.0000033116.57574.95 |
| [9] | Behsaz, B.; Friggstad, Z.; Salavatipour, MR; Sivakumar, R.; Halldórsson, MM; Iwama, K.; Kobayashi, N.; Speckmann, B., Approximation algorithms for min-sum k-clustering and balanced k-median, Automata, Languages, and Programming, 116-128 (2015), Heidelberg: Springer, Heidelberg · Zbl 1418.68238 · doi:10.1007/978-3-662-47672-7_10 |
| [10] | Bonchi, F.: Overlapping correlation clustering. Knowl. Inf. Syst. 35, 1-32 (2013) |
| [11] | Braverman, V., Lang, H., Levin, K., Monemizadeh, M.: Clustering problems on sliding windows. In: Proceedings of SODA, pp. 1374-1390 (2016) · Zbl 1411.68182 |
| [12] | Byrka, J., Fleszar, K., Rybicki, B., Spoerhase, J.: Bi-factor approximation algorithms for hard capacitated \(k\)-median problems. In: Proceedings of SODA, pp. 722-736 (2015) · Zbl 1371.90072 |
| [13] | Charikar, M.; Guruswami, V.; Wirth, A., Clustering with qualitative information, J. Comput. Syst. Sci., 71, 360-383 (2005) · Zbl 1094.68075 · doi:10.1016/j.jcss.2004.10.012 |
| [14] | Chawla, S., Makarychev, K., Schramm, T., Yaroslavtsev, G.: Near optimal LP rounding algorithm for correlation clustering on complete and complete \(k\)-partite graphs. In: Proceedings of STOC, pp. 219-228 (2015) · Zbl 1321.68495 |
| [15] | Demaine, E.; Emanuel, D.; Fiat, A.; Immorlica, N., Correlation clustering in general weighted graphs, Theoret. Comput. Sci., 361, 172-187 (2006) · Zbl 1099.68074 · doi:10.1016/j.tcs.2006.05.008 |
| [16] | Frieze, A.; Jerrum, M., Improved approximation algorithms for max \(k\)-cut and max bisection, Algorithmica, 18, 67-81 (1997) · Zbl 0873.68078 · doi:10.1007/BF02523688 |
| [17] | Giotis, I., Guruswami, V.: Correlation clustering with a fixed number of clusters. In: Proceedings of SODA, pp. 1167-1176 (2006) · Zbl 1194.62087 |
| [18] | Goemans, MX; Williamson, DP, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42, 1115-1145 (1995) · Zbl 0885.68088 · doi:10.1145/227683.227684 |
| [19] | Hendrickx, JM; Tsitsiklis, JN, Convergence of type-symmetric and cut-balanced consensus seeking systems, IEEE Trans. Autom. Control, 58, 214-218 (2013) · Zbl 1369.93025 · doi:10.1109/TAC.2012.2203214 |
| [20] | Ji, S.; Xu, D.; Li, M.; Wang, Y.; Du, D-Z; Li, L.; Sun, X.; Zhang, J., Approximation algorithm for the correlation clustering problem with non-uniform hard constrained cluster sizes, Algorithmic Aspects in Information and Management, 159-168 (2019), Cham: Springer, Cham · Zbl 1534.68261 · doi:10.1007/978-3-030-27195-4_15 |
| [21] | Kuila, P.; Jana, PK, Approximation schemes for load balanced clustering in wireless sensor networks, J. Supercomput., 68, 1, 87-105 (2013) · doi:10.1007/s11227-013-1024-6 |
| [22] | Li, S.: On uniform capacitated \(k\)-median beyond the natural LP relaxation. ACM Trans. Algorithms 13(2) (2017). Article No. 22 · Zbl 1451.90089 |
| [23] | Li, M.; Xu, D.; Zhang, D.; Zhang, T., A streaming algorithm for \(k\)-means with approximate coreset, Asia Pacific J. Oper. Res., 36, 1, 1950006 (2019) · Zbl 1411.62169 · doi:10.1142/S0217595919500064 |
| [24] | Liao, Y.; Qi, H.; Li, W., Load-balanced clustering algorithm with distributed self-organization for wireless sensor networks, IEEE Sens. J., 13, 1498-1506 (2013) · doi:10.1109/JSEN.2012.2227704 |
| [25] | Mathieu, C.; Sankur, O.; Schudy, W., Online correlation clustering, Comput. Stat., 21, 211-229 (2010) · Zbl 1230.68219 |
| [26] | Mathieu, C., Schudy, W.: Correlation clustering with noisy input. In: Proceedings of SODA, pp. 712-728 (2010) · Zbl 1288.68197 |
| [27] | Puleo, GJ; Milenkovic, O., Correlation clustering with constrained cluster sizes and extended weights bounds, SIAM J. Optim., 25, 1857-1872 (2015) · Zbl 1337.68296 · doi:10.1137/140994198 |
| [28] | Puleo, GJ; Milenkovic, O., Correlation clustering and biclustering with locally bounded errors, IEEE Trans. Inf. Theory, 64, 4105-4119 (2018) · Zbl 1395.62172 · doi:10.1109/TIT.2018.2819696 |
| [29] | Shamir, R.; Sharan, R.; Tsur, D., Cluster graph modification problems, Discrete Appl. Math., 144, 173-182 (2004) · Zbl 1068.68107 · doi:10.1016/j.dam.2004.01.007 |
| [30] | Swamy, C.: Correlation clustering: maximizing agreements via semidefinite programming. In: Proceedings of SODA, pp. 526-527 (2004) · Zbl 1318.68197 |
| [31] | Zhao, M.; Yang, Y.; Wang, C., Mobile data gathering with load balanced clustering and dual data uploading in wireless sensor networks, IEEE Trans. Mob. Comput., 14, 770-785 (2015) · doi:10.1109/TMC.2014.2338315 |
| [32] | Pereira, R.; Serrano, J., A review of methods used on IT maturity models development: a systematic literature review and a critical analysis, J. Inf. Technol., 35, 2, 161-178 (2020) · doi:10.1177/0268396219886874 |
| [33] | Nambisan, S., Wright, M., Feldman, M.: The digital transformation of innovation and entrepreneurship: progress, challenges and key themes. Res. Policy 48(8) (2019). doi:10.1016/j.respol.2019.03.018 |
| [34] | Loonam, J.; Eaves, S.; Kumar, V.; Parry, G., Towards digital transformation: lessons learned from traditional organizations, Strateg. Chang., 27, 101-109 (2018) · doi:10.1002/jsc.2185 |
| [35] | Matt, C.; Hess, T.; Benlian, A., Digital transformation strategies, Bus. Inf. Syst. Eng., 57, 5, 339-343 (2015) · doi:10.1007/s12599-015-0401-5 |
| [36] | Misuraca, G.; Alfano, G.; Viscusi, G., A multi-level framework for ICT-enabled governance: assessing the non-technical dimensions of’government openness’, Electron. J. e-Govern., 9, 152-165 (2011) |
| [37] | Larsson, H.; Grönlund, A., Future-oriented eGovernance: the sustainability concept in eGov research, and ways forward, Gov. Inf. Q., 31, 137-149 (2014) · doi:10.1016/j.giq.2013.07.004 |
| [38] | Normile, D.: Coronavirus cases have dropped sharply in South Korea. What’s the secret to its success?, https://www.sciencemag.org/news/2020/03/coronavirus-cases-have-dropped-sharply-south-korea-whats-secret-its-success# |
| [39] | Strickland, E.: An Official WHO Coronavirus App Will Be a “Waze for COVID-19.” IEEE Spectr (2020) |
| [40] | Giddens, A., The Constitution of Society - Outline of the Theory of Structuration (1984), Berkeley and Los Angeles: University of California Press, Berkeley and Los Angeles |
| [41] | Misuraca, G.; Viscusi, G.; Pasi, G.; Scholl, HJ, Digital governance challenges for ICT-enabled innovation of social protection systems in the EU, IFIP EGOV and ePart 2016 (2016), Guimarães: IOS Press, Guimarães |
| [42] | Helsper, EJ, The social relativity of digital exclusion: applying relative deprivation theory to digital inequalities, Commun. Theory., 27, 223-242 (2016) · doi:10.1111/comt.12110 |
| [43] | Hargittai, E., Piper, A.M., Morris, M.R.: From internet access to internet skills: digital inequality among older adults. University Access Information Society (2018) |
| [44] | Hargittai, E.; Hinnant, A., Digital inequality: differences in young adults’ use of the internet, Communic. Res., 35, 602-621 (2008) · doi:10.1177/0093650208321782 |
| [45] | Misuraca, G., van Noordt, C.: Overview of the use and impact of AI in public services in the EU, EUR 30255 EN. Publications Office of the European Union, Luxembourg (2020). doi:10.2760/039619. https://ec.europa.eu/jrc/en/publication/eur-scientific-and-technical-research-reports/ai-watch-artificial-intelligence-public-services. ISBN 978-92-76-19540-5. JRC120399 |
| [46] | vbjk: Kind & Gezin (Child & Family). https://vbjk.be/en/partners/kind-gezin |
| [47] | Ranerup, A.; Henriksen, HZ, Value positions viewed through the lens of automated decision-making: the case of social services, Gov. Inf. Q., 36, 101377 (2019) · doi:10.1016/j.giq.2019.05.004 |
| [48] | Engels, F.; Wentland, A.; Pfotenhauer, SM, Testing future societies? Developing a framework for test beds and living labs as instruments of innovation governance, Res. Policy, 48, 103826 (2019) · doi:10.1016/j.respol.2019.103826 |
| [49] | Kela: About Kela. https://www.kela.fi/web/en/about-kela |
| [50] | Mchangama, J., Liu, H.-Y.: The Welfare State Is Committing Suicide by Artificial Intelligence. https://foreignpolicy.com/2018/12/25/the-welfare-state-is-committing-suicide-by-artificial-intelligence/ |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
