research
∙
08/29/2023
Parameterized and Approximation Algorithms for the Maximum Bimodal Subgraph Problem
A vertex of a plane digraph is bimodal if all its incoming edges (and he...
share
research
∙
08/29/2023
FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges
We study the α-Fixed Cardinality Graph Partitioning (α-FCGP) problem, th...
research
∙
08/21/2023
Parameterized Complexity of Fair Bisection: FPT-Approximation meets Unbreakability
In the Minimum Bisection problem, input is a graph G and the goal is to ...
research
∙
08/14/2023
Kernelization for Spreading Points
We consider the following problem about dispersing points. Given a set o...
research
∙
07/17/2023
Fixed-Parameter Algorithms for Fair Hitting Set Problems
Selection of a group of representatives satisfying certain fairness cons...
research
∙
05/02/2023
FPT Approximations for Capacitated/Fair Clustering with Outliers
Clustering problems such as k-Median, and k-Means, are motivated from ap...
research
∙
03/02/2023
Coresets for Clustering in Geometric Intersection Graphs
Designing coresets–small-space sketches of the data preserving cost of t...
research
∙
01/10/2023
Proportionally Fair Matching with Multiple Groups
The study of fair algorithms has become mainstream in machine learning a...
research
∙
12/01/2022
Clustering What Matters: Optimal Approximation for Clustering with Outliers
Clustering with outliers is one of the most fundamental problems in Comp...
research
∙
11/17/2022
(Re)packing Equal Disks into Rectangle
The problem of packing of equal disks (or circles) into a rectangle is a...
research
∙
08/14/2022
Exact Exponential Algorithms for Clustering Problems
In this paper we initiate a systematic study of exact algorithms for wel...
research
∙
11/11/2021
Non-Uniform k-Center and Greedy Clustering
In the Non-Uniform k-Center problem, a generalization of the famous k-ce...
research
∙
07/14/2021
ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space
De Berg et al. in [SICOMP 2020] gave an algorithmic framework for subexp...
research
∙
11/04/2019
Algorithms for Intersection Graphs of Multiple Intervals and Pseudo Disks
Intersection graphs of planar geometric objects such as intervals, disks...
research
∙
07/21/2019
A Constant Approximation for Colorful k-Center
In this paper, we consider the colorful k-center problem, which is a gen...
research
∙
11/15/2018
Large-Scale Distributed Algorithms for Facility Location with Outliers
This paper presents fast, distributed, O(1)-approximation algorithms for...
research
∙
09/18/2018
On the Partition Set Cover Problem
Various O( n) approximations are known for the Set Cover problem, where ...
research
∙
11/13/2017
On Partial Covering For Geometric Set Systems
We study a generalization of the Set Cover problem called the Partial Se...
research
∙
10/23/2017