Source author record

Sayan Bandyapadhyay

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Geometry Discrete Mathematics Computational Complexity Computer Science and Game Theory Machine Learning math.PR

Catalog footprint

Research overview

14works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Proportionally Fair Matching with Multiple Groups

The study of fair algorithms has become mainstream in machine learning and artificial intelligence due to its increasing demand in dealing with biases and discrimination. Along this line, researchers have considered fair versions of traditional optimization problems including clustering, regression, ranking and voting. However, most of the efforts have been channeled into designing heuristic algorithms, which often do not provide any guarantees on the quality of the solution. In this work, we study matching problems with the notion of proportional fairness. Proportional fairness is one of the most popular notions of group fairness where every group is represented up to an extent proportional to the final selection size. Matching with proportional fairness or more commonly, proportionally fair matching, was introduced in [Chierichetti et al., AISTATS, 2019], where the problem was studied with only two groups. However, in many practical applications, the number of groups -- although often a small constant -- is larger than two. In this work, we make the first step towards understanding the computational complexity of proportionally fair matching with more than two groups. We design exact and approximation algorithms achieving reasonable guarantees on the quality of the matching as well as on the time complexity. Our algorithms are also supported by suitable hardness bounds.

preprint2022arXiv

Geometric Planar Networks on Bichromatic Points

We study three classical graph problems - Hamiltonian path, minimum spanning tree, and minimum perfect matching on geometric graphs induced by bichromatic (red and blue) points. These problems have been widely studied for points in the Euclidean plane, and many of them are NP-hard. In this work, we consider these problems for collinear points. We show that almost all of these problems can be solved in linear time in this setting.

preprint2022arXiv

Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H-Minor-Free Graphs

We design the first subexponential-time (parameterized) algorithms for several cut and cycle-hitting problems on $H$ -minor free graphs. In particular, we obtain the following results (where $k$ is the solution-size parameter). 1. $2^{O(\sqrt{k}\log k)} \cdot n^{O(1)}$ time algorithms for Edge Bipartization and Odd Cycle Transversal; 2. a $2^{O(\sqrt{k}\log^4 k)} \cdot n^{O(1)}$ time algorithm for Edge Multiway Cut and a $2^{O(r \sqrt{k} \log k)} \cdot n^{O(1)}$ time algorithm for Vertex Multiway Cut, where $r$ is the number of terminals to be separated; 3. a $2^{O((r+\sqrt{k})\log^4 (rk))} \cdot n^{O(1)}$ time algorithm for Edge Multicut and a $2^{O((\sqrt{rk}+r) \log (rk))} \cdot n^{O(1)}$ time algorithm for Vertex Multicut, where $r$ is the number of terminal pairs to be separated; 4. a $2^{O(\sqrt{k} \log g \log^4 k)} \cdot n^{O(1)}$ time algorithm for Group Feedback Edge Set and a $2^{O(g \sqrt{k}\log(gk))} \cdot n^{O(1)}$ time algorithm for Group Feedback Vertex Set, where $g$ is the size of the group. 5. In addition, our approach also gives $n^{O(\sqrt{k})}$ time algorithms for all above problems with the exception of $n^{O(r+\sqrt{k})}$ time for Edge/Vertex Multicut and $(ng)^{O(\sqrt{k})}$ time for Group Feedback Edge/Vertex Set. We obtain our results by giving a new decomposition theorem on graphs of bounded genus, or more generally, an $h$ -almost-embeddable graph for any fixed constant $h$ . In particular we show the following. Let $G$ be an $h$ -almost-embeddable graph for a constant $h$ . Then for every $p\in\mathbb{N}$ , there exist disjoint sets $Z_1,\dots,Z_p \subseteq V(G)$ such that for every $i \in \{1,\dots,p\}$ and every $Z'\subseteq Z_i$ , the treewidth of $G/(Z_i\backslash Z')$ is $O(p+|Z'|)$ . Here $G/(Z_i\backslash Z')$ is the graph obtained from $G$ by contracting edges with both endpoints in $Z_i \backslash Z'$ .

preprint2020arXiv

Approximate Covering with Lower and Upper Bounds via LP Rounding

