More Like this

1. On Approximability of 𝓁₂² Min-Sum Clustering

   https://doi.org/10.4230/lipics.socg.2025.62  

   S, Karthik C; Lee, Euiwoong; Rabani, Yuval; Schwiegelshohn, Chris; Zhou, Samson (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Aichholzer, Oswin; Wang, Haitao (Ed.)

   The 𝓁₂² min-sum k-clustering problem is to partition an input set into clusters C_1,…,C_k to minimize ∑_{i=1}^k ∑_{p,q ∈ C_i} ‖p-q‖₂². Although 𝓁₂² min-sum k-clustering is NP-hard, it is not known whether it is NP-hard to approximate 𝓁₂² min-sum k-clustering beyond a certain factor. In this paper, we give the first hardness-of-approximation result for the 𝓁₂² min-sum k-clustering problem. We show that it is NP-hard to approximate the objective to a factor better than 1.056 and moreover, assuming a balanced variant of the Johnson Coverage Hypothesis, it is NP-hard to approximate the objective to a factor better than 1.327. We then complement our hardness result by giving a fast PTAS for 𝓁₂² min-sum k-clustering. Specifically, our algorithm runs in time O(n^{1+o(1)}d⋅ 2^{(k/ε)^O(1)}), which is the first nearly linear time algorithm for this problem. We also consider a learning-augmented setting, where the algorithm has access to an oracle that outputs a label i ∈ [k] for input point, thereby implicitly partitioning the input dataset into k clusters that induce an approximately optimal solution, up to some amount of adversarial error α ∈ [0,1/2). We give a polynomial-time algorithm that outputs a (1+γα)/(1-α)²-approximation to 𝓁₂² min-sum k-clustering, for a fixed constant γ > 0. 

   more » « less
2. Efficient Computation of a Semi-Algebraic Basis of the First Homology Group of a Semi-Algebraic Set

   https://doi.org/10.1007/s00454-024-00626-0  

   Basu, Saugata; Percival, Sarah (September 2024, Discrete & Computational Geometry)

   Let $$\R$$ be a real closed field and $$\C$$ the algebraic closure of $$\R$$. We give an algorithm for computing a semi-algebraic basis for the first homology group, $$\HH_1(S,\mathbb{F})$$, with coefficients in a field $$\FF$$, of any given semi-algebraic set $$S \subset \R^k$$ defined by a closed formula. The complexity of the algorithm is bounded singly exponentially. More precisely, if the given quantifier-free formula involves $$s$$ polynomials whose degrees are bounded by $$d$$, the complexity of the algorithm is bounded by $$(s d)^{k^{O(1)}}$$. This algorithm generalizes well known algorithms having singly exponential complexity for computing a semi-algebraic basis of the zero-th homology group of semi-algebraic sets, which is equivalent to the problem of computing a set of points meeting every semi-algebraically connected component of the given semi-algebraic set at a unique point. It is not known how to compute such a basis for the higher homology groups with singly exponential complexity. As an intermediate step in our algorithm we construct a semi-algebraic subset $$\Gamma$$ of the given semi-algebraic set $$S$$, such that $$\HH_q(S,\Gamma) = 0$$ for $q=0,1$. We relate this construction to a basic theorem in complex algebraic geometry stating that for any affine variety $$X$$ of dimension $$n$$, there exists Zariski closed subsets \[ Z^{(n-1)} \supset \cdots \supset Z^{(1)} \supset Z^{(0)} \] with $$\dim_\C Z^{(i)} \leq i$, and $$\HH_q(X,Z^{(i)}) = 0$$ for $$0 \leq q \leq i$$. We conjecture a quantitative version of this result in the semi-algebraic category, with $$X$$ and $$Z^{(i)}$$ replaced by closed semi-algebraic sets. We make initial progress on this conjecture by proving the existence of $$Z^{(0)}$$ and $$Z^{(1)}$$ with complexity bounded singly exponentially (previously, such an algorithm was known only for constructing $$Z^{(0)}$$). 

   more » « less
3. Algorithms for covering multiple submodular constraints and applications

   https://doi.org/10.1007/s10878-022-00874-x  

   Chekuri, Chandra; Inamdar, Tanmay; Quanrud, Kent; Varadarajan, Kasturi; Zhang, Zhao (June 2022, Journal of Combinatorial Optimization)

   Abstract We consider the problem of covering multiple submodular constraints. Given a finite ground setN, a weight function$$w: N \rightarrow \mathbb {R}_+$$ $w:N\to R_{+}$,rmonotone submodular functions$$f_1,f_2,\ldots ,f_r$$ $f_1,f_2,\dots ,f_r$overNand requirements$$k_1,k_2,\ldots ,k_r$$ $k_1,k_2,\dots ,k_r$the goal is to find a minimum weight subset$$S \subseteq N$$ $S\subseteq N$such that$$f_i(S) \ge k_i$$ $f_i\left(S\right)\ge k_i$for$$1 \le i \le r$$ $1\le i\le r$. We refer to this problem asMulti-Submod-Coverand it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$ $r=1$Multi-Submod-Covergeneralizes the well-known Submodular Set Cover problem (Submod-SC), and it can also be easily reduced toSubmod-SC. A simple greedy algorithm gives an$$O(\log (kr))$$ $O(log(kr\left)\right)$approximation where$$k = \sum _i k_i$$ $k={\sum }_i{k}_i$and this ratio cannot be improved in the general case. In this paper, motivated by several concrete applications, we consider two ways to improve upon the approximation given by the greedy algorithm. First, we give a bicriteria approximation algorithm forMulti-Submod-Coverthat covers each constraint to within a factor of$$(1-1/e-\varepsilon )$$ $(1-1/e-\epsilon )$while incurring an approximation of$$O(\frac{1}{\epsilon }\log r)$$ $O(\frac{1}{ϵ}logr)$in the cost. Second, we consider the special case when each$$f_i$$ $f_i$is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover (Partial-SC), covering integer programs (CIPs) and multiple vertex cover constraints Bera et al. (Theoret Comput Sci 555:2–8 Bera et al. 2014). Both these algorithms are based on mathematical programming relaxations that avoid the limitations of the greedy algorithm. We demonstrate the implications of our algorithms and related ideas to several applications ranging from geometric covering problems to clustering with outliers. Our work highlights the utility of the high-level model and the lens of submodularity in addressing this class of covering problems. 

   more » « less
4. Max-Cut with Multiple Cardinality Constraints

   https://doi.org/10.4230/lipics.approx/random.2025.13  

   Makarychev, Yury; Pittu, Madhusudhan Reddy; Vakilian, Ali (September 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Ene, Alina; Chattopadhyay, Eshan (Ed.)

   We study the classic Max-Cut problem under multiple cardinality constraints, which we refer to as the Constrained Max-Cut problem. Given a graph G = (V, E), a partition of the vertices into c disjoint parts V₁, …, V_c, and cardinality parameters k₁, …, k_c, the goal is to select a set S ⊆ V such that |S ∩ V_i| = k_i for each i ∈ [c], maximizing the total weight of edges crossing S (i.e., edges with exactly one endpoint in S).\r\nBy designing an approximate kernel for Constrained Max-Cut and building on the correlation rounding technique of Raghavendra and Tan (2012), we present a (0.858 - ε)-approximation algorithm for the problem when c = O(1). The algorithm runs in time O(min{k/ε, n}^poly(c/ε) + poly(n)), where k = ∑_{i∈[c]} k_i and n = |V|. This improves upon the (1/2 + ε₀)-approximation of Feige and Langberg (2001) for Max-Cut_k (the special case when c = 1, k₁ = k), and generalizes the (0.858 - ε)-approximation of Raghavendra and Tan (2012), which only applies when min{k,n-k} = Ω(n) and does not handle multiple constraints.\r\nWe also establish that, for general values of c, it is NP-hard to determine whether a feasible solution exists that cuts all edges. Finally, we present a 1/2-approximation algorithm for Max-Cut under an arbitrary matroid constraint. 

   more » « less
5. Type 𝐼𝐼 quantum subgroups of 𝔰𝔩_{𝔑}. ℑ: Symmetries of local modules

   https://doi.org/10.1090/cams/19  

   Edie-Michell, Cain (May 2023, Communications of the American Mathematical Society)

   This paper is the first of a pair that aims to classify a large number of the type I I II quantum subgroups of the categories C ( s l r + 1 , k ) \mathcal {C}(\mathfrak {sl}_{r+1}, k) . In this work we classify the braided auto-equivalences of the categories of local modules for all known type I I quantum subgroups of C ( s l r + 1 , k ) \mathcal {C}(\mathfrak {sl}_{r+1}, k) . We find that the symmetries are all non-exceptional except for four cases (up to level-rank duality). These exceptional cases are the orbifolds C ( s l 2 , 16 ) Rep ⁡ ( Z 2 ) 0 \mathcal {C}(\mathfrak {sl}_{2}, 16)^0_{\operatorname {Rep}(\mathbb {Z}_{2})} , C ( s l 3 , 9 ) Rep ⁡ ( Z 3 ) 0 \mathcal {C}(\mathfrak {sl}_{3}, 9)^0_{\operatorname {Rep}(\mathbb {Z}_{3})} , C ( s l 4 , 8 ) Rep ⁡ ( Z 4 ) 0 \mathcal {C}(\mathfrak {sl}_{4}, 8)^0_{\operatorname {Rep}(\mathbb {Z}_{4})} , and C ( s l 5 , 5 ) Rep ⁡ ( Z 5 ) 0 \mathcal {C}(\mathfrak {sl}_{5}, 5)^0_{\operatorname {Rep}(\mathbb {Z}_{5})} . We develop several technical tools in this work. We give a skein theoretic description of the orbifold quantum subgroups of C ( s l r + 1 , k ) \mathcal {C}(\mathfrak {sl}_{r+1}, k) . Our methods here are general, and the techniques developed will generalise to give skein theory for any orbifold of a braided tensor category. We also give a formulation of orthogonal level-rank duality in the type D D - D D case, which is used to construct one of the exceptionals. We uncover an unexpected connection between quadratic categories and exceptional braided auto-equivalences of the orbifolds. We use this connection to construct two of the four exceptionals. In the sequel to this paper we will use the classified braided auto-equivalences to construct the corresponding type I I II quantum subgroups of the categories C ( s l r + 1 , k ) \mathcal {C}(\mathfrak {sl}_{r+1}, k) . This will essentially finish the type I I II classification for s l n \mathfrak {sl}_n modulo type I I classification. When paired with Gannon’s type I I classification for r ≤ 6 r\leq 6 , our results will complete the type I I II classification for these same ranks. This paper includes an appendix by Terry Gannon, which provides useful results on the dimensions of objects in the categories C ( s l r + 1 , k ) \mathcal {C}(\mathfrak {sl}_{r+1}, k) . 

   more » « less