research
∙
06/03/2023
On Approximability of Steiner Tree in ℓ_p-metrics
In the Continuous Steiner Tree problem (CST), we are given as input a se...
share
research
∙
05/26/2023
Can You Solve Closest String Faster than Exhaustive Search?
We study the fundamental problem of finding the best string to represent...
research
∙
05/04/2023
Impossibility of Depth Reduction in Explainable Clustering
Over the last few years Explainable Clustering has gathered a lot of att...
research
∙
10/18/2022
Clustering Categorical Data: Soft Rounding k-modes
Over the last three decades, researchers have intensively explored vario...
research
∙
02/21/2022
Obtaining Approximately Optimal and Diverse Solutions via Dispersion
There has been a long-standing interest in computing diverse solutions t...
research
∙
12/07/2021
Almost Polynomial Factor Inapproximability for Parameterized k-Clique
The k-Clique problem is a canonical hard problem in parameterized comple...
research
∙
12/06/2021
On Complexity of 1-Center in Various Metrics
We consider the classic 1-center problem: Given a set P of n points in a...
research
∙
11/21/2021
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics
K-median and k-means are the two most popular objectives for clustering ...
research
∙
11/10/2021
Applications of Random Algebraic Constructions to Hardness of Approximation
In this paper, we show how one may (efficiently) construct two types of ...
research
∙
09/30/2020
On Approximability of Clustering Problems Without Candidate Centers
The k-means objective is arguably the most widely-used cost function for...
research
∙
09/06/2020
On Hardness of Approximation of Parameterized Set Cover and Label Cover: Threshold Graphs from Error Correcting Codes
In the (k,h)-SetCover problem, we are given a collection 𝒮 of sets over ...
research
∙
08/15/2020
On Efficient Low Distortion Ultrametric Embedding
A classic problem in unsupervised learning and data analysis is to find ...
research
∙
08/12/2020
Deterministic Replacement Path Covering
In this article, we provide a unified and simplified approach to derando...
research
∙
06/08/2020
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
Parameterization and approximation are two popular ways of coping with N...
research
∙
09/24/2019
On Communication Complexity of Fixed Point Computation
Brouwer's fixed point theorem states that any continuous function from a...
research
∙
09/04/2019
Parameterized Intractability of Even Set and Shortest Vector Problem
The k-Even Set problem is a parameterized variant of the Minimum Distanc...
research
∙
08/27/2019
Hardness Amplification of Optimization Problems
In this paper, we prove a general hardness amplification scheme for opti...
research
∙
01/18/2019
Towards a General Direct Product Testing Theorem
The Direct Product encoding of a string a∈{0,1}^n on an underlying domai...
research
∙
12/03/2018
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
Given a set of n points in R^d, the (monochromatic) Closest Pair proble...
research
∙
03/26/2018
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH
The k-Even Set problem is a parameterized variant of the Minimum Distanc...
research
∙
11/29/2017