Zobrazeno 1 - 10
of 762
pro vyhledávání: '"Karthik, C"'
Parameterized Inapproximability Hypothesis (PIH) is a central question in the field of parameterized complexity. PIH asserts that given as input a 2-CSP on $k$ variables and alphabet size $n$, it is W[1]-hard parameterized by $k$ to distinguish if th
Externí odkaz:
http://arxiv.org/abs/2407.08917
In the Euclidean $k$-means problems we are given as input a set of $n$ points in $\mathbb{R}^d$ and the goal is to find a set of $k$ points $C\subseteq \mathbb{R}^d$, so as to minimize the sum of the squared Euclidean distances from each point in $P$
Externí odkaz:
http://arxiv.org/abs/2405.13877
Autor:
S., Karthik C., Rahul, Saladi
In this work, we present a plethora of results for the range longest increasing subsequence problem (Range-LIS) and its variants. The input to Range-LIS is a sequence $\mathcal{S}$ of $n$ real numbers and a collection $\mathcal{Q}$ of $m$ query range
Externí odkaz:
http://arxiv.org/abs/2404.04795
The Ulam distance of two permutations on $[n]$ is $n$ minus the length of their longest common subsequence. In this paper, we show that for every $\varepsilon>0$, there exists some $\alpha>0$, and an infinite set $\Gamma\subseteq \mathbb{N}$, such th
Externí odkaz:
http://arxiv.org/abs/2401.17235
On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
Autor:
S., Karthik C., Manurangsi, Pasin
The field of combinatorial reconfiguration studies search problems with a focus on transforming one feasible solution into another. Recently, Ohsaka [STACS'23] put forth the Reconfiguration Inapproximability Hypothesis (RIH), which roughly asserts th
Externí odkaz:
http://arxiv.org/abs/2312.17140
In the Max-k-diameter problem, we are given a set of points in a metric space, and the goal is to partition the input points into k parts such that the maximum pairwise distance between points in the same part of the partition is minimized. The appro
Externí odkaz:
http://arxiv.org/abs/2312.02097
In the Euclidean Steiner Tree problem, we are given as input a set of points (called terminals) in the $\ell_2$-metric space and the goal is to find the minimum-cost tree connecting them. Additional points (called Steiner points) from the space can b
Externí odkaz:
http://arxiv.org/abs/2312.01252
Assuming the Exponential Time Hypothesis (ETH), a result of Marx (ToC'10) implies that there is no $f(k)\cdot n^{o(k/\log k)}$ time algorithm that can solve 2-CSPs with $k$ constraints (over a domain of arbitrary large size $n$) for any computable fu
Externí odkaz:
http://arxiv.org/abs/2311.05913
In the Continuous Steiner Tree problem (CST), we are given as input a set of points (called terminals) in a metric space and ask for the minimum-cost tree connecting them. Additional points (called Steiner points) from the metric space can be introdu
Externí odkaz:
http://arxiv.org/abs/2306.02189
We study the fundamental problem of finding the best string to represent a given set, in the form of the Closest String problem: Given a set $X \subseteq \Sigma^d$ of $n$ strings, find the string $x^*$ minimizing the radius of the smallest Hamming ba
Externí odkaz:
http://arxiv.org/abs/2305.16878