Pith. sign in

REVIEW 2 major objections 6 minor 52 references

Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach

T0 review · 2 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A single primal-dual framework yields a linear-time optimal-ratio algorithm for Local ECC and the first true approximation algorithms for Robust and Global ECC.

desk verdict A careful, genuinely useful theory paper: first true approximations for Robust and Global ECC, a clean linear-time primal-dual for Local ECC, and honest hardness/gap results; the experiments are the weakest part but the core is solid. read the letter →

arxiv 2505.18043 v1 pith:B56D65SN submitted 2025-05-23 cs.LG cs.DBcs.DS

Changyeol Lee , Yongho Shin , Hyung-Chan An This is my paper · ORCID
classification cs.LGcs.DBcs.DS MSC 68W2568Q1705C65
keywords edge-coloredclusteringhypergraphoverlappingrobustprimal-dualapproximationalgorithmsintegralitygapinapproximabilitylinear-time
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to settle how well the three NP-hard variants of edge-colored clustering can be approximated without sacrificing speed. It claims that one LP-based combinatorial framework, built on the primal-dual method, achieves a $(b_{\mathrm{local}}+1)$-approximation in linear time for Local ECC and the first true, non-bicriteria $2(b_{\mathrm{robust}}+1)$- and $2(b_{\mathrm{global}}+1)$-approximations for Robust and Global ECC. The same analysis proves matching integrality gaps and, for Local ECC, hardness showing the ratio is essentially best possible under the Unique Games Conjecture. If correct, this replaces budget-violating bicriteria algorithms, answers two open questions from the previous literature, and gives practical algorithms that the experiments show beat the prior greedy method for Local ECC while improving solution quality for Robust and Global ECC at a modest runtime cost.

What carries the argument

The load-bearing mechanism is the primal-dual method run as a continuous-time dual increase process. The algorithms maintain a dual-feasible solution $\alpha,\beta,\lambda$ and a set $L$ of loose edges—edges whose constraint $\sum_{v\in e} \beta_{e,v} \le w_e$ is not yet tight—and increase dual variables at rates controlled by the number of distinct colors among each vertex's incident loose edges, $|\chi(\delta(v)\cap L)|$. The proof works by charging mistakes only to tight edges and comparing the rate at which the output cost grows to the rate at which the dual objective grows; that ratio is exactly what becomes the approximation factor. For Robust ECC, the key new LP constraint $z_v + \sum_{c\in C} x_{v,c} \le 1$ couples deletion and coloring decisions and reduces the integrality gap from infinite to $\Theta(b_{\mathrm{robust}})$.

What would settle it

Enumerate all edge-colored hypergraphs on at most eight vertices, run the proposed algorithms with $b_{\mathrm{local}}=1$ and $b_{\mathrm{robust}}=0$, and compare each output against a brute-force optimal coloring; any instance whose mistakes exceed $(b_{\mathrm{local}}+1)\cdot\mathrm{OPT}$ or $2(b_{\mathrm{robust}}+1)\cdot\mathrm{OPT}$ refutes Theorems 3.1 and 3.5.

Watch

Extended reading notes

Core claim

The paper establishes that all three NP-hard variants of edge-colored clustering admit combinatorial approximation algorithms with LP-certified guarantees. For Local ECC, the proposed algorithm colors each vertex with the colors of its incident loose edges once edge constraints go tight; every mistake is a tight edge, so the output cost can be charged against the dual of a natural LP relaxation, yielding a $(b_{\mathrm{local}}+1)$-approximation in linear time, an integrality gap converging to the same value, and UGC-based inapproximability matching it. For Robust ECC and Global ECC, a strengthened LP relaxation—the addition of the per-vertex constraint $z_v + \sum_{c\in C} x_{v,c} \le 1$ in the robust case—repairs an integrality gap that was previously infinite and makes possible the first true approximation algorithms, with ratios $2(b_{\mathrm{robust}}+1)$ and $2(b_{\mathrm{global}}+1)$. The paper also establishes bicriteria versions whose violation factors are $O(1)$, resolving the previously open question of whether Global ECC admits constant-factor, constant-violation approximation.

Load-bearing premise

The load-bearing premise is the Unique Games Conjecture, a widely used hardness-of-approximation assumption imported through the cited hypergraph vertex-cover result; if the conjecture fails, the claim that the Local ECC ratio is essentially best possible loses its support, though the positive algorithms and the P≠NP-based hardness remain intact.