In this paper, we study the lower- and upper-bounded covering (LUC) problem, where we are given a set $P$ of $n$ points, a collection $\mathcal{B}$ of balls, and parameters $L$ and $U$ . The goal is to find a minimum-sized subset $\mathcal{B}'\subseteq \mathcal{B}$ and an assignment of the points in $P$ to $\mathcal{B}'$ , such that each point $p\in P$ is assigned to a ball that contains $p$ and for each ball $B_i\in \mathcal{B}'$ , at least $L$ and at most $U$ points are assigned to $B_i$ . We obtain an LP rounding based constant approximation for LUC by violating the lower and upper bound constraints by small constant factors and expanding the balls by again a small constant factor. Similar results were known before for covering problems with only the upper bound constraint. We also show that with only the lower bound constraint, the above result can be obtained without any lower bound violation. Covering problems have close connections with facility location problems. We note that the known constant-approximation for the corresponding lower- and upper-bounded facility location problem, violates the lower and upper bound constraints by a constant factor.

preprint2020arXiv

Improved Bounds for Metric Capacitated Covering Problems

In the Metric Capacitated Covering (MCC) problem, given a set of balls $\mathcal{B}$ in a metric space $P$ with metric $d$ and a capacity parameter $U$ , the goal is to find a minimum sized subset $\mathcal{B}'\subseteq \mathcal{B}$ and an assignment of the points in $P$ to the balls in $\mathcal{B}'$ such that each point is assigned to a ball that contains it and each ball is assigned with at most $U$ points. MCC achieves an $O(\log |P|)$ -approximation using a greedy algorithm. On the other hand, it is hard to approximate within a factor of $o(\log |P|)$ even with $β< 3$ factor expansion of the balls. Bandyapadhyay~{et al.} [SoCG 2018, DCG 2019] showed that one can obtain an $O(1)$ -approximation for the problem with $6.47$ factor expansion of the balls. An open question left by their work is to reduce the gap between the lower bound $3$ and the upper bound $6.47$ . In this current work, we show that it is possible to obtain an $O(1)$ -approximation with only $4.24$ factor expansion of the balls. We also show a similar upper bound of $5$ for a more generalized version of MCC for which the best previously known bound was $9$ .

preprint2020arXiv

On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications

Fair clustering is a constrained variant of clustering where the goal is to partition a set of colored points, such that the fraction of points of any color in every cluster is more or less equal to the fraction of points of this color in the dataset. This variant was recently introduced by Chierichetti et al. [NeurIPS, 2017] in a seminal work and became widely popular in the clustering literature. In this paper, we propose a new construction of coresets for fair clustering based on random sampling. The new construction allows us to obtain the first coreset for fair clustering in general metric spaces. For Euclidean spaces, we obtain the first coreset whose size does not depend exponentially on the dimension. Our coreset results solve open questions proposed by Schmidt et al. [WAOA, 2019] and Huang et al. [NeurIPS, 2019]. The new coreset construction helps to design several new approximation and streaming algorithms. In particular, we obtain the first true constant-approximation algorithm for metric fair clustering, whose running time is fixed-parameter tractable (FPT). In the Euclidean case, we derive the first $(1+ε)$ -approximation algorithm for fair clustering whose time complexity is near-linear and does not depend exponentially on the dimension of the space. Besides, our coreset construction scheme is fairly general and gives rise to coresets for a wide range of constrained clustering problems. This leads to improved constant-approximations for these problems in general metrics and near-linear time $(1+ε)$ -approximations in the Euclidean metric.

preprint2020arXiv

On Perturbation Resilience of Non-Uniform $k$ -Center

The Non-Uniform $k$ -center (NUkC) problem has recently been formulated by Chakrabarty, Goyal and Krishnaswamy [ICALP, 2016] as a generalization of the classical $k$ -center clustering problem. In NUkC, given a set of $n$ points $P$ in a metric space and non-negative numbers $r_1, r_2, \ldots , r_k$ , the goal is to find the minimum dilation $α$ and to choose $k$ balls centered at the points of $P$ with radius $α\cdot r_i$ for $1\le i\le k$ , such that all points of $P$ are contained in the union of the chosen balls. They showed that the problem is NP-hard to approximate within any factor even in tree metrics. On the other hand, they designed a "bi-criteria" constant approximation algorithm that uses a constant times $k$ balls. Surprisingly, no true approximation is known even in the special case when the $r_i$ 's belong to a fixed set of size 3. In this paper, we study the NUkC problem under perturbation resilience, which was introduced by Bilu and Linial [Combinatorics, Probability and Computing, 2012]. We show that the problem under 2-perturbation resilience is polynomial time solvable when the $r_i$ 's belong to a constant sized set. However, we show that perturbation resilience does not help in the general case. In particular, our findings imply that even with perturbation resilience one cannot hope to find any "good" approximation for the problem.

