1 citations · 2 across the 7 of their papers we have counts for
11 papers · 1 filter
Greedy Region Growing: Improved Approximations for Cutwidth, Pathwidth, Flow-Expander Decomposition, and More
Aditya Anand
We give a new rounding technique for spreading-metric linear programs, called Greedy Region Growing, which adapts the classical technique of region growing to min-max graph layout…
Socially Fair Clustering: Parameterized Approximation and Local Search
Aditya Anand, Yury Makarychev, Liren Shan
We study the Socially Fair Clustering problem introduced by Abbasi, Bhaskara, and Venkatasubramanian (2021) and Ghadiri, Samadi, and Vempala (2021), along with its extension, the $…
Spectral Dual Fitting for -Means
Aditya Anand, Moses Charikar, Vincent Cohen-Addad +5
We give a new dual fitting algorithm which gives improved approximation ratios of and for -Means in (high-dimensional) Euclidean and genera…
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…
Unbreakable Decomposition in Close-to-Linear Time
Aditya Anand, Euiwoong Lee, Jason Li +2
Unbreakable decomposition, introduced by Cygan et al. (SICOMP'19) and Cygan et al. (TALG'20), has proven to be one of the most powerful tools for parameterized graph cut problems i…
Approximating Small Sparse Cuts
Aditya Anand, Euiwoong Lee, Jason Li +1
We study polynomial-time approximation algorithms for (edge/vertex) Sparsest Cut and Small Set Expansion in terms of , the number of edges or vertices cut in the optimal solutio…
Separating -Median from the Supplier Version
Aditya Anand, Euiwoong Lee
Given a metric space along with an integer , the -Median problem asks to open centers to minimize , where $d(v, C) := \mi…