Editorial extensions

If this is right

  • Local ECC is now settled up to a $(b_{\mathrm{local}}+1)$ ratio: the algorithm runs in linear time and, under UGC, no polynomial-time algorithm improves on the ratio.
  • Robust ECC no longer requires bicriteria algorithms that may exceed the deletion budget; a true $2(b_{\mathrm{robust}}+1)$-approximation exists.
  • Global ECC has both a true $2(b_{\mathrm{global}}+1)$-approximation and a bicriteria guarantee with constant factor and constant budget violation, answering the open question.
  • The benchmark experiments show the Local ECC algorithm beating the previous greedy algorithm in speed and solution quality, and the Robust/Global algorithms producing better solutions while strictly respecting budgets.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the approximation ratios depend on per-vertex color degree rather than hypergraph rank, one predicts the algorithms will scale well on high-rank hypergraphs such as recipe or co-purchase data; this is testable on the benchmarks with rank far above 2.
  • The strengthened robust LP constraint suggests a transferable recipe for other outlier-tolerant clustering problems, such as robust correlation clustering, where deletion and labeling decisions are usually handled separately.
  • A natural next step is to ask whether the factor-two gap between the Local ratio $b_{\mathrm{local}}+1$ and the Robust/Global ratios $2(b_{\mathrm{robust}}+1)$ and $2(b_{\mathrm{global}}+1)$ can be closed by dual fitting or local search; the paper does not address this.
  • The paper's final remark that the Local ECC algorithm is online could be developed into a streaming version with bounded memory; that extension is only implicit.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. The paper proposes primal-dual approximation algorithms for three edge-colored hypergraph clustering problems: Local ECC, Robust ECC, and Global ECC. For Local ECC it gives a (b_local+1)-approximation algorithm running in linear time, matching the previous LP-rounding ratio with a purely combinatorial implementation. For Robust ECC and Global ECC it gives true (non-bicriteria) approximation algorithms with ratios 2(b_robust+1) and 2(b_global+1), respectively, in both cases independent of the hypergraph rank. The paper further proves integrality gap lower bounds for the three LP relaxations, UGC-based and P != NP-based inapproximability results for Local ECC, and bicriteria approximation variants. Experiments on six benchmark datasets compare running time and solution quality against prior greedy and LP-rounding algorithms.

Significance. The main algorithmic results are significant: they replace bicriteria guarantees with true approximation ratios for Robust and Global ECC, obtain a linear-time combinatorial algorithm for Local ECC that matches the best known LP-based ratio, and the accompanying hardness results essentially determine the approximability of Local ECC up to a UGC assumption. The primal-dual analyses are detailed and appear sound in the core lemmas, with no fitted parameters and no circular dependence on the results being proved. The experimental evaluation is extensive and consistent with the theoretical findings, showing large practical speedups over LP-rounding and better solution quality than the previous combinatorial greedy algorithm.

