Aditya Anand

activity

20242026

most citedApproximating Small Sparse Cuts

1 citations · 2 across the 7 of their papers we have counts for

collaborators

Showing 2024Show all

5 papers · 1 filter

cs.DS2024

Min-CSPs on Complete Instances

Aditya Anand, Euiwoong Lee, Amatya Sharma

Given a fixed arity $k \geq 2$ , Min- $k$ -CSP on complete instances involves a set of $n$ variables $V$ and one nontrivial constraint for every $k$ -subset of variables (so there are…

cs.DS2024

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 $n$ -vertex graph $G$ , our a…

cs.DS2024★ 1 cited

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…

cs.DS2024★ 1 cited

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 $k$ , the number of edges or vertices cut in the optimal solutio…

cs.DS2024

Separating $k$ -Median from the Supplier Version

Aditya Anand, Euiwoong Lee

Given a metric space $(V, d)$ along with an integer $k$ , the $k$ -Median problem asks to open $k$ centers $C \subseteq V$ to minimize $\sum_{v \in V} d (v, C)$ , where $d(v, C) := \mi…

Min-CSPs on Complete Instances

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries

Unbreakable Decomposition in Close-to-Linear Time

Approximating Small Sparse Cuts

Separating k-Median from the Supplier Version

Separating $k$ -Median from the Supplier Version