From the 1 of 4 linked papers with an AI index.
4 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…
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…
A Decomposition Approach to the Weighted -server Problem
Nikhil Ayyadevara, Ashish Chiplunkar, Amatya Sharma
A natural variant of the classical online -server problem is the Weighted -server problem, where the cost of moving a server is its weight times the distance through which it…