major comments (2)
  1. [Appendix B.2 (proof of Theorem 3.2)] The integrality gap construction sets |V| = |E|/(b_local+1), but the argument that any set S of b_local+1 satisfied edges yields a node v_S that must be colored with b_local+1 colors requires V to contain all subsets of E of size b_local+1. With the stated |V|, a chosen set S of satisfied edges need not be one of the labels, so the contradiction does not follow. In fact, if the labels are chosen as a partition of E, each edge is incident to exactly one node and an integral solution can satisfy one edge per node, giving no gap. The proof can be repaired by setting |V| = binom(|E|, b_local+1); the fractional solution then satisfies the edge constraints and the lower bound of |E| - b_local mistakes goes through, yielding a gap converging to b_local+1. As written, however, the proof of the lower bound is invalid.
  2. [Section 4.1] The sentence 'we used our LP relaxation instead since we can prove that our relaxation always yields a better estimate of the true optimum' is unsupported and, for Local and Global ECC, appears to be false: for Local ECC the LP is exactly the one presented in Section 3.1 (the same as Crane et al.'s relaxation), and for Global ECC the paper states in Appendix D.3 that the LP is equivalent to Crane et al.'s. Only for Robust ECC does the added constraint z_v + sum_c x_{v,c} <= 1 strengthen the relaxation. The authors should either prove the claim for each problem or qualify it to Robust ECC; otherwise the relative-error comparisons are presented on an unclear basis.
minor comments (6)
  1. [Appendix B.5 (Algorithm 2)] The update line 'l_e <- l_e + min{slack(c), s*} / slack(c) * (w_e - l_e)' divides by slack(c); when slack(c) = 0 the expression is undefined, although in that case no update is needed. Please handle the zero-slack case explicitly.
  2. [Section 4.3] Typo: 'LP-rouding algorithm' should be 'LP-rounding algorithm'.
  3. [Appendix D.3 (Lemma D.2)] The notation budget_L(S) := sum_{v in R} (kappa_L(v) - 1) for S subset of V has an unused argument S; either remove S or define the function as intended over the relevant set.
  4. [Appendix C.5 (Theorem C.3)] The statement begins 'Suppose that b >= 1' but then uses b_robust; please make the variable consistent.
  5. [Appendix B.1 (Lemma B.3)] The proof states that a single iteration runs in O(d_v) and concludes linear total time; it should explicitly mention that the discretized Algorithm 2 performs at most one iteration per vertex, which is why the bound sums to O(sum_v d_v).
  6. [Section 3.1] For vertices with chi(delta(v) cap L) = empty, Algorithm 1 assigns the empty set; this is feasible for Local ECC but may be worth stating explicitly, and the arbitrary-color remark used in the other algorithms could be added for consistency.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: LP-primal-dual analyses are from-scratch and hardness rests on independent external theorems.

full rationale

The derivation chain is self-contained. Algorithm 1 is analyzed by maintaining a feasible dual solution and comparing the algorithm's cost against the dual objective via weak LP duality (Lemma B.2); no parameter is fitted and no target ratio is assumed. The Robust and Global proofs (Lemmas C.2 and D.2) similarly bound the dual objective directly from feasibility properties, with the R' / R'' and b' arguments justified by monotone dual increases and the loop termination conditions. The integrality-gap examples (Theorems 3.2, 3.7, 3.8) are explicit feasible fractional solutions, and the Local ECC hardness is a direct approximation-preserving reduction from Ek-Vertex-Cover using the external Bansal-Khot and Dinur et al. theorems; no result of this paper is used as an input to itself. There is no load-bearing self-citation: the authors cite no prior work of their own for any central premise. The only flagged passage is Section 4.1's assertion, 'we can prove that our relaxation always yields a better estimate of the true optimum,' which is an omitted proof and an experimental-methodology claim; it is not used in any theorem and is not circular, since the stronger LP immediately gives an improved lower bound. A minor, non-circular caveat is that the reduction in Appendix B.3 assumes the constructed edges e_w are distinct, so duplicate neighborhoods would need standard multiset handling; this is a correctness detail, not a circularity. Overall score 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No parameters are fitted to data; budgets and epsilon are inputs, and all constants are fixed by the proofs. The positive results rely only on standard LP duality. The hardness theorems rely on the Unique Games Conjecture and P != NP as cited external assumptions. No new physical or mathematical entities are postulated.

assumptions (3)
  • standard math Weak LP duality holds for the primal-dual pairs in Sections 3.1, C.1, and D.1
    Used throughout the proofs to convert feasible dual solutions into lower bounds on OPT, for example in Lemmas B.2, C.2, and D.2.
  • domain assumption The Unique Games Conjecture is true
    Invoked through Bansal-Khot [10] in Theorem B.4 to prove Theorem 3.3, the UGC-hardness of Local ECC within a factor of b_local+1-epsilon.
  • domain assumption P is not equal to NP
    Invoked through Dinur et al. [23] in Theorem B.5 to prove Theorem 3.4, the conditional NP-hardness of Local ECC within a factor of b_local-epsilon for b_local at least 2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach." pith.science (2026). https://pith.science/paper/B56D65SN

@misc{pith2026250518043,
  author       = {Pith},
  title        = {Pith review of: Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/B56D65SN}},
  note         = {Machine review of arXiv:2505.18043}
}
read the original abstract

