Clustering without Over-Representation

1 INTRODUCTION

• The motivation includes preventing any advertiser from gaining a large market share within an auction cluster, as well as avoiding clusters dominated by one news source or viewpoint.The auction example cites for a theoretical justification; news and committee examples illustrate other settings for upper bounds on group representation.Source: §1 · p. 1
• The paper studies k-center clustering with a cap α on each color’s fraction in every cluster, targeting balance without requiring exact proportional representation.The authors choose k-center for its theoretical simplicity and its guarantee that every point is close to its cluster center.Source: §1 · p. 1
• For α = 1/2, the paper obtains a combinatorial approximation algorithm; for general α, it gives an LP-based algorithm with a bicriteria approximation guarantee and proves the problem NP-hard to approximate.Source: §1 · pp. 1–2
• On a number of real datasets, the authors evaluate their LP-based algorithm and report that its performance is even better than the theoretical guarantees.Source: §1 · p. 2
• Unlike prior fair k-center work requiring each cluster to match the population’s color distribution, this cap can admit non-trivial clusterings when exact proportionality does not.The paper distinguishes its objective from diversity constraints requiring a minimum number of colors.Source: §1 · p. 2

2 MODEL AND PRELIMINARIES

• A k-center instance has clients D, facilities F = D, a metric distance function, and a bound k; a solution opens at most k facilities and assigns each client to one.Its cost is the maximum distance from a client to its assigned facility.Source: §2 · p. 2
• The unconstrained k-center greedy algorithm repeatedly opens a center at the client farthest from the current centers, then assigns clients to their closest open center.The cited standard algorithm is a 2-approximation [17]; with added constraints, closest-center assignment may be infeasible.Source: §2 · p. 2
• In α-capped k-center, each color’s assigned clients at any facility may be no more than α times that facility’s total assigned clients.The model specifies a color for each point and uses Dc for the clients of color c.Source: §2 · p. 2

3 A GENERAL ALGORITHM

• The general algorithm rounds an LP relaxation to an integral solution, trading a constant-factor cost guarantee for additive fairness violation of at most 2 clients per color and facility.When 1/α is integral, the additive violation improves to 1.Source: §3 · p. 3, §3.2 · p. 3

3.1 An LP formulation

• The LP encodes assignments within distance λ, facility-opening and k limits, and each color’s representation cap; its relaxation also requires an open facility to serve at least ⌈1/α⌉ clients.The bicriteria polytope allows additive error Δ in the cap constraint.Source: §3.1 · p. 3

3.2 Outline

• Binary search finds the smallest λ′ with a nonempty P(λ′, α), then the algorithm constructs an integral solution in P(3λ′, α, 2).Theorem 3.1 bounds the resulting cost by 3λ*; for 1/α integral, the multiplicative cap bound is 2α.Source: §3.2 · p. 3

3.3 Finding facilities to open

• A maximal set of facilities separated by more than 2λ′ is opened, and fractional assignments are rerouted to these facilities, keeping reassigned client distances within 3λ′.Each facility outside the selected set maps to a selected facility within 2λ′.Source: §3.3 · pp. 3–4

3.4 Assigning clients to facilities

• An integral maximum flow assigns clients along supported fractional edges, preserving full client assignment while bounding the color cap’s additive violation by 2, or 1 when 1/α is integral.The proof compares fractional and integral color and total assignments; its bound is T′′ < αB′′ + 2, tightened to αB′′ + 1 in the integral-reciprocal case.Source: §3.4 · p. 4

4 AN ALGORITHM FOR α = 1/2

• For α = 1/2, the constraint means no color occurs more than half the times in a cluster; caplets are pairs or triples of distinct colors.A caplet decomposition partitions a connected graph into edge caplets and at most one triangle caplet.Source: §4 · p. 4

4.1 Algorithm

