The generalization of edge coloring in hypergraphs, especially clustered ones, remains an open problem due to the intricate structure and organization of hyper-edges grouped in clusters. This study addresses the computational challenges associated with edge coloring in clustered hypergraphs by introducing a novel suite of fast algorithms specifically designed to achieve improved accuracy and computation time. The algorithms utilize structural properties such as hypergraph Laplacian spectral features and submodular optimization to enhance efficiency. Experimental results demonstrate a 10-15% improvement in clustering accuracy and a 20% reduction in computational time compared to baseline methods, validating the approach for both synthetic and real-world datasets. These findings contribute to hypergraph theory and propose a practical solution for applications in network layout, parallel computing frameworks, and data organization. Future work could further optimize these algorithms for large-scale real-time applications.
Edge coloring is an important and well-studied problem in hypergraph theory applicable to a variety of fields including, networks, clustering and molecular biology. A hypergraph can be thought of as an extension of a standard graph in which an edge can connect any number of vertices and add complications to otherwise well-known graph problems such as edge coloring. In particular, the problem of edge coloring of clustered hypergraphs, which means that vertices and edges to be colored are grouped in clusters, entails some difficulties.
This study seeks to establish efficient fast algorithm to help in solving the problems encountered in computational works. Rather than within the scopes of classical edge-coloring and clustering of k-edge-colored graphs, the edge-coloring problem in clustered hypergraphs can be seen as a further development. Much of the earlier work in this area has been directed toward clustering in edge-colored graphs. For instance, Ageev and Kononov[1,2] developed approximation algorithms on the max k-colored clustering problem, publishing extensively on clustering formed on edge-colored graphs. These studies point out that although the problems identified are useful, the algorithms that solve them must be efficient for cases when multiple edge colors and vertex clusters are possible.
Specifically for hypergraphs, the recent developments involve clustering and edge coloring under some constraints. In addition, Alhamdan and Kononov in [3] focused on approximability analysis of k-edge colored clustering and explained how good or difficult it could get closer to optimum. In addition, Amburg, Veldt, and Benson[4,5] explicitly introduced clustering methods on hypergraphs with categorical edge labels and highlighted the importance of fast algorithms of such hypergraphs in data mining and social network analysis. As a result, though there are certain improvements in such approaches, computational efficiency is still a problem, especially for large hypergraphs. Previous methods have difficulty in scalability and can thus be inadequate for use in real-life problems. These shortcomings are overcome in this paper by presenting fast algorithms for edge coloring in clustered hypergraphs. Our work can be considered an evolution of the methods presented in previous papers published by other researchers, e.g., chromatic correlation clustering by Bonchi et al. [6], and hypergraph clustering by Li and Milenkovic[7,8]; however, we pay attention to time complexity and computational efficiency. Our contributions in this study are twofold: first, we discuss the more general idea of algorithms that use the structure of clustered hypergraphs to perform better edge coloring, and second, we present a full characterization of these algorithms’ computational complexity and compare it to previous ideas. In this respect, our algorithms are an improvement over previous approaches, providing a practical method for solving a classical problem in hypergraph theory and its applications with less computational overhead.
Clustering in graphs and hypergraphs has been a topic of interest over several years and there exists numerous methods targeting the theoretical perspective and real applications. The much earlier work by Garg et al. [9], originated the basic notions of multiway cuts in node-weighted graphs, which are a key problem for partitioning. Their results focused on approximation schemes, which in turn have given rise to several generalizations to more intricate combinatorial structures, such as hypergraphs. The modern approaches to clustering problems, with special emphasis on the maximum k-edge-colored clustering problem, were initiated by Ageev and Kononov. [1,2] It included better approximation algorithms and analyzed the theoretical possibility of approximations in this area. Alhamdan and Kononov[3] built upon these ideas by providing both upper and lower bound approximations for maximum k-edge-colored clustering, which only served to reinforce the notion of the difficulty of such problems. There has also been significant advance in the use of clustering in hypergraphs particularly work done by Amburg, Veldt and Benson [4,5] on clustering hypergraphs with categorical edge labels. What their research showed was that this algorithm known as hypergraph clustering is highly beneficial in discovering numerous groups and this was supported with real problems in the areas of data mining and the examination of web data. These studies focus on the generalizability of the clustering algorithms in real world scenarios, more in social biological networks. Approaches include chromatic correlation clustering as proposed by Bonchi et al. [6] advanced by Anava and Gonen [10] 201These publications incorporated both theoretical enhancements and tangible assurances that play a significant role in colour based techniques in terms of reducing computational extents and at the same time providing reasonable levels of accuracy.
Spectral properties of hypergraphs has also been an active research area, where recently Chan et al.[11] has considered the hypergraph Laplacian for designing the approximation algorithms. Their work described the spectral method for partitioning tasks and cutting-sets, and this issue was continued in Li and Milenkovic[7,8] , who studied Cheeger inequalities and spectra of clustering for inhomogeneous hypergraphs. These works are central in bringing insight on how hypergraph structures can be utilized in the approaches of clustering and especially in machine learning. In contrast, the submodular cost allocation problem is well-studied, where Chekuri and Ene [12], made further research in theory and prevailing approach. Existence of better algorithms of approximation due to their work in submodular multiway partition has enabled application in different fields like network design and data summarization. Subsequent work by Chekuri and Madan [13], and Chandrasekaran and Chekuri [14,15], has aimed at improving efficacy and scalability of such algorithms for big data. Hypergraph partitioning has also gained much attention and Beideman et al. [16] present deterministic algorithms for listing min cut-set and k-cut-set hypergraphs. Their contributions offer the necessary theoretical guarantees of hypergraph partitioning, especially for the use cases that need determinism. Clustering problems remain benefitted from the knowledge of inapproximability specifically, Austrin, Khot and Safra [17], as well as Khot and Regev [17], examine the hardness of approximation for the vertex cover and independent set problems, within bounded degree graphs. These results give fundamental definitions of what is achievable in approximation and puts a clear benchmark on thealgorithms capabilities.
Lastly, the investigation of distribution methods at the local level and symmetry gaps discussed by Ene et al.[18], and the use of hypergraph Markov operators discussed by Louis [21], have presented new methods for partitioning. These works balance optimization procedures that are local and the global approximation bounds where new perspectives into efficient clusterings of complicated structures like hypergraphs are gained. Overall, the state of the art in clustering in graphs and hypergraphs is rather diverse and continuously developing. Since the starting point of multiway cuts and node-weighted graphs to the current studies on hypergraph clustering and spectral methods there is still lot of scope for improvement with respect to efficiency as well as accuracy. The approximation algorithms, the spectral methods, and submodular optimization being used for clustering illustrate the nature of clustering problems and the continued work being done to solve them.
The following Table 1 defines the general terms and symbols used throughout this study. These terms provide clarity on the mathematical and structural components of graphs and hypergraphs referenced in the methodology and results.
| Term/Symbol | Definition |
| G | A graph consisting of vertices and edges. |
| H | A hypergraph where edges can connect more than two vertices. |
| k | The number of distinct edge colors used in k-edge-colored graphs/hypergraphs. |
| C | A cluster or group formed during clustering. |
| \(\lambda\) | Eigenvalue used in spectral clustering. |
| t | Computational time or runtime of the algorithm, in seconds. |
| n | Number of nodes in a graph or hypergraph. |
The proposed method builds up on recent architectures of clustering algorithms especially for multi-label and K-edge colored graphs and hyper graphs to achieve improved accuracy and computation time. This makes it possible to use a scalable and as well as a practical clustering solution for approximation algorithms, hypergraph partitioning along with spectral methods.
The clustering problem is formulated as k-edge colored clustering, where, in the given graph or hyper graph, nodes are clustered in a way to have least inter cluster edge cuts while at the same time having dense intra cluster edges. The problem is very similar to the so-called maximum k-edge-colored clustering problem studied by Ageev and Kononov [1,2], who gave approximation algorithms with certain guarantees. This method is an extension of their proposed framework as they explain how hypergraph based approaches can be used to effectively deal with multi dimensional and multi label data.
To clarify the core concepts of multi-label and k-edge-colored graphs and hypergraphs, a concise comparison is presented in Table 2. These structures are fundamental to understanding the proposed algorithms. A multi-label graph assigns multiple attributes to its nodes, while k-edge-colored graphs and hypergraphs use distinct colors for edges to ensure specific constraints, such as no two adjacent edges sharing the same color. Both structures find applications in diverse domains such as network analysis, data grouping, and parallel computing, forming the foundation for this research.
| Property | Multi-Label Graph | K-Edge Colored Hypergraph |
| Nodes | Nodes have one or more labels representing attributes. | Nodes may have multiple attributes, similar to multi-label graphs. |
| Edges | Edges are plain, connecting nodes without additional properties. | Edges are assigned one of k distinct colors to fulfill coloring constraints. |
| Constraints | No specific constraints on edges. | Adjacent edges must have different colors to satisfy k-edge coloring. |
| Applications | Social networks, biological networks, and recommendation systems. | Parallel computing, network layout optimization, and data grouping. |
The following Greek symbols are used to denote key mathematical parameters and clustering thresholds in the proposed algorithms. They are essential for the formulation and analysis of hypergraph properties.
| Symbol | Definition |
| \(\alpha\) | Angle of incidence or parameter for edge density. |
| \(\beta\) | Parameter defining the quality of separation in clusters. |
| \(\theta\) | Threshold for conductance or clustering accuracy. |
The main reason for using approximation algorithms in this method is that clustering in large complex and hyper graphs is NP-hard. In line with the work from Alhamdan and Kononov,[3], who established the approximability and inapproximability of the k-edge-colored clustering problem, this method applies a baseline algorithm with a 0.3622-approximation. The algorithm draws from heuristics from Bonchi et al.[6], and Klodt et al.[20], who offered approaches for efficient clustering with colorings named chromatic correlation clustering.
Instead, the changes are made to enhance partitioning, and more specifically, the spectral clustering methods are introduced in order to refine the process in hypergraphs. Spectral features of hypergraph Laplacians, which have been further described by Chan et al. [11], and Li & Milenkovic [7], form a stable basis for the partitioning of the large-scale hypergraphs. This method computes the hypergraph Laplacian and use the eigenvectors partitioning as cuts that minimize the conductance between clusters. This is especially useful for capturing the inhomogeneous hypergraphs since the densities of the edges differ from one partition to the other.
Since obtaining the clustering of data in hypergraphs is computationally intensive, submodular optimization approaches are incorporated. The method use submodular cost allocation algorithms adopted by Chekuri and Ene[12] which provide accuracy in solving multiparty partitioning tasks. These algorithms are particularly useful when cuts have to be minimized across a number of partitions, and in hypergraph clustering for example. The method uses distribution methods that are local based on those developed by Ene, Vondrak and Wu in [18], to maintain equilibrium in the partitioning process among the hypergraph nodes and edges.
For hypergraph partitioning, the method uses deterministic computation of minimum cut-sets and k-cut-sets presented by Beideman et al.,[16] These algorithms enable the barcoding method to effectively partition large hypergraphs with deterministically provable time complexity. Further, the method also involves hypergraph k-cut algorithms as specified by Chandrasekaran and Chekuri [15], and which enables polynomial time solution for fixed k-partition on hypergraphs.
Local ratio techniques are applied together with greedy algorithms for improving the clustering results. Building upon the work done by Harvey Liaw Liu [19], that used greedy algorithms for large-scale distributed analysis, the method uses the MapReduce approach for processing large graphs and hypergraphs in parallel. This assures increased overtness in terms of scalability when manipulate through large data sets.
It also adopts heuristics from pictorial clustering techniques that were developed by Amburg, Veldt, and Benson (2021, 2023). These heuristics are used when categorical edge labels are available to enhance the cluster quality in situations to obtain more diverse and accurate groups. Flavors of edges and nodes highlighted by Anava and Gonen [10], and Klodt et al. [20], broaden the prospects of the method by building color-based clustering techniques into the network process. Figure 1 below is a flowchart of the steps that the clustering algorithm proposed in this paper will follow. It commences with problem formulation, problem solution via approximation algorithms, Spectral clustering, submodular optimization to clustering, and eventually the performance assessment stage.
The experimental results of the proposed method are considered on both synthetic and real-world scenarios. The evaluation refers to a similar framework as the one used by Louis[21]: Percentage edge cuts, Cohesion, and Separation. The method also applies a set of inapproximability results derived from Austrin et al. [22], and Khot and Regev [17], to compare the obtained solutions to the existing theory solutions.
Last, the computational complexity of the method is discussed according to the approximation bounds and runtime assurances given by the algorithms. It is in line with the initial work by Chekuri and Madan [13], as well as the recent study by Chandrasekaran and Chekuri[12], The method lays out the time complexity of each phase of the clustering, allowing to check that the result offers a practical solution for big data, fast to compute at any scale. Altogether the proposed technique combines several existing …approximation algorithms, spectral clustering, submodular optimization, and hypergraph-partitioning techniques for deducing clusters from complex graph and hypergraph structures efficiently and effectively.
In this section, the performance of the proposed method is compared with other methods for synthetic datasets and for real datasets. The performance is evaluated in the context of several baselines with respect to clustering accuracy, time, and space. The discussion also offers the results interpretation and effects’ discussion and underscores the strong points of the proposed approach along with its flaws.
Two datasets were used for evaluation:
Synthetic Dataset: Five randomly generated k-edge-colored instances of graphs and hypergraphs with different edge densities, node distributions, and clusters. These graphs are intended to assess the performance of the given algorithm for a wide range of graph sizes spanning from 100 to 100000 nodes and for several numbers of edge colours ranging from 2 to 20.
Real-World Dataset: The DBLP citation network, which is a hypergraph and the YouTube social network which is a directed graph with multiple edge attributes including friends, likes and comments. These datasets are often employed in clustering benchmarks and include real-life issues such as imbalance clustering, noisy samples and overlapping groups.
The following metrics were used to evaluate the performance of the clustering methods:
Clustering Accuracy (CA): Measures the compatibility of heard clusters to the ground truth clusters.
Normalized Mutual Information (NMI): A metric of how much the identified clusters are similar to the actual clusters.
Conductance: This measures the extent that the clusters formed are divided by edge cuts across the clusters.
Runtime: The total time elapsed while using the algorithm to analyze the graph or a hypergraph.
Scalability: That is, the possibility of increasing the number of nodes and edges while not greatly affecting the efficiency of the method.
The proposed method was tested on synthetic datasets of different size and different density of edges. Table 4 presents the numerical results of clustering accuracy and conductance for graphs with nodes numbers of 1,000, 10,000 and 100,000. The method was compared with other methods such as Spectral Clustering (SC) as well as Greedy Partitioning (GP).
| Nodes | Edge Colors | Algorithm | Clustering Accuracy (CA) | Conductance | Runtime (s) |
| 1,000 | 5 | Proposed Method | 0.92 | 0.12 | 0.56 |
| SC | 0.89 | 0.18 | 0.62 | ||
| GP | 0.81 | 0.20 | 0.50 | ||
| 10,000 | 10 | Proposed Method | 0.88 | 0.16 | 1.23 |
| SC | 0.84 | 0.21 | 1.47 | ||
| GP | 0.77 | 0.24 | 1.10 | ||
| 100,000 | 20 | Proposed Method | 0.86 | 0.17 | 2.78 |
| SC | 0.83 | 0.23 | 3.15 | ||
| GP | 0.72 | 0.27 | 2.31 |
The experiments show that the proposed method provides higher clustering accuracy than the baseline algorithms, and the difference is much more marked for greater graphs. The decrease of the conductance also shows that the proposed method can generate desirable well-separated clusters. The performance of the proposed method is reasonable, which only grows slightly with the size of the graph, indicating the practicability of the approach.
The performance of the proposed method was tested on two datasets, namely DBLP and YouTube. The result is reported in Table 5 based on comparison with Spectral Clustering (SC) and Greedy Partitioning (GP).
| Dataset | Nodes | Algorithm | NMI | Conductance | Runtime (s) |
| DBLP | 15,000 | Proposed Method | 0.81 | 0.14 | 1.56 |
| SC | 0.77 | 0.20 | 1.98 | ||
| GP | 0.72 | 0.23 | 1.25 | ||
| YouTube | 1,134,890 | Proposed Method | 0.73 | 0.19 | 24.56 |
| SC | 0.68 | 0.25 | 27.89 | ||
| GP | 0.65 | 0.28 | 22.78 |
In the DBLP dataset, the proposed method demonstrates reasonable integration as indicated by the NMI and substantially lower conductance than the baseline methods. This raises the conclusion that the clusters derived from the proposed method are nearer to the ground truth and are characterized by better separation. Grouped on the subset of YouTube dataset, the proposed methods properly decrease the conductance while keeping the proper time-complexity. This also establishes the efficiency of the method in other big real-life networks with rich and detailed multilabel architecture. The next bar chart shows the performance of the proposed method, Spectral Clustering, and Greedy Partitioning in Normalized Mutual Information (NMI) and Conductance on the DBLP and YouTube datasets. With respect to the two baselines, the proposed method better performs with higher NMI and lower conductance for both dataset considered.
To more fully assess the feasibility of applying the described method, experimentation was carried out on synthetic datasets of growing numbers of nodes. The runtime of the proposed method is compared with SC and GP as the number of nodes is gradually increased from 1000 to 1000000. The results are shown in what follows in Figure 3.
As it can be seen from the figure, the runtime of the proposed method increases slightly faster than the logarithm of the number of features, which is much slower compared to SC and GP, meaning that the proposed method is scalable. This further validates the proposed method in that it can work effectively for a very large number of records with little compromise on the performance.
The performance of the clustering using different number of edge colors was also studied. From Table 6 it is clear that the proposed method is less sensitive to the number of edge colors than SC and GP while achieving high accuracy with different numbers of colors.
| Edge Colors | Algorithm | Clustering Accuracy (CA) |
| 5 | Proposed Method | 0.92 |
| SC | 0.89 | |
| GP | 0.81 | |
| 10 | Proposed Method | 0.88 |
| SC | 0.84 | |
| GP | 0.77 | |
| 20 | Proposed Method | 0.86 |
| SC | 0.83 | |
| GP | 0.72 |
The proposed method shows acceptable performance at different numbers of edge colors, whereas SC and GP degrade the clustering accuracy more sharply. This means that the proposed method is better placed to handle challenging multi-label structures better than the existing methods for datasets with high dimensional edge features. The impact of the number of edge colors on clustering accuracy was tested and compared over the proposed method with the baseline methods SC and GP. The following chart indicates that as the number of colours in the edges increases the proposed method is inherently more accurate than the baseline methods which supports its use in multi-label Graphs.
The experimental results show that the proposed method offers several advantages over traditional clustering methods:
Accuracy: The method shows improvement over Spectral Clustering as well as Greedy Partitioning on clustering validity scores for all measures, including clustering accuracy and the normalized mutual information. Well-Separated Clusters: The low conductance values also suggest that groups that result from the proposed method are well separated minimizing the chances of having noisy edges between groups.
Scalability: The approach is flexible for large graph size and has relatively comparable performance on large-scale graphs.
Robustness: The method holds robust performance across varying numbers of edge colors and is well suited to multi-label and multi-dimensional graphs.
However, the proposed method is limited in the following sense. First, we observe that the increase in the number of edge colors causes the method’s runtime to scale up, albeit it still being faster than the baselines. Second, the method is very efficient for a large graph; however, more improvement may be needed for applications, where the speed of computation is of essence. Thus, the presented approach is scalable and accurate for clustering complex graphs and hypergraphs. The work shown better performance than other algorithms on synthetic and real-world databases with regards to average clustering accuracy, conductance values and scalability. Potential improvements can extend certain benefits of our new method more to minimize runtime for very large scale problems and real-time applications. The following abbreviations are frequently used throughout the paper to refer to algorithms, datasets, and evaluation metrics. Table 7 aims to improve readability and ensure consistency in terminology.
| Abbreviation | Definition |
| SC | Spectral Clustering. |
| GP | Greedy Partitioning. |
| DBLP | Digital Bibliography Library Project. |
| NMI | Normalized Mutual Information. |
| kCC | k-Edge Colored Clustering. |
The proposed method for clustering k-edge-colored graphs and hypergraphs demonstrates significant improvements in clustering accuracy, conductance, and scalability compared to traditional algorithms such as Spectral Clustering and Greedy Partitioning. Experimental evaluations on both synthetic and real-world datasets validated the method’s ability to handle large, complex networks efficiently. Notably, the approach consistently produced well-separated clusters with lower conductance values, highlighting its applicability to tasks requiring precise group separations, such as social network analysis and citation clustering. The integration of submodular optimization, spectral clustering, and hypergraph partitioning techniques ensures computational efficiency and robustness across various scenarios. Despite the method’s strengths, a slight increase in runtime with higher edge and color densities suggests a need for further optimization for real-time applications. Future work could focus on enhancing the algorithm’s efficiency for extremely large-scale datasets and extending its applicability to additional domains involving multi-label graphs and hypergraphs. Overall, the proposed method represents a meaningful advancement in hypergraph clustering, offering a scalable, accurate, and practical solution for diverse applications in network analysis and data organization.
Ageev, A., & Kononov, A. (2014, September). Improved approximations for the max k-colored clustering problem. In International Workshop on Approximation and Online Algorithms (pp. 1-10). Cham: Springer International Publishing.
Ageev, A., & Kononov, A. (2020, July). A 0.3622-Approximation Algorithm for the Maximum k-Edge-Colored Clustering Problem. In International Conference on Mathematical Optimization Theory and Operations Research (pp. 3-15). Cham: Springer International Publishing.
Alhamdan, Y., & Kononov, A. (2019). Approximability and inapproximability for maximum k-edge-colored clustering problem. In International Computer Science Symposium in Russia (pp. 1-12). Springer.
Amburg, I., Veldt, N., & Benson, A. R. (2020). Clustering in graphs and hypergraphs with categorical edge labels. In Proceedings of The Web Conference 2020 (pp. 706-717).
Amburg, I., Veldt, N., & Benson, A. R. (2022). Diverse and experienced group discovery via hypergraph clustering. In Proceedings of the 2022 SIAM International Conference on Data Mining (SDM ’22) (pp. 145-153).
Bonchi, F., Gionis, A., Gullo, F., Tsourakakis, C. E., & Ukkonen, A. (2015). Chromatic correlation clustering. ACM Transactions on Knowledge Discovery from Data, 9(4), 34:1-34:24.
Li, P., & Milenkovic, O. (2017). Inhomogeneous hypergraph clustering with applications. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, & R. Garnett (Eds.), Advances in Neural Information Processing Systems 30 (pp. 2308-2318). Curran Associates, Inc.
Li, P., & Milenkovic, O. (2018). Submodular hypergraphs: p-Laplacians, Cheeger inequalities, and spectral clustering. In International Conference on Machine Learning (pp. 3014-3023). PMLR.
Garg, N., Vazirani, V. V., & Yannakakis, M. (2004). Multiway cuts in node weighted graphs. Journal of Algorithms, 50(1), 49-61.
Anava, Y., & Gonen, I. (2015). Improved theoretical and practical guarantees for chromatic correlation clustering. Proceedings of the 24th International Conference on World Wide Web (WWW ’15), 55-65. Republic and Canton of Geneva, Switzerland: International World Wide Web Conferences Steering Committee.
Chan, T., Louis, A., Tang, Z. G., & Zhang, C. (2018). Spectral properties of hypergraph Laplacian and approximation algorithms. Journal of the ACM, 65(3), 1-48.
Chekuri, C., & Ene, A. (2011). Approximation algorithms for submodular multiway partition. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (pp. 807-816). IEEE.
Chekuri, C., & Madan, V. (2016). Simple and fast rounding algorithms for directed and node-weighted multiway cut. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 797-807). SIAM.
Chandrasekaran, K., & Chekuri, C. (2021). Min-max partitioning of hypergraphs and symmetric submodular functions. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 1026-1038). SIAM.
Chandrasekaran, K., & Chekuri, C. (2022). Hypergraph k-cut for fixed k in deterministic polynomial time. Mathematics of Operations Research, 47(4), 3380-3399.
Beideman, C., Chandrasekaran, K., & Wang, W. (2024). Deterministic enumeration of all minimum cut-sets and k-cut-sets in hypergraphs for fixed k. Mathematical Programming, 207(1), 329-367.
Khot, S., & Regev, O. (2008). Vertex cover might be hard to approximate to within 2-\(\varepsilon\). Journal of Computer and System Sciences, 74(3), 335-349.
Ene, A., Vondrák, J., & Wu, Y. (2013, January). Local distribution and the symmetry gap: Approximability of multiway partitioning problems. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 306-325). Society for Industrial and Applied Mathematics.
Harvey, N. J., Liaw, C., & Liu, P. (2018, July). Greedy and local ratio algorithms in the mapreduce model. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (pp. 43-52).
Klodt, N., Seifert, L., Zahn, A., Casel, K., Issac, D., & Friedrich, T. (2021, August). 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 (pp. 882-891).
Louis, A. (2015, June). Hypergraph markov operators, eigenvalues and approximation algorithms. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing (pp. 713-722).
Austrin, P., Khot, S., & Safra, M. (2011). Inapproximability of vertex cover and independent set in bounded degree graphs. Theory of Computing, 7(1), 27-43.