Clustering is a fundamental task in both machine learning and data mining. Among various methods, edge-colored clustering (ECC) has emerged as a useful approach for handling categorical data. Given a hypergraph with (hyper)edges labeled by colors, ECC aims to assign vertex colors to minimize the number of edges where the vertex color differs from the edge's color. However, traditional ECC has inherent limitations, as it enforces a nonoverlapping and exhaustive clustering. To tackle these limitations, three versions of ECC have been studied: Local ECC and Global ECC, which allow overlapping clusters, and Robust ECC, which accounts for vertex outliers. For these problems, both linear programming (LP) rounding algorithms and greedy combinatorial algorithms have been proposed. While these LP-rounding algorithms provide high-quality solutions, they demand substantial computation time; the greedy algorithms, on the other hand, run very fast but often compromise solution quality. In this paper, we present an algorithmic framework that combines the strengths of LP with the computational efficiency of combinatorial algorithms. Both experimental and theoretical analyses show that our algorithms efficiently produce high-quality solutions for all three problems: Local, Global, and Robust ECC. We complement our algorithmic contributions with complexity-theoretic inapproximability results and integrality gap bounds, which suggest that significant theoretical improvements are unlikely. Our results also answer two open questions previously raised in the literature.

Figures

Figures reproduced from arXiv: 2505.18043 by the authors.

