From the 1 of 6 linked papers with an AI index.
6 papers
Spectral Dual Fitting for -Means
Aditya Anand, Moses Charikar, Vincent Cohen-Addad +5
The paper introduces a new dual‑fitting algorithm that achieves better approximation ratios for the k‑means clustering problem in both Euclidean and general metric spaces, using a…
Complexity of Local Search for CSPs Parameterized by Constraint Difference
Aditya Anand, Vincent Cohen-Addad, Tommaso d'Orsi +4
In this paper, we study the parameterized complexity of local search, whose goal is to find a good nearby solution from the given current solution. Formally, given an optimization…
All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
Aditya Anand, Euiwoong Lee, Jason Li +1
Given a directed graph with vertices and edges, a parameter and two disjoint subsets , we show that the number of all-subsets important separato…
Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
Aditya Anand, Euiwoong Lee, Davide Mazzali +1
This paper studies complete -Constraint Satisfaction Problems (CSPs), where an -variable instance has exactly one nontrivial constraint for each subset of variables, i.e.…
Min-CSPs on Complete Instances
Aditya Anand, Euiwoong Lee, Amatya Sharma
Given a fixed arity , Min--CSP on complete instances involves a set of variables and one nontrivial constraint for every -subset of variables (so there are…
Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
Aditya Anand, Thatchaphol Saranurak, Yunfan Wang
We give the first deterministic algorithm that makes sub-quadratic queries to find the global min-cut of a simple graph in the cut query model. Given an -vertex graph , our a…