{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:13Z","timestamp":1740109333717,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2023,4,10]],"date-time":"2023-04-10T00:00:00Z","timestamp":1681084800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,4,10]],"date-time":"2023-04-10T00:00:00Z","timestamp":1681084800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100013209","name":"Hellenic Foundation for Research and Innovation","doi-asserted-by":"publisher","award":["00704"],"award-info":[{"award-number":["00704"]}],"id":[{"id":"10.13039\/501100013209","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/P02002X\/1"],"award-info":[{"award-number":["EP\/P02002X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,9]]},"abstract":"Abstract<\/jats:title>Let V<\/jats:italic> be a set of n<\/jats:italic> vertices, $${\\mathcal M}$$<\/jats:tex-math>\n M<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> a set of m<\/jats:italic> labels, and let $${\\textbf{R}}$$<\/jats:tex-math>\n R<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> be an $$m \\times n$$<\/jats:tex-math>\n \n m<\/mml:mi>\n \u00d7<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> matrix ofs independent Bernoulli random variables with probability of success p<\/jats:italic>; columns of $${\\textbf{R}}$$<\/jats:tex-math>\n R<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> are incidence vectors of label sets assigned to vertices. A random instance $$G(V, E, {\\textbf{R}}^T {\\textbf{R}})$$<\/jats:tex-math>\n \n G<\/mml:mi>\n (<\/mml:mo>\n V<\/mml:mi>\n ,<\/mml:mo>\n E<\/mml:mi>\n ,<\/mml:mo>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n T<\/mml:mi>\n <\/mml:msup>\n R<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of the weighted random intersection graph model is constructed by drawing an edge with weight equal to the number of common labels (namely $$[{\\textbf{R}}^T {\\textbf{R}}]_{v,u}$$<\/jats:tex-math>\n \n \n [<\/mml:mo>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n T<\/mml:mi>\n <\/mml:msup>\n R<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n \n v<\/mml:mi>\n ,<\/mml:mo>\n u<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>) between any two vertices u<\/jats:italic>,\u00a0v<\/jats:italic> for which this weight is strictly larger than 0. In this paper we study the average case analysis of Weighted Max Cut<\/jats:sc>, assuming the input is a weighted random intersection graph, i.e. given $$G(V, E, {\\textbf{R}}^T {\\textbf{R}})$$<\/jats:tex-math>\n \n G<\/mml:mi>\n (<\/mml:mo>\n V<\/mml:mi>\n ,<\/mml:mo>\n E<\/mml:mi>\n ,<\/mml:mo>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n T<\/mml:mi>\n <\/mml:msup>\n R<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> we wish to find a partition of V<\/jats:italic> into two sets so that the total weight of the edges having exactly one endpoint in each set is maximized. In particular, we initially prove that the weight of a maximum cut of $$G(V, E, {\\textbf{R}}^T {\\textbf{R}})$$<\/jats:tex-math>\n \n G<\/mml:mi>\n (<\/mml:mo>\n V<\/mml:mi>\n ,<\/mml:mo>\n E<\/mml:mi>\n ,<\/mml:mo>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n T<\/mml:mi>\n <\/mml:msup>\n R<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is concentrated around its expected value, and then show that, when the number of labels is much smaller than the number of vertices (in particular, $$m=n^{\\alpha }, \\alpha <1$$<\/jats:tex-math>\n \n m<\/mml:mi>\n =<\/mml:mo>\n \n n<\/mml:mi>\n \u03b1<\/mml:mi>\n <\/mml:msup>\n ,<\/mml:mo>\n \u03b1<\/mml:mi>\n <<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>), a random partition of the vertices achieves asymptotically optimal cut weight with high probability. Furthermore, in the case $$n=m$$<\/jats:tex-math>\n \n n<\/mml:mi>\n =<\/mml:mo>\n m<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and constant average degree (i.e. $$p = \\frac{\\Theta (1)}{n}$$<\/jats:tex-math>\n \n p<\/mml:mi>\n =<\/mml:mo>\n \n \n \u0398<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>), we show that with high probability, a majority type randomized algorithm outputs a cut with weight that is larger than the weight of a random cut by a multiplicative constant strictly larger than 1. Then, we formally prove a connection between the computational problem of finding a (weighted) maximum cut in $$G(V, E, {\\textbf{R}}^T {\\textbf{R}})$$<\/jats:tex-math>\n \n G<\/mml:mi>\n (<\/mml:mo>\n V<\/mml:mi>\n ,<\/mml:mo>\n E<\/mml:mi>\n ,<\/mml:mo>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n T<\/mml:mi>\n <\/mml:msup>\n R<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and the problem of finding a 2-coloring that achieves minimum discrepancy for a set system $$\\Sigma $$<\/jats:tex-math>\n \u03a3<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with incidence matrix $${\\textbf{R}}$$<\/jats:tex-math>\n R<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> (i.e. minimum imbalance over all sets in $$\\Sigma $$<\/jats:tex-math>\n \u03a3<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>). We exploit this connection by proposing a (weak) bipartization algorithm for the case $$m=n, p = \\frac{\\Theta (1)}{n}$$<\/jats:tex-math>\n \n m<\/mml:mi>\n =<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n p<\/mml:mi>\n =<\/mml:mo>\n \n \n \u0398<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> that, when it terminates, its output can be used to find a 2-coloring with minimum discrepancy in a set system with incidence matrix $${\\textbf{R}}$$<\/jats:tex-math>\n R<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. In fact, with high probability, the latter 2-coloring corresponds to a bipartition with maximum cut-weight in $$G(V, E, {\\textbf{R}}^T {\\textbf{R}})$$<\/jats:tex-math>\n \n G<\/mml:mi>\n (<\/mml:mo>\n V<\/mml:mi>\n ,<\/mml:mo>\n E<\/mml:mi>\n ,<\/mml:mo>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n T<\/mml:mi>\n <\/mml:msup>\n R<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Finally, we prove that our (weak) bipartization algorithm terminates in polynomial time, with high probability, at least when $$p = \\frac{c}{n}, c<1$$<\/jats:tex-math>\n \n p<\/mml:mi>\n =<\/mml:mo>\n \n c<\/mml:mi>\n n<\/mml:mi>\n <\/mml:mfrac>\n ,<\/mml:mo>\n c<\/mml:mi>\n <<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00453-023-01121-3","type":"journal-article","created":{"date-parts":[[2023,4,10]],"date-time":"2023-04-10T10:02:35Z","timestamp":1681120955000},"page":"2817-2842","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["MAX CUT in Weighted Random Intersection Graphs and Discrepancy of Sparse Random Set Systems"],"prefix":"10.1007","volume":"85","author":[{"given":"Sotiris","family":"Nikoletseas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9837-2632","authenticated-orcid":false,"given":"Christoforos","family":"Raptopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,4,10]]},"reference":[{"key":"1121_CR1","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1145\/568522.568523","volume":"34","author":"J D\u00edaz","year":"2002","unstructured":"D\u00edaz, J., Petit, J., Serna, M.: A survey on graph layout problems. ACM Comput. Surv. 34, 313\u2013356 (2002)","journal-title":"ACM Comput. Surv."},{"key":"1121_CR2","series-title":"DIMACS series in Discrete Mathematics and Theoretical Computer Science","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1090\/dimacs\/020\/04","volume-title":"Maximum cuts and largest bipartite subgraphs","author":"S Poljak","year":"1995","unstructured":"Poljak, S., Tuza, Z.: Maximum cuts and largest bipartite subgraphs. DIMACS series in Discrete Mathematics and Theoretical Computer Science, pp. 181\u2013244. American Mathematical Society, Providence (1995)"},{"issue":"3","key":"1121_CR3","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1287\/opre.36.3.493","volume":"36","author":"F Barahona","year":"1988","unstructured":"Barahona, F., Gr\u00f6tschel, M., J\u00fcnger, M., Reinelt, G.: An application of combinatorial optimization to statistical physics and circuit layout design. Oper. Res. 36(3), 493\u2013513 (1988)","journal-title":"Oper. Res."},{"key":"1121_CR4","first-page":"197","volume":"4265","author":"J Poland","year":"2006","unstructured":"Poland, J., Zeugmann, T.: Clustering pairwise distances with missing data: maximum cuts versus normalized cuts. Comput. Sci. 4265, 197\u2013208 (2006)","journal-title":"Comput. Sci."},{"issue":"3","key":"1121_CR5","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C Papadimitriou","year":"1991","unstructured":"Papadimitriou, C., Yannakakis, M.: Optimization, approximation, and complexity classes. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"Comput. Syst. Sci."},{"issue":"2","key":"1121_CR6","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1002\/rsa.20738","volume":"52","author":"D Gamarnik","year":"2018","unstructured":"Gamarnik, D., Li, Q.: On the max-cut of sparse random graphs. Random Struct. Algorithms 52(2), 219\u2013262 (2018)","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"1121_CR7","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1002\/rsa.20096","volume":"28","author":"A Coja-Oghlan","year":"2006","unstructured":"Coja-Oghlan, A., Moore, C., Sanwalani, V.: Max k-cut and approximating the chromatic number of random graphs. Random Struct. Algorithms 28(3), 289\u2013322 (2006)","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"1121_CR8","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1002\/rsa.20015","volume":"24","author":"D Coppersmith","year":"2004","unstructured":"Coppersmith, D., Gamarnik, D., Hajiaghayi, M., Sorkin, G.: Random maxsat, random maxcut, and their phase transitions. Rand. Struct. Algorithms 24(4), 502\u2013545 (2004)","journal-title":"Rand. Struct. Algorithms"},{"key":"1121_CR9","doi-asserted-by":"publisher","first-page":"4080","DOI":"10.1214\/12-AOP816","volume":"41","author":"M Bayati","year":"2013","unstructured":"Bayati, M., Gamarnik, D., Tetal, P.: Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. Ann. Probab. 41, 4080\u20134115 (2013)","journal-title":"Ann. Probab."},{"issue":"2","key":"1121_CR10","doi-asserted-by":"publisher","first-page":"1190","DOI":"10.1214\/15-AOP1084","volume":"45","author":"A Dembo","year":"2017","unstructured":"Dembo, A., Montanari, A., Sen, S.: Extremal cuts of sparse random graphs. Ann. Probab. 45(2), 1190\u20131217 (2017)","journal-title":"Ann. Probab."},{"key":"1121_CR11","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1017\/S0963548398003459","volume":"8","author":"M Karo\u0144ski","year":"1999","unstructured":"Karo\u0144ski, M., Scheinerman, E., Singer-Cohen, K.: On random intersection graphs: the subgraph problem. Comb. Probab. Comput. 8, 131\u2013159 (1999)","journal-title":"Comb. Probab. Comput."},{"key":"1121_CR12","doi-asserted-by":"crossref","unstructured":"Nikoletseas, S., Raptopoulos, C., Spirakis, P.: Communication and security in random intersection graphs models. In: Proceedings of the 12th IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (WOWMOM), pp. 1\u20136 (2011)","DOI":"10.1109\/WoWMoM.2011.5986170"},{"key":"1121_CR13","doi-asserted-by":"publisher","unstructured":"Bloznelis, M., Godehardt, E., Jaworski, J., Kurauskas, V., Rybarczyk, K.: Recent progress in complex network analysis: models of random intersection graphs. In: Lausen, B., Krolak-Schwerdt, S., B\u00f6hmer, M. (eds.) Data Science, Learning by Latent Structures, and Knowledge Discovery. Studies in Classification, Data Analysis, and Knowledge Organization, pp. 69\u201378. Springer, Berlin, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-44983-7_6","DOI":"10.1007\/978-3-662-44983-7_6"},{"key":"1121_CR14","volume-title":"Handbook of Approximation Algorithms and Metaheuristics","author":"S Nikoletseas","year":"2018","unstructured":"Nikoletseas, S., Raptopoulos, C., Spirakis, P.: Efficient approximation algorithms in random intersection graphs. In: Gonzalez, T.F. (ed.) Handbook of Approximation Algorithms and Metaheuristics, 2nd edn. Chapman and Hall\/CRC, Boca Raton (2018)","edition":"2"},{"issue":"2","key":"1121_CR15","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1002\/(SICI)1098-2418(200003)16:2<156::AID-RSA3>3.0.CO;2-H","volume":"16","author":"J Fill","year":"2000","unstructured":"Fill, J., Sheinerman, E., Singer-Cohen, K.: Random intersection graphs when $$m = \\omega (n)$$: an equivalence theorem relating the evolution of the $$g(n, m, p)$$ and $$g(n, p)$$ models. Random Struct. Algorithms 16(2), 156\u2013176 (2000)","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"1121_CR16","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1002\/rsa.20750","volume":"52","author":"JH Kim","year":"2018","unstructured":"Kim, J.H., Lee, S.J., Na, J.: On the total variation distance between the binomial random graph and the random intersection graph. Random Struct. Algorithms 52(4), 662\u2013679 (2018)","journal-title":"Random Struct. Algorithms"},{"issue":"1\u20132","key":"1121_CR17","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/rsa.20356","volume":"38","author":"K Rybarczyk","year":"2011","unstructured":"Rybarczyk, K.: Equivalence of a random intersection graph and $$g(n, p)$$. Random Struct. Algorithms 38(1\u20132), 205\u2013234 (2011)","journal-title":"Random Struct. Algorithms"},{"key":"1121_CR18","doi-asserted-by":"crossref","unstructured":"Raptopoulos, C., Spirakis, P.: Simple and efficient greedy algorithms for hamilton cycles in random intersection graphs. In: Proceedings of the 16th International Symposium on Algorithms and Computation (ISAAC), pp. 493\u2013504 (2005)","DOI":"10.1007\/11602613_50"},{"key":"1121_CR19","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21054","author":"D Altschuler","year":"2021","unstructured":"Altschuler, D., Niles-Weed, J.: The discrepancy of random rectangular matrices. Random Struct. Algorithms (2021). https:\/\/doi.org\/10.1002\/rsa.21054","journal-title":"Random Struct. Algorithms"},{"key":"1121_CR20","doi-asserted-by":"crossref","unstructured":"Hoberg, R., Rothvoss, T.: A fourier-analytic approach for the discrepancy of random set systems. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2547\u20132556 (2019)","DOI":"10.1137\/1.9781611975482.156"},{"key":"1121_CR21","unstructured":"Ezra, E., Lovett, S.: On the beck-fiala conjecture for random set systems. In: Proceedings of Approximation, Randomization, and Combinatorial Optimization - Algorithms and Techniques (APPROX-RANDOM), pp. 29\u201312910 (2016)"},{"key":"1121_CR22","unstructured":"Potukuchi, A.: Discrepancy in random hypergraph models. CoRR abs arxiv: 1811.01491 (2018)"},{"key":"1121_CR23","doi-asserted-by":"crossref","unstructured":"Bansal, N., Meka, R.: On the discrepancy of random low degree set systems. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms SODA, pp. 2557\u20132564 (2019)","DOI":"10.1137\/1.9781611975482.157"},{"key":"1121_CR24","unstructured":"Nikoletseas, S., Raptopoulos, C., Spirakis, P.: Max cut in weighted random intersection graphs and discrepancy of sparse random set systems. In: Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC), pp. 1\u201316 (2021)"},{"issue":"1","key":"1121_CR25","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1137\/050647153","volume":"23","author":"M Behrisch","year":"2009","unstructured":"Behrisch, M., Taraz, A., Ueckerdt, M.: Coloring random intersection graphs and complex networks. SIAM J. Discret. Math. 23(1), 288\u2013299 (2009)","journal-title":"SIAM J. Discret. Math."},{"key":"1121_CR26","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1134\/S1064562414030338","volume":"89","author":"I Shevtsova","year":"2014","unstructured":"Shevtsova, I.: On the absolute constants in the Berry-Esseen-type inequalities. Doklady Math. 89, 378\u2013381 (2014)","journal-title":"Doklady Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01121-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01121-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01121-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T15:03:58Z","timestamp":1695395038000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01121-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,10]]},"references-count":26,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["1121"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01121-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2023,4,10]]},"assertion":[{"value":"21 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 March 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 April 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}