203 citations · 288 across the 21 of their papers we have counts for
18 papers · 1 filter
Online Algorithms for Matchings with Proportional Fairness Constraints and Diversity Constraints
Anand Louis, Meghana Nasre, Prajakta Nimbhorkar +1
Matching problems with group-fairness constraints and diversity constraints have numerous applications such as in allocation problems, committee selection, school choice, etc. More…
Approximating CSPs with Outliers
Suprovat Ghoshal, Anand Louis
Constraint satisfaction problems (CSPs) are ubiquitous in theoretical computer science. We study the problem of StrongCSPs, i.e. instances where a large induced sub-instance has a…
Exact recovery algorithm for Planted Bipartite Graph in Semi-random Graphs
Akash Kumar, Anand Louis, Rameesh Paul
The problem of finding the largest induced balanced bipartite subgraph in a given graph is NP-hard. This problem is closely related to the problem of finding the smallest Odd Cycle…
Matchings with Group Fairness Constraints: Online and Offline Algorithms
Govind S. Sankar, Anand Louis, Meghana Nasre +1
We consider the problem of assigning items to platforms in the presence of group fairness constraints. In the input, each item belongs to certain categories, called classes in this…
Independent Sets in Semi-random Hypergraphs
Yash Khanna, Anand Louis, Rameesh Paul
A set of vertices in a hypergraph is called an independent set if no hyperedge is completely contained inside the set. Given a hypergraph, computing its largest size independent se…
Group Fairness for Knapsack Problems
Deval Patel, Arindam Khan, Anand Louis
We study the knapsack problem with group fairness constraints. The input of the problem consists of a knapsack of bounded capacity and a set of items, each item belongs to a partic…
Approximation Algorithms and Hardness for Strong Unique Games
Suprovat Ghoshal, Anand Louis
The UNIQUE GAMES problem is a central problem in algorithms and complexity theory. Given an instance of UNIQUE GAMES, the STRONG UNIQUE GAMES problem asks to find the largest subse…
Planted Models for the Densest -Subgraph Problem
Yash Khanna, Anand Louis
Given an undirected graph , the Densest -subgraph problem (DkS) asks to compute a set of cardinality such that the weight of…
Planted Models for -way Edge and Vertex Expansion
Anand Louis, Rakesh Venkat
Graph partitioning problems are a central topic of study in algorithms and complexity theory. Edge expansion and vertex expansion, two popular graph partitioning objectives, seek a…
Approximation Algorithms for Partially Colorable Graphs
Suprovat Ghoshal, Anand Louis, Rahul Raychaudhury
Graph coloring problems are a central topic of study in the theory of algorithms. We study the problem of partially coloring partially colorable graphs. For and $k \in \m…
Semi-Random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
Anand Louis, Rakesh Venkat
The problem of computing the vertex expansion of a graph is an NP-hard problem. The current best worst-case approximation guarantees for computing the vertex expansion of a graph a…
On Euclidean -Means Clustering with -Center Proximity
Amit Deshpande, Anand Louis, Apoorv Vikram Singh
-means clustering is NP-hard in the worst case but previous work has shown efficient algorithms assuming the optimal -means clusters are \emph{stable} under additive or multi…
Accelerated Newton Iteration: Roots of Black Box Polynomials and Matrix Eigenvalues
Anand Louis, Santosh S. Vempala
We study the problem of computing the largest root of a real rooted polynomial to within error given only black box access to it, i.e., for any $x \in {\mathb…
Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion
Anand Louis, Yury Makarychev
The expansion of a hypergraph, a natural extension of the notion of expansion in graphs, is defined as the minimum over all cuts in the hypergraph of the ratio of the number of the…
Approximation Algorithm for Sparsest k-Partitioning
Anand Louis, Konstantin Makarychev
Given a graph , the sparsest-cut problem asks to find the set of vertices which has the least expansion defined as $$ϕ_G(S) := \frac{w(E(S,\bar{S}))}{\min \set{w(S), w(\bar{…
Many Sparse Cuts via Higher Eigenvalues
Anand Louis, Prasad Raghavendra, Prasad Tetali +1
Cheeger's fundamental inequality states that any edge-weighted graph has a vertex subset such that its expansion (a.k.a. conductance) is bounded as follows: \[ ϕ(S) \defeq \fra…
Cut-Matching Games on Directed Graphs
Anand Louis
We give O(log^2 n)-approximation algorithm based on the cut-matching framework of [10, 13, 14] for computing the sparsest cut on directed graphs. Our algorithm uses only O(log^2 n)…
Improved Algorithm for Degree Bounded Survivable Network Design Problem
Anand Louis, Nisheeth Vishnoi
We consider the Degree-Bounded Survivable Network Design Problem: the objective is to find a minimum cost subgraph satisfying the given connectivity requirements as well as the deg…