preprint2016arXiv

Approximate Clustering via Metric Partitioning

In this paper we consider two metric covering/clustering problems - \textit{Minimum Cost Covering Problem} (MCC) and $k$ -clustering. In the MCC problem, we are given two point sets $X$ (clients) and $Y$ (servers), and a metric on $X \cup Y$ . We would like to cover the clients by balls centered at the servers. The objective function to minimize is the sum of the $α$ -th power of the radii of the balls. Here $α\geq 1$ is a parameter of the problem (but not of a problem instance). MCC is closely related to the $k$ -clustering problem. The main difference between $k$ -clustering and MCC is that in $k$ -clustering one needs to select $k$ balls to cover the clients. For any $\eps > 0$, we describe quasi-polynomial time $(1 + \eps)$ approximation algorithms for both of the problems. However, in case of $k$ -clustering the algorithm uses $(1 + \eps)k$ balls. Prior to our work, a $3^α$ and a ${c}^α$ approximation were achieved by polynomial-time algorithms for MCC and $k$ -clustering, respectively, where $c > 1$ is an absolute constant. These two problems are thus interesting examples of metric covering/clustering problems that admit $(1 + \eps)$-approximation (using $(1+\eps)k$ balls in case of $k$ -clustering), if one is willing to settle for quasi-polynomial time. In contrast, for the variant of MCC where $α$ is part of the input, we show under standard assumptions that no polynomial time algorithm can achieve an approximation factor better than $O(\log |X|)$ for $α\geq \log |X|$ .

preprint2016arXiv

Polynomial Time Algorithms for Bichromatic Problems

In this article, we consider a collection of geometric problems involving points colored by two colors (red and blue), referred to as bichromatic problems. The motivation behind studying these problems is two fold; (i) these problems appear naturally and frequently in the fields like Machine learning, Data mining, and so on, and (ii) we are interested in extending the algorithms and techniques for single point set (monochromatic) problems to bichromatic case. For all the problems considered in this paper, we design low polynomial time exact algorithms. These algorithms are based on novel techniques which might be of independent interest.

preprint2015arXiv

A Constant Factor Approximation for Orthogonal Order Preserving Layout Adjustment

Given an initial placement of a set of rectangles in the plane, we consider the problem of finding a disjoint placement of the rectangles that minimizes the area of the bounding box and preserves the orthogonal order i.e.\ maintains the sorted ordering of the rectangle centers along both $x$ -axis and $y$ -axis with respect to the initial placement. This problem is known as Layout Adjustment for Disjoint Rectangles(LADR). It was known that LADR is $\mathbb{NP}$ -hard, but only heuristics were known for it. We show that a certain decision version of LADR is $\mathbb{APX}$ -hard, and give a constant factor approximation for LADR.

preprint2015arXiv

On Variants of k-means Clustering

\textit{Clustering problems} often arise in the fields like data mining, machine learning etc. to group a collection of objects into similar groups with respect to a similarity (or dissimilarity) measure. Among the clustering problems, specifically \textit{ $k$ -means} clustering has got much attention from the researchers. Despite the fact that $k$ -means is a very well studied problem its status in the plane is still an open problem. In particular, it is unknown whether it admits a PTAS in the plane. The best known approximation bound in polynomial time is $9+\eps$. In this paper, we consider the following variant of $k$ -means. Given a set $C$ of points in $\mathcal{R}^d$ and a real $f > 0$ , find a finite set $F$ of points in $\mathcal{R}^d$ that minimizes the quantity $f*|F|+\sum_{p\in C} \min_{q \in F} {||p-q||}^2$ . For any fixed dimension $d$ , we design a local search PTAS for this problem. We also give a "bi-criterion" local search algorithm for $k$ -means which uses $(1+\eps)k$ centers and yields a solution whose cost is at most $(1+\eps)$ times the cost of an optimal $k$ -means solution. The algorithm runs in polynomial time for any fixed dimension. The contribution of this paper is two fold. On the one hand, we are being able to handle the square of distances in an elegant manner, which yields near optimal approximation bound. This leads us towards a better understanding of the $k$ -means problem. On the other hand, our analysis of local search might also be useful for other geometric problems. This is important considering that very little is known about the local search method for geometric approximation.

preprint2014arXiv

A Variant of the Maximum Weight Independent Set Problem

