2012 | OriginalPaper | Chapter
Reducing a Target Interval to a Few Exact Queries
Authors : Jesper Nederlof, Erik Jan van Leeuwen, Ruben van der Zwaan
Published in: Mathematical Foundations of Computer Science 2012
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Many combinatorial problems involving weights can be formulated as a so-called
ranged problem
. That is, their input consists of a universe
U
, a (succinctly-represented) set family
$\mathcal{F} \subseteq 2^{U}$
, a weight function
ω
:
U
→ {1,…,
N
}, and integers 0 ≤
l
≤
u
≤ ∞. Then the problem is to decide whether there is an
$X \in \mathcal{F}$
such that
l
≤ ∑
e
∈
X
ω
(
e
) ≤
u
. Well-known examples of such problems include
Knapsack
,
Subset Sum
,
Maximum Matching
, and
Traveling Salesman
. In this paper, we develop a generic method to transform a ranged problem into an
exact problem
(i.e. a ranged problem for which
l
=
u
). We show that our method has several intriguing applications in exact exponential algorithms and parameterized complexity, namely:
In exact exponential algorithms, we present new insight into whether
Subset Sum
and
Knapsack
have efficient algorithms in both time and space. In particular, we show that the time and space complexity of
Subset Sum
and
Knapsack
are equivalent up to a small polynomial factor in the input size. We also give an algorithm that solves sparse instances of
Knapsack
efficiently in terms of space and time.
In parameterized complexity, we present the first kernelization results on weighted variants of several well-known problems. In particular, we show that weighted variants of
Vertex Cover
and
Dominating Set
,
Traveling Salesman
, and
Knapsack
all admit polynomial randomized Turing kernels when parameterized by |
U
|.
Curiously, our method relies on a technique more commonly found in approximation algorithms.