Algorithmica

We examine the complexity of the online Dictionary Matching with One Gap Problem (DMOG) which is the following. Preprocess a dictionary D of d patterns, where each pattern contains a special gap symbol that can match any string, so that given a text ...

Span programs are a model of computation that have been used to design quantum algorithms, mainly in the query model. It is known that for any decision problem, there exists a span program that leads to an algorithm with optimal quantum query complexity,...

In this paper we consider graphs whose edges are associated with a degree of importance, which may depend on the type of connections they represent or on how recently they appeared in the scene, in a streaming setting. The goal is to construct layouts ...

We show that randomization can lead to significant improvements for a few fundamental problems in distributed tracking. Our basis is the count-tracking problem, where there are k players, each holding a counter $n_i$ that gets incremented over time, ...$$${}_{}{}_{}$$$$\sqrt{}$

We study maximization subject to a budget constraint, where we are given a valuation function v, budget B and a cost $$c_i$$ci for each item i. The goal is to find a set S that maximizes v(S) subject to $$\Sigma _{i\in S}c_i\le B$$Σi?Sci≤B. Special ...

In the Partial Information Network Query (PINQ) problem, we are given a host graph H, and a pattern $${\mathcal {P}}$$P whose topology is partially known. We seek a connected subgraph of H that resembles$${\mathcal {P}}$$P. PINQ is a generalization of ...

Given a set of n sites in the plane, the order-k Voronoi diagram is a planar subdivision such that all points in a region share the same k nearest sites. The order-k Voronoi diagram arises for the k-nearest-neighbor problem, and there has been a lot of ...

In this paper, we consider a coverage problem for uncertain points in a tree. Let T be a tree containing a set $${\mathcal {P}}$$P of n (weighted) demand points, and the location of each demand point $$P_i\in {{\mathcal {P}}}$$Pi?P is uncertain but is ...

We consider the following semi-infinite linear programming problems: $$\max $$max (resp., $$\min $$min) $$c^Tx$$cTx s.t. $$y^TA_ix+(d^i)^Tx \le b_i$$yTAix+(di)Txýbi (resp., $$y^TA_ix+(d^i)^Tx \ge b_i)$$yTAix+(di)Tx bi), for all $$y \in {{\mathcal {Y}}}_...

Given a point s and a set of h pairwise disjoint polygonal obstacles with a total of n vertices in the plane, suppose a triangulation of the space outside the obstacles is given; we present an $$O(n+h\log h)$$ time and O(n) space algorithm for ...

We study the version of the C-Planarity problem in which edges connecting the same pair of clusters must be grouped into pipes, which generalizes the Strip Planarity problem. We give algorithms to decide several families of instances for the two ...

We prove that every set of $$\varDelta -1$$ slopes is 1-bend universal for the planar graphs with maximum vertex degree $$\varDelta $$. This means that any planar graph with maximum degree $$\varDelta $$ admits a planar drawing with at most one ...

Stable flows generalize the well-known concept of stable matchings to markets in which transactions may involve several agents, forwarding flow from one to another. An instance of the problem consists of a capacitated directed network in which vertices ...

In this paper we consider the classical connected dominating set problem. Twenty years ago, Guha and Khuller developed two algorithms for this problem--a centralized greedy approach with an approximation guarantee of $$H(\varDelta ) +2$$H(Δ)+2, and a ...

Let G be an undirected simple graph having n vertices and let $$f:V(G)\rightarrow \{0,\dots , n-1\}$$ be a function. An f-factor of G is a spanning subgraph H such that $$d_H(v)=f(v)$$ for every vertex $$v\in V(G)$$. The subgraph H is called a ...

In the longest common substring problem, we are given two strings of length n and must find a substring of maximal length that occurs in both strings. It is well known that the problem can be solved in linear time, but the solution is not robust ...