We study a natural extension of the Maximum Weight Independent Set Problem (MWIS), one of the most studied optimization problems in Graph algorithms. We are given a graph $G=(V,E)$ , a weight function $w: V \rightarrow \mathbb{R^+}$ , a budget function $b: V \rightarrow \mathbb{Z^+}$ , and a positive integer $B$ . The weight (resp. budget) of a subset of vertices is the sum of weights (resp. budgets) of the vertices in the subset. A $k$ -budgeted independent set in $G$ is a subset of vertices, such that no pair of vertices in that subset are adjacent, and the budget of the subset is at most $k$ . The goal is to find a $B$ -budgeted independent set in $G$ such that its weight is maximum among all the $B$ -budgeted independent sets in $G$ . We refer to this problem as MWBIS. Being a generalization of MWIS, MWBIS also has several applications in Scheduling, Wireless networks and so on. Due to the hardness results implied from MWIS, we study the MWBIS problem in several special classes of graphs. We design exact algorithms for trees, forests, cycle graphs, and interval graphs. In unweighted case we design an approximation algorithm for $d+1$ -claw free graphs whose approximation ratio ( $d$ ) is competitive with the approximation ratio ( $\frac{d}{2}$ ) of MWIS (unweighted). Furthermore, we extend Baker's technique \cite{Baker83} to get a PTAS for MWBIS in planar graphs.

preprint2014arXiv

Approximation Schemes for Partitioning: Convex Decomposition and Surface Approximation

We revisit two NP-hard geometric partitioning problems - convex decomposition and surface approximation. Building on recent developments in geometric separators, we present quasi-polynomial time algorithms for these problems with improved approximation guarantees.

preprint2014arXiv

Voronoi Game on Graphs

\textit{Voronoi game} is a geometric model of competitive facility location problem played between two players. Users are generally modeled as points uniformly distributed on a given underlying space. Each player chooses a set of points in the underlying space to place their facilities. Each user avails service from its nearest facility. Service zone of a facility consists of the set of users which are closer to it than any other facility. Payoff of each player is defined by the quantity of users served by all of its facilities. The objective of each player is to maximize their respective payoff. In this paper we consider the two players {\it Voronoi game} where the underlying space is a road network modeled by a graph. In this framework we consider the problem of finding $k$ optimal facility locations of Player 2 given any placement of $m$ facilities by Player 1. Our main result is a dynamic programming based polynomial time algorithm for this problem on tree network. On the other hand, we show that the problem is strongly $\mathcal{NP}$ -complete for graphs. This proves that finding a winning strategy of P2 is $\mathcal{NP}$ -complete. Consequently, we design an $1-\frac{1}{e}$ factor approximation algorithm, where $e \approx 2.718$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Sayan Bandyapadhyay

Research overview

Is this your work?

14 publications

Proportionally Fair Matching with Multiple Groups

Geometric Planar Networks on Bichromatic Points

Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H-Minor-Free Graphs

Approximate Covering with Lower and Upper Bounds via LP Rounding

Improved Bounds for Metric Capacitated Covering Problems

On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications

On Perturbation Resilience of Non-Uniform $k$ -Center

Approximate Clustering via Metric Partitioning

Polynomial Time Algorithms for Bichromatic Problems

A Constant Factor Approximation for Orthogonal Order Preserving Layout Adjustment

On Variants of k-means Clustering

A Variant of the Maximum Weight Independent Set Problem

Approximation Schemes for Partitioning: Convex Decomposition and Surface Approximation

Voronoi Game on Graphs

See the researcher in context

Building this map preview

Sayan Bandyapadhyay

Research overview

Is this your work?

14 publications

Proportionally Fair Matching with Multiple Groups

Geometric Planar Networks on Bichromatic Points

Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H-Minor-Free Graphs

Approximate Covering with Lower and Upper Bounds via LP Rounding

Improved Bounds for Metric Capacitated Covering Problems

On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications

On Perturbation Resilience of Non-Uniform kkk-Center

Approximate Clustering via Metric Partitioning

Polynomial Time Algorithms for Bichromatic Problems

A Constant Factor Approximation for Orthogonal Order Preserving Layout Adjustment

On Variants of k-means Clustering

A Variant of the Maximum Weight Independent Set Problem

Approximation Schemes for Partitioning: Convex Decomposition and Surface Approximation

Voronoi Game on Graphs

See the researcher in context

Building this map preview

On Perturbation Resilience of Non-Uniform $k$ -Center