• The algorithm enumerates candidate λ*, builds a threshold graph, decomposes its components into caplets, then clusters the caplets with the greedy k-center algorithm.The threshold graph connects nearby points of different colors.Source: §4.1 · pp. 4–5, §4 · p. 4
• 12λ* cost: Algorithm 3 returns a valid (1/2)-capped k-clustering, so no color is an absolute majority in any cluster.The proof bounds the cost using a caplet-decomposition diameter of at most 10λ*.Source: §4.1 · p. 5

4.2 Analysis

• Within each optimal facility’s assigned points, different-color pairs and, when needed, a three-color triangle form caplets of diameter at most 2λ*.This construction yields at most one triangle caplet per facility.Source: §4.2 · p. 5
• A rooted-tree procedure forms disjoint paths between triangle caplets, with edge caplets internally and consecutive caplets at distance at most 6λ*.The procedure continues until at most one triangle caplet remains outside the paths.Source: §4.2 · pp. 5–6
• Shifting points along each triangle-ended path creates edge caplets whose diameters are at most 10λ*, yielding a valid decomposition for the component.The shift is possible because each caplet contains points of different colors.Source: §4.2 · pp. 5–6

5.1 Datasets

• The datasets span 8–20 dimensions and 4 to over 12,000 colors, with color distributions from balanced to more than 40% of points in one color.They include text, co-authorship graph embeddings, and online-auction data, all represented in Euclidean spaces.Source: §5.1 · p. 6

5.2.1 Baselines.

• Greedy k-center, post-processed with Lloyd iterations, serves as a gold-standard baseline; random centers are also tested across ten runs and averaged.Source: §5.2.1 · p. 7

5.2.2 Measures of quality.

• Quality is measured by maximum distance to a center and maximum additive cap violation; the algorithm’s violation is provably at most 2, or 1 when 1/α is integer.Source: §5.2.2 · p. 7

5.2.3 Implementation details and parameters of the algorithm.

• The implementation searches increasing λ values from a greedy lower bound toward a distance-based upper bound, and restricts LP variables to a greedy m × k core-set; m ≥ 1 retains a constant-factor approximation.Source: §5.2.3 · p. 7

5.3 Experimental results

• 10–50% above the unconstrained solution in some cases; across datasets, cost is usually +10% worse to 2x worse than Greedy, and observed Δ is always 1.The comparison uses k = 25, ϵ = 0.1, and m = 2.Source: §5.3 · pp. 7–8, Table 2 · p. 8
• ⪅2 for ϵ = 0.1 and ⪅3 for ϵ = 0.5; higher α is associated with lower cost ratios, while larger k generally has higher ratios.Source: Figure 3 · p. 8, §5.3 · p. 8
• Larger k increases running time, while larger α mostly reduces it because fewer λ values need evaluation to find a non-empty P(λ,α).Source: Figure 4 · p. 8, §5.3 · p. 8
• Larger m is generally associated with lower cost ratios, but good results with m = 2 allow small LP instances.Figure 4(a) studies m’s effect through the core-set, which reduces the number of y_i variables to m × k.Source: §5.3 · p. 8

6 HARDNESS

• The graph construction first handles α = 1/2, then extends to α = 1/(2+t) for integer t > 0; it assumes the derived t_r and t_b are non-negative integers.Otherwise, it constructs a trivial instance with no fair coverage.Source: §6 · p. 9
• For α ∈ (0, 0.5], α-capped k-center clustering is NP-hard to approximate within a factor better than 2.The hardness holds for minimizing cost even with an arbitrary number of clusters.Source: §6 · pp. 8–9
• The reduction maps a t-Star-Decomposition instance to a colored graph metric; a t-star decomposition yields capped clustering cost 1, while cost at most 2 implies such a decomposition.Source: §6 · pp. 8–9

• The algorithms have provable guarantees, and experiments show they are effective on different real-world datasets.Source: §7 · p. 9
• The general algorithm solves a linear program, which can be challenging when the number of points is large.Source: §7 · p. 9
• Future work includes a scalable combinatorial algorithm for the general case, tighter guarantees, and extensions to k-means and k-median.Source: §7 · p. 9