Figure 1
Figure 1. (a) Running times (in seconds) and (b) relative error estimates of the [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. (a) Running times (in seconds) and (b) relative error estimates of the [PITH_FULL_IMAGE:figures/full_fig_p026_2.png] view at source ↗
Figure 3
Figure 3. (a) Running times (in seconds) and (b) relative error estimates of the [PITH_FULL_IMAGE:figures/full_fig_p027_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

52 extracted references · 51 canonical work pages

  1. [1]

    Improved approximations for the max k-colored cluster- ing problem

    Alexander Ageev and Alexander Kononov. Improved approximations for the max k-colored cluster- ing problem. In Proceedings of the International Workshop on Approximation and Online Algorithms (WAOA), pages 1–10. Springer, 2014

    work page

  2. [2]

    A 0.3622-Approximation Algorithm for the Maximum k- Edge-Colored Clustering Problem

    Alexander Ageev and Alexander Kononov. A 0.3622-Approximation Algorithm for the Maximum k- Edge-Colored Clustering Problem. In International Conference on Mathematical Optimization Theory and Operations Research (MOTOR), pages 3–15. Springer, 2020. 5When we reran the proposed algorithm with the budget doubled, the number of mistakes made by the proposed a...

    work page 2020

  3. [3]

    Approximability and inapproximability for maximum k-edge-colored clustering problem

    Yousef M Alhamdan and Alexander Kononov. Approximability and inapproximability for maximum k-edge-colored clustering problem. In Computer Science–Theory and Applications: 14th International Computer Science Symposium in Russia (CSR) , pages 1–12. Springer, 2019

    work page 2019

  4. [4]

    Clustering in graphs and hypergraphs with categorical edge labels

    Ilya Amburg, Nate Veldt, and Austin Benson. Clustering in graphs and hypergraphs with categorical edge labels. In Proceedings of The Web Conference (WWW) , pages 706–717, 2020

    work page 2020

  5. [5]

    Diverse and experienced group discovery via hypergraph clustering

    Ilya Amburg, Nate Veldt, and Austin R Benson. Diverse and experienced group discovery via hypergraph clustering. In Proceedings of the 2022 SIAM International Conference on Data Mining (SDM) , pages 145–153. SIAM, 2022

    work page 2022

  6. [6]

    Improved theoretical and practical guarantees for chromatic correlation clustering

    Yael Anava, Noa Avigdor-Elgrabli, and Iftah Gamzu. Improved theoretical and practical guarantees for chromatic correlation clustering. In Proceedings of the 24th International Conference on World Wide Web (WWW) , pages 55–65, 2015

    work page 2015

  7. [7]

    Evolutionary algorithms for overlapping correlation clustering

    Carlos E Andrade, Mauricio GC Resende, Howard J Karloff, and Fl´ avio K Miyazawa. Evolutionary algorithms for overlapping correlation clustering. In Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation (GECCO) , pages 405–412, 2014

    work page 2014

  8. [8]

    Clustering on k-edge-colored graphs

    Eric Angel, Evripidis Bampis, A Kononov, Dimitris Paparas, Emmanouil Pountourakis, and Vassilis Zissimopoulos. Clustering on k-edge-colored graphs. Discrete Applied Mathematics , 211:15–22, 2016

    work page 2016

Show all 52 references
  1. [9]

    Correlation clustering

    Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine Learning, 56:89–113, 2004

    2004

  2. [10]

    Inapproximability of hypergraph vertex cover and applications to scheduling problems

    Nikhil Bansal and Subhash Khot. Inapproximability of hypergraph vertex cover and applications to scheduling problems. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 250–261. Springer, 2010

    2010

  3. [11]

    Cut, glue & cut: A fast, approximate solver for multicut partitioning

    Thorsten Beier, Thorben Kroeger, Jorg H Kappes, Ullrich Kothe, and Fred A Hamprecht. Cut, glue & cut: A fast, approximate solver for multicut partitioning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) , pages 73–80, 2014

    2014

  4. [12]

    Higher-order organization of complex networks

    Austin R Benson, David F Gleich, and Jure Leskovec. Higher-order organization of complex networks. Science, 353(6295):163–166, 2016

    2016

  5. [13]

    Linear time bounds for median computations

    Manuel Blum, Robert W Floyd, Vaughan Pratt, Ronald L Rivest, and Robert E Tarjan. Linear time bounds for median computations. In Proceedings of the 4th Annual ACM Symposium on Theory of Computing (STOC) , pages 119–124, 1972

    1972

  6. [14]

    Correlation Clustering

    Francesco Bonchi, David Garc ´ ıa-Soriano, and Francesco Gullo. Correlation Clustering . Morgan & Claypool Publishers, 2022

    2022

  7. [15]

    Chromatic correlation clustering

    Francesco Bonchi, Aristides Gionis, Francesco Gullo, Charalampos E Tsourakakis, and Antti Ukkonen. Chromatic correlation clustering. ACM Transactions on Knowledge Discovery from Data (TKDD) , 9(4):1–24, 2015

    2015

  8. [16]

    Overlapping correlation clustering

    Francesco Bonchi, Aristides Gionis, and Antti Ukkonen. Overlapping correlation clustering. In 2011 IEEE 11th International Conference on Data Mining (ICDM) , pages 51–60, 2011

    2011

  9. [17]

    A hybrid heuristic for the overlapping cluster editing problem

    Guilherme Oliveira Chagas, Luiz Antonio Nogueira Lorena, and Rafael Duarte Coelho dos Santos. A hybrid heuristic for the overlapping cluster editing problem. Applied Soft Computing , 81:105482, 2019

    2019

  10. [18]

    Hypergraph clustering: from blockmodels to modularity

    Philip S Chodrow, Nate Veldt, and Austin R Benson. Hypergraph clustering: from blockmodels to modularity. Science Advances, 2021. 11

    2021

  11. [19]

    Overlapping and robust edge-colored clustering in hypergraphs

    Alex Crane, Brian Lavallee, Blair D Sullivan, and Nate Veldt. Overlapping and robust edge-colored clustering in hypergraphs. In Proceedings of the 17th ACM International Conference on Web Search and Data Mining (WSDM) , pages 143–151, 2024

    2024

  12. [20]

    Edge-colored clustering in hypergraphs: Beyond minimizing unsatisfied edges

    Alex Crane, Thomas Stanley, Blair D Sullivan, and Nate Veldt. Edge-colored clustering in hypergraphs: Beyond minimizing unsatisfied edges. arXiv preprint arXiv:2502.13000 , 2025

    2025 arXiv

  13. [21]

    Cognitive relevance of the community structure of the human brain functional coactivation network

    Nicolas A Crossley, Andrea Mechelli, Petra E V´ ertes, Toby T Winton-Brown, Ameera X Patel, Cedric E Ginestet, Philip McGuire, and Edward T Bullmore. Cognitive relevance of the community structure of the human brain functional coactivation network. Proceedings of the National ...

    2013

  14. [22]

    Robust Correlation Clustering

    Devvrit, Ravishankar Krishnaswamy, and Nived Rajaraman. Robust Correlation Clustering. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (AP- PROX/RANDOM 2019), volume 145, pages 33:1–33:18, 2019

    2019

  15. [23]

    A new multilayered PCP and the hardness of hypergraph vertex cover

    Irit Dinur, Venkatesan Guruswami, Subhash Khot, and Oded Regev. A new multilayered PCP and the hardness of hypergraph vertex cover. SIAM Journal on Computing , 34(5):1129–1146, 2005

    2005

  16. [24]

    A density-based algorithm for discover- ing clusters in large spatial databases with noise

    Martin Ester, Hans-Peter Kriegel, J¨ org Sander, and Xiaowei Xu. A density-based algorithm for discover- ing clusters in large spatial databases with noise. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD) , page 226–231, 1996

    1996

  17. [25]

    A comprehensive survey of clustering algorithms: State-of-the-art machine learning applications, taxonomy, challenges, and future research prospects

    Absalom E Ezugwu, Abiodun M Ikotun, Olaide O Oyelade, Laith Abualigah, Jeffery O Agushaka, Christopher I Eke, and Andronicus A Akinyelu. A comprehensive survey of clustering algorithms: State-of-the-art machine learning applications, taxonomy, challenges, and future research p...

    2022

  18. [26]

    Lp-based pivoting algorithm for higher-order correlation clustering

    Takuro Fukunaga. Lp-based pivoting algorithm for higher-order correlation clustering. Journal of Combinatorial Optimization , 37:1312–1326, 2019

    2019

  19. [27]

    Approximation algorithms for partial covering problems

    Rajiv Gandhi, Samir Khuller, and Aravind Srinivasan. Approximation algorithms for partial covering problems. Journal of Algorithms , 53(1):55–84, 2004

    2004

  20. [28]

    Correlation clustering generalized

    David F Gleich, Nate Veldt, and Anthony Wirth. Correlation clustering generalized. In 29th Interna- tional Symposium on Algorithms and Computation (ISAAC) , 2018

    2018

  21. [29]

    A general approximation technique for constrained forest problems

    Michel X Goemans and David P Williamson. A general approximation technique for constrained forest problems. SIAM Journal on Computing , 24(2):296–317, 1995

    1995

  22. [30]

    Goemans and David P

    Michel X. Goemans and David P. Williamson. The primal-dual method for approximation algorithms and its application to network design problems. In Dorit S. Hochbaum, editor,Approximation Algorithms for NP-hard Problems . 1996

    1996

  23. [31]

    A primal-dual bicriteria distributed algorithm for capacitated vertex cover

    Fabrizio Grandoni, Jochen K¨ onemann, Alessandro Panconesi, and Mauro Sozio. A primal-dual bicriteria distributed algorithm for capacitated vertex cover. SIAM Journal on Computing , 38(3):825–840, 2008

    2008

  24. [32]

    Approximation algorithms for the capacitated correlation clustering problem with penalties

    Sai Ji, Gaidi Li, Dongmei Zhang, and Xianzhao Zhang. Approximation algorithms for the capacitated correlation clustering problem with penalties. Journal of Combinatorial Optimization , 45(1), January 2023

    2023

  25. [33]

    Walmart Recruiting: Trip Type Classifica- tion

    jprenci, Walmart Competition Admin, and Will Cukierski. Walmart Recruiting: Trip Type Classifica- tion. https://kaggle.com/competitions/walmart-recruiting-trip-type-classification , 2015

    2015

  26. [34]

    What’s Cooking? https://kaggle.com/competitions/whats-cooking, 2015

    Wendy Kan. What’s Cooking? https://kaggle.com/competitions/whats-cooking, 2015. Kaggle

    2015

  27. [35]

    Practical guide to cluster analysis in R: Unsupervised machine learning , vol- ume 1

    Alboukadel Kassambara. Practical guide to cluster analysis in R: Unsupervised machine learning , vol- ume 1. Sthda, 2017. 12

    2017

  28. [36]

    Higher-order correlation clus- tering for image segmentation

    Sungwoong Kim, Sebastian Nowozin, Pushmeet Kohli, and Chang Yoo. Higher-order correlation clus- tering for image segmentation. Advances in Neural Information Processing Systems (NIPS) , 24, 2011

    2011

  29. [37]

    A color-blind 3-approximation for chromatic correlation clustering and improved heuristics

    Nicolas Klodt, Lars Seifert, Arthur Zahn, Katrin Casel, Davis Issac, and Tobias Friedrich. A color-blind 3-approximation for chromatic correlation clustering and improved heuristics. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining (KDD) , ...

    2021

  30. [38]

    Recsys challenge 2019: Session-based hotel recommendations

    Peter Knees, Yashar Deldjoo, Farshad Bakhshandegan Moghaddam, Jens Adamczak, Gerard-Paul Leyson, and Philipp Monreal. Recsys challenge 2019: Session-based hotel recommendations. In Pro- ceedings of the 13th ACM Conference on Recommender Systems , pages 570–571, 2019

    2019

  31. [39]

    Motif clustering and overlapping clustering for social network analysis

    Pan Li, Hoang Dau, Gregory Puleo, and Olgica Milenkovic. Motif clustering and overlapping clustering for social network analysis. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM), pages 1–9. IEEE, 2017

    2017

  32. [40]

    Inhomogeneous hypergraph clustering with applications

    Pan Li and Olgica Milenkovic. Inhomogeneous hypergraph clustering with applications. Advances in neural information processing systems (NeurIPS) , 30, 2017

    2017

  33. [41]

    Mittelmann

    Hans D. Mittelmann. Latest benchmark results. In INFORMS Annual Conference, Phoenix, AZ, USA, 2018

    2018

  34. [42]

    Mittelmann

    Hans D. Mittelmann. Latest progress in optimization software. In INFORMS Annual Meeting, Phoenix, AZ, USA, 2023

    2023

  35. [43]

    Correlation clustering methodologies and their funda- mental results

    Divya Pandove, Shivani Goel, and Rinkle Rani. Correlation clustering methodologies and their funda- mental results. Expert Systems, 35(1):e12229, 2018

    2018

  36. [44]

    Complex network measures of brain connectivity: uses and interpre- tations

    Mikail Rubinov and Olaf Sporns. Complex network measures of brain connectivity: uses and interpre- tations. Neuroimage, 52(3):1059–1069, 2010

    2010

  37. [45]

    An overview of Microsoft Academic Service (MAS) and Applications

    Arnab Sinha, Zhihong Shen, Yang Song, Hao Ma, Darrin Eide, Bo-June Hsu, and Kuansan Wang. An overview of Microsoft Academic Service (MAS) and Applications. In Proceedings of the 24th Interna- tional Conference on World Wide Web (WWW) Companion , pages 243–246, 2015

    2015

  38. [46]

    Drug Abuse Warning Network (DA WN)

    Substance Abuse and Mental Health Services Administration. Drug Abuse Warning Network (DA WN). https://www.samhsa.gov/data/data-we-collect/dawn-drug-abuse-warning-network , 2011

    2011

  39. [47]

    Overlapping and Robust Edge-Colored Clustering in Hyper- graphs

    TheoryInPractice. Github repository for “Overlapping and Robust Edge-Colored Clustering in Hyper- graphs” (Crane et al. [19]). https://github.com/TheoryInPractice/overlapping-ecc, 2024

    2024

  40. [48]

    Optimal LP rounding and linear-time approximation algorithms for clustering edge-colored hypergraphs

    Nate Veldt. Optimal LP rounding and linear-time approximation algorithms for clustering edge-colored hypergraphs. In International Conference on Machine Learning (ICML) , pages 34924–34951. PMLR, 2023

    2023

  41. [49]

    A correlation clustering framework for community detection

    Nate Veldt, David F Gleich, and Anthony Wirth. A correlation clustering framework for community detection. In Proceedings of the 2018 World Wide Web Conference (WWW) , pages 439–448, 2018

    2018

  42. [50]

    A literature review on correlation clustering: cross-disciplinary taxonomy with bibliometric analysis

    Dewan F Wahid and Elkafi Hassini. A literature review on correlation clustering: cross-disciplinary taxonomy with bibliometric analysis. In Operations Research Forum, volume 3, page 47. Springer, 2022

    2022

  43. [51]

    Chromatic correlation clustering, revisited

    Qing Xiu, Kai Han, Jing Tang, Shuang Cui, and He Huang. Chromatic correlation clustering, revisited. Advances in Neural Information Processing Systems (NeurIPS) , 35:26147–26159, 2022

    2022

  44. [52]

    level” ℓe := P u∈e βe,u. Consider an iteration for node v ∈ V . By enumerating δ(v), we can compute, for every color c ∈ χ(δ(v)), the “slack

    Julian Yarkony, Alexander Ihler, and Charless C Fowlkes. Fast planar correlation clustering for image segmentation. In Computer Vision: 12th European Conference on Computer Vision (ECCV) , pages 568–581. Springer, 2012. 13 A Related work Angel et al. [8] initiated the study of...

    2012

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.