Partial Optimality in Cubic Correlation Clustering
Authors: David Stein, Silvia Di Gregorio, Bjoern Andres
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Here, we focus on establishing partial optimality conditions for the special case of complete graphs and cubic objective functions. In addition, we define and implement algorithms for testing these conditions and examine their effect numerically, on two datasets. Next, we examine the effectiveness of the algorithms empirically, on two datasets. For both, we report the percentage of fixed variables and triples, as well as the runtime. |
| Researcher Affiliation | Academia | David Stein 1 Silvia Di Gregorio 1 Bjoern Andres 1 1Faculty of Computer Science, TU Dresden, Germany. |
| Pseudocode | Yes | Algorithm 1 Region Growing 1: Input: S = , c : IS R 2: Initialize: R = {}, queue Q = S 3: repeat |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | The paper describes the generation of two datasets ("Partition Dataset", "Geometric Dataset") but does not provide concrete access information (link, DOI, formal citation with authors/year) for public availability. |
| Dataset Splits | No | The paper describes how its datasets are defined and generated, but it does not specify any training, validation, or test dataset splits. |
| Hardware Specification | Yes | All algorithms are implemented in C++ and run on one core of an Intel Core i5-6600 equipped with 16 GB of RAM. |
| Software Dependencies | Yes | we solve the dual max st-flow problems by the implementation in the C++ library Boost (2022) of the push-relabel algorithm of Goldberg & Tarjan (1988). |
| Experiment Setup | Yes | With respect to a parameter α [0, 1], we draw the costs of pairs and triplets from two Gaussian distributions with means 1 + α and 1 α, depending on whether their elements belong to the same set or distinct sets in the partition R, and with standard deviation σ = σ0 + α(σ1 σ0), with σ0 = 0.1 and σ1 = 0.4. With respect to a parameter β [0, 1], we multiply the costs of pairs by 1 β, and the costs of triples by β. Here, the hardness of the instances is embodied by σ. |