John Dickerson, Brian Brubach, Aravind Srinivasan, Leonidas Tsepenekas, Darshan Chakrabarti
We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. The repositories linked to it are listed below.
Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.
Metric clustering is fundamental in areas ranging from Combinatorial Optimization and Data Mining, to Machine Learning and Operations Research. However, in a variety of situations we may have additional requirements or knowledge, distinct from the underlying metric, regarding which pairs of points should be clustered together. To capture and analyze such scenarios, we introduce a novel family of stochastic pairwise constraints, which we incorporate into several essential clustering objectives (radius/median/means). Moreover, we demonstrate that these constraints can succinctly model an intriguing collection of applications, including among others Individual Fairness in clustering and Must-link constraints in semi-supervised learning. Our main result consists of a general framework that yields approximation algorithms with provable guarantees for important clustering objectives, while at the same time producing solutions that respect the stochastic pairwise constraints. Furthermore, for certain objectives we devise improved results in the case of Must-link constraints, which are also the best possible from a theoretical perspective. Finally, we present experimental evidence that validates the effectiveness of our algorithms. In a generic metric clustering problem, there is a set of points C, requiring service from a set of locations F , where both C and F are embedded in some metric space. The sets C, F do not need to be disjoint, and we may very well have C = F . The goal is then to choose a set of locations S ⊆ F , where S might have to satisfy additional problem-specific requirements and an assignment φ : C → S, such that a metric-related objective function over C is minimized. However, in a variety of situations there may be external and metric-independent constraints imposed on φ, regarding which pairs of points j, j ∈ C should be clustered together, i.e., constraints forcing a linkage φ(j) = φ(j ). In this work, we generalize this deterministic requirement, by introducing a novel family of stochastic pairwise constraints. Our input is augmented with multiple sets P q of pairs of points from C (P q ⊆ C 2 for each q), and values ψ q ∈ [0, 1]. Given these, we ask for a randomized solution, which ensures that in expectation at most ψ q |P q | pairs of P q are separated in the
The same record, over MCP at https://syntology.ai/mcp:
get_harvested_code_for_paper("2103.02013")
get_code_for_paper("2103.02013")
have("2103.02013")
The run record, dated, one paper per request, free:
curl https://syntology.ai/api/ran/2103.02013.json
A badge for a README (the split and the date, never a ratio):
[](https://syntology.ai/paper/2103.02013)
Connect an agent — have() is free.