Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCovering Problems for Partial Words and for Indeterminate Strings
144
0
0.0
(
0
)
Added by
Tomasz Kociumaka
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider the problem of computing a shortest solid cover of an indeterminate string. An indeterminate string may contain non-solid symbols, each of which specifies a subset of the alphabet that could be present at the corresponding position. We also consider covering partial words, which are a special case of indeterminate strings where each non-solid symbol is a dont care symbol. We prove that indeterminate string covering problem and partial word covering problem are NP-complete for binary alphabet and show that both problems are fixed-parameter tractable with respect to $k$, the number of non-solid symbols. For the indeterminate string covering problem we obtain a $2^{O(k log k)} + n k^{O(1)}$-time algorithm. For the partial word covering problem we obtain a $2^{O(sqrt{k}log k)} + nk^{O(1)}$-time algorithm. We prove that, unless the Exponential Time Hypothesis is false, no $2^{o(sqrt{k})} n^{O(1)}$-time solution exists for either problem, which shows that our algorithm for this case is close to optimal. We also present an algorithm for both problems which is feasible in practice.
rate research
Read More
Given an indeterminate string pattern $p$ and an indeterminate string text $t$, the problem of order-preserving pattern matching with character uncertainties ($mu$OPPM) is to find all substrings of $t$ that satisfy one of the possible orderings defined by $p$. When the text and pattern are determinate strings, we are in the presence of the well-studied exact order-preserving pattern matching (OPPM) problem with diverse applications on time series analysis. Despite its relevance, the exact OPPM problem suffers from two major drawbacks: 1) the inability to deal with indetermination in the text, thus preventing the analysis of noisy time series; and 2) the inability to deal with indetermination in the pattern, thus imposing the strict satisfaction of the orders among all pattern positions. This paper provides the first polynomial algorithm to answer the $mu$OPPM problem when indetermination is observed on the pattern or text. Given two strings with length $m$ and $O(r)$ uncertain characters per string position, we show that the $mu$OPPM problem can be solved in $O(mrlg r)$ time when one string is indeterminate and $rinmathbb{N}^+$. Mappings into satisfiability problems are provided when indetermination is observed on both the pattern and the text, and results concerning the general problem complexity are presented as well, with $mu$OPPM problem proved to be NP-hard in general.
A factor $u$ of a word $w$ is a cover of $w$ if every position in $w$ lies within some occurrence of $u$ in $w$. A word $w$ covered by $u$ thus generalizes the idea of a repetition, that is, a word composed of exact concatenations of $u$. In this article we introduce a new notion of $alpha$-partial cover, which can be viewed as a relaxed variant of cover, that is, a factor covering at least $alpha$ positions in $w$. We develop a data structure of $O(n)$ size (where $n=|w|$) that can be constructed in $O(nlog n)$ time which we apply to compute all shortest $alpha$-partial covers for a given $alpha$. We also employ it for an $O(nlog n)$-time algorithm computing a shortest $alpha$-partial cover for each $alpha=1,2,ldots,n$.
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 $beta < 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$.
Covering problems are fundamental classical problems in optimization, computer science and complexity theory. Typically an input to these problems is a family of sets over a finite universe and the goal is to cover the elements of the universe with as few sets of the family as possible. The variations of covering problems include well known problems like Set Cover, Vertex Cover, Dominating Set and Facility Location to name a few. Recently there has been a lot of study on partial covering problems, a natural generalization of covering problems. Here, the goal is not to cover all the elements but to cover the specified number of elements with the minimum number of sets. In this paper we study partial covering problems in graphs in the realm of parameterized complexity. Classical (non-partial) version of all these problems have been intensively studied in planar graphs and in graphs excluding a fixed graph $H$ as a minor. However, the techniques developed for parameterized version of non-partial covering problems cannot be applied directly to their partial counterparts. The approach we use, to show that various partial covering problems are fixed parameter tractable on planar graphs, graphs of bounded local treewidth and graph excluding some graph as a minor, is quite different from previously known techniques. The main idea behind our approach is the concept of implicit branching. We find implicit branching technique to be interesting on its own and believe that it can be used for some other problems.
We show algorithms for computing representative families for matroid intersections and use them in fixed-parameter algorithms for set packing, set covering, and facility location problems with multiple matroid constraints. We complement our tractability results by hardness results.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
