Algorithms and Computation

Nowadays, route planning systems belong to the most frequently used information systems. The algorithmic core problem of such systems, i.e., the fast computation of shortest paths is a classical problem that can be solved by Dijkstra’s shortest paths algorithm. However, for the huge datasets that frequently appear in route planning the algorithm is far too slow. Recently, algorithms for route planning in transportation networks have undergone a rapid development, leading to methods that are more than a million times faster than Dijkstra’s algorithm. In particular, computing shortest paths in huge networks has become a showpiece of algorithm engineering demonstrating the engineering cycle that consists of design, analysis, implementation and experimental evaluation of practicable algorithms. In this talk, we provide a condensed overview of the techniques enabling this development. In particular, new theoretical insights on when and why those techniques work so well will be discussed. The main part of the talk will focus on variants of the problem that occur in more realistic traffic scenarios.

Computing approximate solutions for NP-hard problems is an important research endeavor. Since the work of Goemans-Williamson in 1993, semidefinite programming (a form of convex programming in which the variables are vector inner products) has been used to design the current best approximation algorithms for problems such as MAX-CUT, MAX-3SAT, SPARSEST CUT, GRAPH COLORING, etc. The talk will survey this area, as well as its fascinating connections with topics such as geometric embeddings of metric spaces, and Khot’s unique games conjecture.

The talk will be self-contained.

The School Bus Problem is an NP-hard vehicle routing problem in which the goal is to route buses that transport children to a school such that for each child, the distance travelled on the bus does not exceed the shortest distance from the child’s home to the school by more than a given

regret

threshold. Subject to this constraint and bus capacity limit, the goal is to minimize the number of buses required.

In this paper, we give a polynomial time 4-approximation algorithm when the children and school are located at vertices of a fixed

tree

. As a byproduct of our analysis, we show that the integrality gap of the natural set-cover formulation for this problem is also bounded by 4. We also present a constant approximation for the variant where we have a fixed number of buses to use, and the goal is to minimize the maximum regret.

In this paper we give improved approximation algorithms for some network design problems. In the Bounded-Diameter or Shallow-Light

k

-Steiner tree problem (SL

k

ST), we are given an undirected graph

G

 = (

V

,

E

) with terminals

T

 ⊆ 

V

containing a root

r

 ∈ 

T

, a cost function

c

:

E

 → ℝ

 + 

, a length function ℓ:

E

 → ℝ

 + 

, a bound

L

 > 0 and an integer

k

 ≥ 1. The goal is to find a minimum

c

-cost

r

-rooted Steiner tree containing at least

k

terminals whose diameter under ℓ metric is at most

L

. The input to the Buy-at-Bulk

k

-Steiner tree problem (BB

k

ST) is similar: graph

G

 = (

V

,

E

), terminals

T

 ⊆ 

V

, cost and length functions

c

,ℓ:

E

 → ℝ

 + 

, and an integer

k

 ≥ 1. The goal is to find a minimum total cost

r

-rooted Steiner tree

H

containing at least

k

terminals, where the cost of each edge

e

is

c

(

e

) + ℓ(

e

)·

f

(

e

) where

f

(

e

) denotes the number of terminals whose path to root in

H

contains edge

e

. We present a bicriteria (

O

(log

2

n

),

O

(log

n

))-approximation for SL

k

ST: the algorithm finds a

k

-Steiner tree of diameter at most

O

(

L

·log

n

) whose cost is at most

$O(\log^2 n\cdot\mbox{\sc opt}^*)$

where

$\mbox{\sc opt}^*$

is the cost of an LP relaxation of the problem. This improves on the algorithm of [9] with ratio (

O

(log

4

n

),

O

(log

2

n

)). Using this, we obtain an

O

(log

3

n

)-approximation for BB

k

ST, which improves upon the

O

(log

4

n

)-approximation of [9]. We also consider the problem of finding a minimum cost 2-edge-connected subgraph with at least

k

vertices, which is introduced as the (

k

,2)-subgraph problem in [14]. We give an

O

(log

n

)-approximation algorithm for this problem which improves upon the

O

(log

2

n

)-approximation of [14].

We investigate a generalization of classical shop scheduling where

n

jobs are located at the vertices of a general undirected graph and

m

machines must travel between the vertices to process the jobs. The aim is to minimize the makespan. For the open shop problem, we develop an

O

(log

m

loglog

m

)-approximation algorithm that significantly improves upon the best known

$O(\sqrt{m})$

-approximation algorithm. For the flow shop problem, we present an

O

(

m

2/3

)-approximation algorithm that improves upon the best known

$\max\{\frac{m+1}{2},\rho\}$

-approximation algorithm, where

ρ

is the approximation factor for metric TSP.

In this experimental study we consider contraction-based Steiner tree approximations. This class contains the only approximation algorithms that guarantee a constant approximation ratio below 2 and still may be applicable in practice. Despite their vivid evolution in theory, these algorithms have, to our knowledge, never been thoroughly investigated in practice before, which is particularly interesting as most of these algorithms’ approximation guarantees only hold when some (constant) parameter

k

tends to infinity, while the running time is exponentially dependent on this very

k

.

We investigate different implementation aspects and parameter choices which finally allow us to construct algorithms feasible for practical use. Then we compare these algorithms against each other and against state-of-the-art approaches.

We consider new versions of the two-center problem where the input consists of a set

$\mathcal{D}$

of disks in the plane. We first study the problem of finding two smallest congruent disks such that each disk in

$\mathcal{D}$

intersects one of these two disks. Then we study the problem of covering the set

$\mathcal{D}$

by two smallest congruent disks. We give exact and approximation algorithms for these versions.

Given a simple rectilinear polygon

P

in the

xy

-plane, a

roof

over

P

is a terrain over

P

whose faces are supported by planes through edges of

P

that make a dihedral angle

π

/4 with the

xy

-plane. In this paper, we introduce

realistic roofs

by imposing a few additional constraints. We investigate the geometric and combinatorial properties of realistic roofs, and show a connection with the straight skeleton of

P

. We show that the maximum possible number of distinct realistic roofs over

P

is

$(n-4)/2 \choose \lfloor(n-4)/4\rfloor$

when

P

has

n

vertices. We present an algorithm that enumerates a combinatorial representation of each such roof in

O

(1) time per roof without repetition, after

O

(

n

4

) preprocessing time. We also present an

O

(

n

5

)-time algorithm for computing a realistic roof with minimum height or volume.

We present several algorithms for computing the visibility polygon of a simple polygon

$\ensuremath{\mathcal{P}}$

from a viewpoint inside the polygon, when the polygon resides in read-only memory and only few working variables can be used. The first algorithm uses a constant number of variables, and outputs the vertices of the visibility polygon in

$O(n\ensuremath{\bar{r}})$

time, where

$\ensuremath{\bar{r}}$

denotes the number of reflex vertices of

$\ensuremath{\mathcal{P}}$

that are part of the output. The next two algorithms use

O

(log

r

) variables, and output the visibility polygon in

O

(

n

log

r

) randomized expected time or

O

(

n

log

2

r

) deterministic time, where

r

is the number of reflex vertices of

$\ensuremath{\mathcal{P}}$

.

We consider a topology control problem in which we are given a set of

n

sensors in ℝ

d

and we would like to assign a communication radius to each of them. The radii assignment must generate a strongly connected network and have low receiver-based interference (defined as the largest in-degree of the network). We give an algorithm that generates a network with

O

(logΔ) interference, where Δ is the interference of a uniform-radius network. Since the radius of each sensor only depends on its neighbors, it can be computed in a distributed fashion. Moreover, this construction will never assign communication radius larger than

R

min

to a sensor, where

R

min

is the minimum value needed to obtain strong connectivity. We also show that Ω(log

n

) interference is needed for some instances, making our algorithms asymptotically optimal.

We introduce a new family of graphs for which the Hamiltonian path problem is non-trivial and yet has a linear time solution. The square of a graph

G

 = (

V

,

E

), denoted as

G

2

, is a graph with the set of vertices

V

, in which two vertices are connected by an edge if there exists a path of length at most 2 connecting them in

G

. Harary & Schwenk (1971) proved that the square of a tree

T

contains a Hamiltonian cycle if and only if

T

is a caterpillar, i.e., it is a single path with several leafs connected to it. Our first main result is a simple graph-theoretic characterization of trees

T

for which

T

2

contains a Hamiltonian path:

T

2

has a Hamiltonian path if and only if

T

is a horsetail (the name is due to the characteristic shape of these trees, see Figure 1). Our next results are two efficient algorithms: linear time testing if

T

2

contains a Hamiltonian path and finding such a path (if there is any), and linear time preprocessing after which we can check for any pair (

u

,

v

) of nodes of

T

in constant time if there is a Hamiltonian path from

u

to

v

in

T

2

.

Let

G

be a finite undirected graph with edge set

E

. An edge set

E

′ ⊆ 

E

is an

induced matching

in

G

if the pairwise distance of the edges of

E

′ in

G

is at least two;

E

′ is

dominating

in

G

if every edge

e

 ∈ 

E

 ∖ 

E

′ intersects some edge in

E

′. The

Dominating Induced Matching Problem

(

DIM

, for short) asks for the existence of an induced matching

E

′ which is also dominating in

G

; this problem is also known as the

Efficient Edge Domination

Problem.

The DIM problem is related to parallel resource allocation problems, encoding theory and network routing. It is

$\mathbb{NP}$

-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree three. However, its complexity was open for

P

k

-free graphs for any

k

 ≥ 5;

P

k

denotes a chordless path with

k

vertices and

k

 − 1 edges. We show in this paper that the weighted DIM problem is solvable in linear time for

P

7

-free graphs in a robust way.

The

k

-

Disjoint Paths

problem, which takes as input a graph

G

and

k

pairs of specified vertices (

s

i

,

t

i

), asks whether

G

contains

k

mutually vertex-disjoint paths

P

i

such that

P

i

connects

s

i

and

t

i

, for

i

 = 1,…,

k

. We study a natural variant of this problem, where the vertices of

P

i

must belong to a specified vertex subset

U

i

for

i

 = 1,…,

k

. In contrast to the original problem, which is polynomial-time solvable for any fixed integer

k

, we show that this variant is

NP

-complete even for

k

 = 2. On the positive side, we prove that the problem becomes polynomial-time solvable for any fixed integer

k

if the input graph is chordal. We use this result to show that, for any fixed graph

H

, the problems

H

-

Contractibility

and

H

-

Induced Minor

can be solved in polynomial time on chordal graphs. These problems are to decide whether an input graph

G

contains

H

as a contraction or as an induced minor, respectively.

Polar and monopolar graphs are natural generalizations of bipartite or split graphs. A graph

G

 = (

V

,

E

) is polar if its vertex set admits a partition

V

 = 

A

 ∪ 

B

such that

A

induces a complete multipartite and

B

the complement of a complete multipartite graph. If

A

is even a stable set then

G

is called monopolar.

Recognizing general polar or monopolar graphs is NP-complete and, as yet, efficient recognition is available only for very few graph classes.

This paper considers monopolar and polar graphs that are also planar. On the one hand, we show that recognizing these graphs remains NP-complete, on the other hand we identify subclasses of planar graphs on which polarity and monopolarity can be checked efficiently. The new NP-completeness results cover very restricted graph classes and are sharper than all previous known cases. On the way to the positive results, we develop new techniques for efficient recognition of subclasses of monopolar graphs. These new results extend nearly all known results for efficient monopolar recognition.

In this paper, we study the minimum cost arborescence problem in a directed graph from the viewpoint of robustness of the optimal objective value. More precisely, we characterize an input graph in which the optimal objective value does not change even if we remove several arcs. Our characterizations lead to efficient algorithms for checking robustness of an input graph.

We consider the problem of supporting several different path queries over a tree on

n

nodes, each having a weight drawn from a set of

σ

distinct values, where

σ

 ≤ 

n

. One query we support is the path median query, which asks for the median weight on a path between two given nodes. For this and the more general path selection query, we present a linear space data structure that answers queries in

$O(\lg \sigma)$

time under the word RAM model. This greatly improves previous results on the same problem, as previous data structures achieving

$O(\lg n)$

query time use

$O(n \lg^2 n)$

space, and previous linear space data structures require

O

(

n

ε

) time to answer a query for any positive constant

ε

[16]. Our linear space data structure also supports path counting queries in

$O(\lg \sigma)$

time. This matches the result of Chazelle [8] when

σ

is close to

n

, but has better performance when

σ

is significantly smaller than

n

. Finally, the same data structure can also support path reporting queries in

$O(\lg \sigma + occ \lg \sigma)$

time, where

occ

is the size of output. In addition, we present a data structure that answers path reporting queries in

$O(\lg \sigma + occ \lg\lg\sigma)$

time, using

$O(n\lg\lg\sigma)$

space. These are the first data structures that answer path reporting queries.

Given a set

P

of

n

coloured points on the real line, we study the problem of answering range

α

-majority (or “heavy hitter”) queries on

P

. More specifically, for a query range

Q

, we want to return each colour that is assigned to more than an

α

-fraction of the points contained in

Q

. We present a new data structure for answering range

α

-majority queries on a dynamic set of points, where

α

 ∈ (0,1). Our data structure uses

O

(

n

) space, supports queries in

$O((\lg n) / \alpha)$

time, and updates in

$O((\lg n) / \alpha)$

amortized time. If the coordinates of the points are integers, then the query time can be improved to

$O(\lg n / (\alpha \lg \lg n))$

. For constant values of

α

, this improved query time matches an existing lower bound, for any data structure with polylogarithmic update time. We also generalize our data structure to handle sets of points in

d

-dimensions, for

d

 ≥ 2, as well as dynamic arrays, in which each entry is a colour.

Given a set

S

of

n

points in the plane, we consider the problem of answering range selection queries on

S

: that is, given an arbitrary

x

-range

Q

and an integer

k

 > 0, return the

k

-th smallest

y

-coordinate from the set of points that have

x

-coordinates in

Q

. We present a linear space data structure that maintains a dynamic set of

n

points in the plane with real coordinates, and supports range selection queries in

$O((\lg n / \lg \lg n)^2)$

time, as well as insertions and deletions in

$O((\lg n / \lg \lg n)^2)$

amortized time. The space usage of this data structure is an

$\Theta(\lg n / \lg \lg n)$

factor improvement over the previous best result, while maintaining asymptotically matching query and update times. We also present a succinct data structure that supports range selection queries on a dynamic array of

n

values drawn from a bounded universe.

In this paper we describe a dynamic data structure that answers one-dimensional stabbing-max queries in optimal

O

(log

n

/loglog

n

) time. Our data structure uses linear space and supports insertions and deletions in

O

(log

n

) and

O

(log

n

/loglog

n

) amortized time respectively.

We also describe a

O

(

n

(log

n

/loglog

n

)

d

 − 1

) space data structure that answers

d

-dimensional stabbing-max queries in

O

( (log

n

/loglog

n

)

d

) time. Insertions and deletions are supported in

O

((log

n

/loglog

n

)

d

loglog

n

) and

O

((log

n

/loglog

n

)

d

) amortized time respectively.

We consider the

two-dimensional range maximum query (2D-RMQ)

problem: given an array

A

of ordered values, to pre-process it so that we can find the position of the largest element in a (user-specified) range of rows and range of columns. We focus on determining the

effective

entropy of 2D-RMQ, i.e., how many bits are needed to encode

A

so that 2D-RMQ queries can be answered

without

access to

A

. We give tight upper and lower bounds on the expected effective entropy for the case when

A

contains independent identically-distributed random values, and new upper and lower bounds for arbitrary

A

, for the case when

A

contains few rows. The latter results improve upon upper and lower bounds by Brodal et al. (ESA 2010). We also give some efficient data structures for 2D-RMQ whose space usage is close to the effective entropy.

A random geometric graph (RGG) is defined by placing

n

points uniformly at random in [0,

n

1/

d

]

d

, and joining two points by an edge whenever their Euclidean distance is at most some fixed

r

. We assume that

r

is larger than the critical value for the emergence of a connected component with Ω(

n

) nodes. We show that, with high probability (w.h.p.), for any two connected nodes with a minimum Euclidean distance of

ω

(log

n

), their graph distance is only a constant factor larger than their Euclidean distance. This implies that the diameter of the largest connected component is Θ(

n

1/

d

/

r

) w.h.p.

We also analyze the following randomized broadcast algorithm on RGGs. At the beginning, only one node from the largest connected component of the RGG is informed. Then, in each round, each informed node chooses a neighbor independently and uniformly at random and informs it. We prove that w.h.p. this algorithm informs every node in the largest connected component of an RGG within Θ(

n

1/

d

/

r

 + log

n

) rounds.

We consider the broadcasting problem in heterogeneous tree networks T = (V(T),E(T)) with edge weight uncertainty, where the edge weight w _u,v can take any value from [w−  _u,v ,$w^+_{u,v}$] with unknown distribution. The broadcasting problem with uncertainty is to find a “minmax-regret” broadcast center to minimize the worst-case loss in the objective function that may occur due to the uncertainty. In this paper, we propose an O(n logn loglogn)-time algorithm for the broadcasting problem with uncertainty in heterogeneous tree networks following the postal model.

We study the problem of distributing a file initially located at a server among a set of peers. Peers who downloaded the file can upload it to other peers. The server and the peers are connected to each other via a core network. The upload and download rates to and from the core are constrained by user and server specific upload and download capacities. Our objective is to minimize the makespan. We derive exact polynomial time algorithms for the case when upload and download capacities per peer and among peers are equal. We show that the problem becomes strongly NP-hard for equal upload and download capacities per peer that may differ among peers. For this case we devise a polynomial time

$(1+2\!\sqrt{2})$

-approximation algorithm. To the best of our knowledge, neither NP-hardness nor approximation algorithms were known before for this problem.

A configuration of unit cubes in three dimensions with integer coordinates is called an

animal

if the boundary of their union is homeomorphic to a sphere. Shermer discovered several animals from which no single cube may be removed such that the resulting configurations are also animals [14]. Here we obtain a dual result: we give an example of an animal to which no cube may be added within its minimal bounding box such that the resulting configuration is also an animal. We also present two

O

(

n

)-time algorithms for determining whether a given configuration of

n

unit cubes is an animal.

Given a simple polygon

Q

drawn on a piece of planar material

R

, we cut

Q

out of

R

by a circular saw with a total number of cuts no more than twice the optimal. This improves the previous approximation ratio of 2.5 obtained by Demaine et al.in 2001.

Inspired by video analysis of team sports, we study the following problem. Let

P

be a polygonal path in the plane with

n

vertices. We want to preprocess

P

into a data structure that can quickly count the number of inclusion-minimal subpaths of

P

whose Fréchet Distance to a given query segment

Q

is at most some threshold value

ε

. We present a data structure that solves an approximate version of this problem: it counts all subpaths whose Fréchet Distance is at most

ε

, but this count may also include subpaths whose Fréchet Distance is up to

$(2+3\sqrt{2})\varepsilon $

. For any parameter

n

 ≤ 

s

 ≤ 

n

2

, our data structure can be tuned such that it uses

O

(

s

polylog

n

) storage and has

$O((n/\sqrt{s}){\rm polylog} n)$

query time. For the special case where we wish to count all subpaths whose Fréchet Distance to

Q

is at most

ε

·

length

(

Q

), we present a structure with

O

(

n

polylog

n

) storage and

O

(polylog

n

) query time.

We introduce a new variant of the geometric Steiner arborescence problem, motivated by the layout of flow maps. Flow maps show the movement of objects between places. They reduce visual clutter by bundling lines smoothly and avoiding self-intersections. To capture these properties, our

angle-restricted Steiner arborescences

, or

flux trees

, connect several targets to a source with a tree of minimal length whose arcs obey a certain restriction on the angle they form with the source.

We study the properties of optimal flux trees and show that they are planar and consist of logarithmic spirals and straight lines. Flux trees have the

shallow-light property

. Computing optimal flux trees is NP-hard. Hence we consider a variant of flux trees which uses only logarithmic spirals.

Spiral trees

approximate flux trees within a factor depending on the angle restriction. Computing optimal spiral trees remains NP-hard, but we present an efficient 2-approximation, which can be extended to avoid “positive monotone” obstacles.

Treemaps are a popular technique to visualize hierarchical data. The input is a weighted tree

$\mathcal T$

where the weight of each node is the sum of the weights of its children. A treemap for

$\mathcal T$

is a hierarchical partition of a rectangle into simply connected regions, usually rectangles. Each region represents a node of

$\mathcal T$

and its area is proportional to the weight of the corresponding node. An important quality criterion for treemaps is the aspect ratio of its regions. One cannot bound the aspect ratio if the regions are restricted to be rectangles. In contrast,

polygonal partitions

, that use convex polygons, can have bounded aspect ratio. We are the first to obtain convex partitions with optimal aspect ratio

$O(depth(\mathcal T))$

. However,

$depth(\mathcal T)$

still depends on the input tree. Hence we introduce a new type of treemaps, namely

orthoconvex treemaps

, where regions representing leaves are rectangles, L-, and S-shapes, and regions representing internal nodes are orthoconvex polygons. We prove that any input tree, irrespective of the weights of the nodes and the depth of the tree, admits an orthoconvex treemap of constant aspect ratio.

Given

k

planar graphs

G

1

,…,

G

k

, deciding whether they admit a simultaneous embedding with fixed edges (

Sefe

) and whether they admit a simultaneous geometric embedding (

Sge

) are NP-hard problems, for

k

 ≥ 3 and for

k

 ≥ 2, respectively. In this paper we consider the complexity of

Sefe

and of

Sge

when the graphs

G

1

,…,

G

k

have a fixed planar embedding. In sharp contrast with the NP-hardness of

Sefe

for three non-embedded graphs, we show that

Sefe

is polynomial-time solvable for three graphs with a fixed planar embedding. Furthermore, we show that, given

k

embedded planar graphs

G

1

,…,

G

k

, deciding whether a

Sefe

of

G

1

,…,

G

k

exists and deciding whether an

Sge

of

G

1

,…,

G

k

exists are NP-hard problems, for

k

 ≥ 14 and

k

 ≥ 13, respectively.

In a proportional contact representation of a planar graph, each vertex is represented by a simple polygon with area proportional to a given weight, and edges are represented by adjacencies between the corresponding pairs of polygons. In this paper we study proportional contact representations that use rectilinear polygons without wasted areas (white space). In this setting, the best known algorithm for proportional contact representation of a maximal planar graph uses 12-sided rectilinear polygons and takes

O

(

n

log

n

) time. We describe a new algorithm that guarantees 10-sided rectilinear polygons and runs in

O

(

n

) time. We also describe a linear-time algorithm for proportional contact representation of planar 3-trees with 8-sided rectilinear polygons and show that this is optimal, as there exist planar 3-trees that require 8-sided polygons. Finally, we show that a maximal outer-planar graph admits a proportional contact representation using rectilinear polygons with 6 sides when the outer-boundary is a rectangle and with 4 sides otherwise.

We describe fully retroactive dynamic data structures for approximate range reporting and approximate nearest neighbor reporting. We show how to maintain, for any positive constant

d

, a set of

n

points in ℝ

d

indexed by time such that we can perform insertions or deletions at any point in the timeline in

O

(log

n

) amortized time. We support, for any small constant

ε

 > 0, (1 + 

ε

)-approximate range reporting queries at any point in the timeline in

O

(log

n

 + 

k

) time, where

k

is the output size. We also show how to answer (1 + 

ε

)-approximate nearest neighbor queries for any point in the past or present in

O

(log

n

) time.

We give a data structure for storing an

n

-element poset of width

w

in essentially minimal space. We then show how this data structure supports the most interesting queries on posets in either constant time, or in time that depends only on

w

and the size of the in-/output, but not on

n

. Our results also have direct applicability to DAGs of low width.

We consider the problem of designing space efficient solutions for representing triangle meshes. Our main result is a new explicit data structure for compactly representing planar triangulations: if one is allowed to permute input vertices, then a triangulation with

n

vertices requires at most 4

n

references (5

n

references if vertex permutations are not allowed). Our solution combines existing techniques from mesh encoding with a novel use of minimal Schnyder woods. Our approach extends to higher genus triangulations and could be applied to other families of meshes (such as quadrangular or polygonal meshes). As far as we know, our solution provides the most parsimonious data structures for triangulations, allowing constant time navigation in the worst case. Our data structures require linear construction time, and all space bounds hold in the worst case. We have implemented and tested our results, and experiments confirm the practical interest of compact data structures.

We consider various data-analysis queries on two-dimensional points. We give new space/time tradeoffs over previous work on semigroup and group queries such as sum, average, variance, minimum and maximum. We also introduce new solutions to queries rarely considered in the literature such as two-dimensional quantiles, majorities, successor/predecessor and mode queries. We face static and dynamic scenarios.

In the

k

-Feedback Arc/Vertex Set

problem we are given a directed graph

D

and a positive integer

k

and the objective is to check whether it is possible to delete at most

k

arcs/vertices from

D

to make it acyclic. Dom et al.[

CIAC, 2006

] initiated a study of the

Feedback Arc Set

problem on bipartite tournaments (

k

-FASBT

) in the realm of parameterized complexity. They showed that

k

-FASBT

can be solved in time

O

(3.373

k

n

6

) on bipartite tournaments having

n

vertices. However, until now there was no known polynomial sized problem kernel for

k

-FASBT

. In this paper we obtain a cubic vertex kernel for

k

-FASBT

. This completes the kernelization picture for the

Feedback Arc/Vertex Set

problem on tournaments and bipartite tournaments, as for all other problems polynomial kernels were known before. We obtain our kernel using a non-trivial application of “independent modules” which could be of independent interest.

Let

G

be an

n

-node bipartite tournament, i.e., a complete bipartite graph, each of whose edges has an orientation. We address the fixed-parameter complexity of the NP-complete problem of determining, for any given parameter

k

, whether

G

admits a

k

-node subset whose removal from

G

yields an acyclic graph. The best previously known upper bound, due to Sasatte, is

$O(3^k\cdot \mbox{poly}(n))$

. In this paper, we show that the fixed-parameter complexity is

$O(2^k\cdot\mbox{poly}(n))$

.

A

linear matching

consists of 2

n

vertices ordered linearly, together with

n

vertex-disjoint edges. In this article, we study the

Linear Matching Inclusion

problem, which takes two linear matchings, called the

pattern

and the

target

, and asks if there is an order-preserving mapping of the pattern into the target. We consider several parameterizations of this problem, for which we obtain parameterized algorithms and hardness results. In addition, we settle the parameterized complexity of the related

Nesting-Free 2-Interval Pattern

problem.

Bidimensionality theory provides a general framework for developing subexponential fixed parameter algorithms for NP-hard problems. In this framework, to solve an optimization problem in a graph

G

, the branchwidth

${\mathop{\rm bw}}(G)$

is first computed or estimated. If

${\mathop{\rm bw}}(G)$

is small then the problem is solved by a branch-decomposition based algorithm which typically runs in polynomial time in the size of

G

but in exponential time in

${\mathop{\rm bw}}(G)$

. Otherwise, a large

${\mathop{\rm bw}}(G)$

implies a large grid minor of

G

and the problem is computed or estimated based on the grid minor. A representative example of such algorithms is the one for the longest path problem in planar graphs. Although many subexponential fixed parameter algorithms have been developed based on bidimensionality theory, little is known on the practical performance of these algorithms. We report a computational study on the practical performance of a bidimensionality theory based algorithm for the longest path problem in planar graphs. The results show that the algorithm is practical for computing/estimating the longest path in a planar graph. The tools developed and data obtained in this study may be useful in other bidimensional algorithm studies.

We study the MapReduce framework from an algorithmic standpoint, providing a generalization of the previous algorithmic models for MapReduce. We present optimal solutions for the fundamental problems of all-prefix-sums, sorting and multi-searching. Additionally, we design optimal simulations of the the well-established PRAM and BSP models in MapReduce, immediately resulting in optimal solutions to the problems of computing fixed-dimensional linear programming and 2-D and 3-D convex hulls.

Many data structures support dictionaries, also known as maps or associative arrays, which store and manage a set of key-value pairs. A

multimap

is a generalization that allows multiple values to be associated with the same key. For example, the inverted file data structure commonly used in search engines is a type of multimap, with words as keys and document pointers as values. We study the multimap abstract data type and how it can be implemented efficiently online in external memory frameworks, with constant expected I/O performance. The key technique used to achieve our results is a combination of cuckoo hashing using buckets that hold multiple items with a multiqueue implementation to cope with varying numbers of values per key. Our results are provably optimal up to constant factors.

In this paper we describe data structures for orthogonal range reporting in external memory that support fast update operations. The query costs either match the query costs of the best previously known data structures or differ by a small multiplicative factor.

Evolutionary algorithms are popular heuristics for solving various combinatorial problems as they are easy to apply and often produce good results. Island models parallelize evolution by using different populations, called islands, which are connected by a graph structure as communication topology. Each island periodically communicates copies of good solutions to neighboring islands in a process called migration. We consider the speedup gained by island models in terms of the parallel running time for problems from combinatorial optimization: sorting (as maximization of sortedness), shortest paths, and Eulerian cycles. Different search operators are considered. The results show in which settings and up to what degree evolutionary algorithms can be parallelized efficiently. Along the way, we also investigate how island models deal with plateaus. In particular, we show that natural settings lead to exponential vs. logarithmic speedups, depending on the frequency of migration.

J. Hopcroft and D. Sheldon originally introduced the PageRank game to investigate the self-interested behavior of web authors who want to boost their PageRank by using game theoretical approaches. The PageRank game is a multiplayer game where players are the nodes in a directed web graph and they place their outlinks to maximize their PageRank value. They give best response strategies for each player and characterize properties of

α

-insensitive Nash equilibria. In this paper we consider PageRank games for undirected web graphs, where players are free to delete any of their bidirectional links if they wish. We study the problem of determining whether the given graph represents a Nash equilibrium or not. We give an

O

(

n

2

) time algorithm for a tree, and a parametric

O

(2

k

n

4

) time algorithm for general graphs, where

k

is the maximum vertex degree in any biconnected component of the graph.

We consider the interactive model of collaborative filtering, where each member of a given set of users has a grade for each object in a given set of objects. The users do not know the grades at start, but a user can

probe

any object, thereby learning her grade for that object directly. We describe reconstruction algorithms which generate good estimates of all user grades (“preference vectors”) using only few probes. To this end, the outcomes of probes are posted on some public “billboard”, allowing users to adopt results of probes executed by others. We give two new algorithms for this task under very general assumptions on user preferences: both improve the best known query complexity for reconstruction, and one improving resilience in the presence of many users with esoteric taste.

Modularity has been introduced as a quality measure for graph partitioning. It has received considerable attention in several disciplines, especially complex systems. In order to better understand this measure from a graph theoretical point of view, we study the modularity of a variety of graph classes. We first consider simple graph classes such as tori and hypercubes. We show that these regular graph families have asymptotic modularity 1 (that is the maximum possible). We extend this result to the general class of unit ball graphs of bounded growth metrics. Our most striking result concerns trees with bounded degree which also appear to have asymptotic modularity 1. This last result can be extended to graphs with constant average degree and to some power-law graphs.

Winfree’s abstract Tile Assembly Model (aTAM) is a model of molecular self-assembly of DNA complexes known as tiles, which float freely in solution and attach one at a time to a growing “seed” assembly based on specific binding sites on their four sides. We show that there is a polynomial-time algorithm that, given an

n

×

n

square, finds the minimal tile system (i.e., the system with the smallest number of distinct tile types) that uniquely self-assembles the square, answering an open question of Adleman, Cheng, Goel, Huang, Kempe, Moisset de Espanés, and Rothemund (

Combinatorial Optimization Problems in Self-Assembly

, STOC 2002). Our investigation leading to this algorithm reveals other positive and negative results about the relationship between the size of a tile system and its “temperature” (the binding strength threshold required for a tile to attach)

We give a unified treatment to optimization problems that can be expressed in the form of nonnegative-real-weighted Boolean constraint satisfaction problems. Creignou, Khanna, Sudan, Trevisan, and Williamson studied the complexity of approximating their optimal solutions whose optimality is measured by the sums of outcomes of constraints. To explore a wider range of optimization constraint satisfaction problems, following an early work of Marchetti-Spaccamela and Romano, we study the case where the optimality is measured by products of constraints’ outcomes. We completely classify those problems into three categories: PO problems, NPO-hard problems, and intermediate problems that lie between the former two categories. To prove this trichotomy theorem, we analyze characteristics of nonnegative-real-weighted constraints using a variant of the notion of T-constructibility developed earlier for complex-weighted counting constraint satisfaction problems.

The paper is devoted to lower bounds on the time complexity of DPLL algorithms that solve the satisfiability problem using a splitting strategy. Exponential lower bounds on the running time of DPLL algorithms on unsatisfiable formulas follow from the lower bounds for resolution proofs. Lower bounds on satisfiable instances are also known for some classes of DPLL algorithms; this lower bounds are usually based on reductions to unsatisfiable instances. In this paper we consider DPLL algorithms with a cut heuristic that may decide that some branch of the splitting tree will not be investigated. DPLL algorithms with a cut heuristic always return correct answer on unsatisfiable formulas while they may err on satisfiable instances. We prove the theorem about effectiveness vs. correctness trade-off for deterministic myopic DPLL algorithms with cut heuristic. Myopic algorithms can see formulas with erased signs of negations; they may also request a small number of clauses to read them precisely.

We construct a family of unsatisfiable formulas Φ

(

n

)

and a polynomial time samplable ensemble of distributions

Q

n

concentrated on satisfiable formulas such that every deterministic myopic algorithm that gives a correct answer with probability 1 − 

o

(1) on a random formula from the ensemble

Q

n

runs exponential time on the formulas Φ

(

n

)

.

This paper deals with a single allocation problem in hub-and-spoke networks. We handle the case that all the nodes are embedded in a 2-dimensional plane and a transportation cost (per unit flow) is proportional to Euclidean distance. We propose a randomized (1 + 2/

π

)-approximation algorithm based on a linear relaxation problem and a dependent rounding procedure.

We present a packing-based approximation algorithm for the

k

-Set Cover problem. We introduce a new local search-based

k

-set packing heuristic, and call it Restricted

k

-Set Packing. We analyze its tight approximation ratio via a complicated combinatorial argument. Equipped with the Restricted

k

-Set Packing algorithm, our

k

-Set Cover algorithm is composed of the

k

-Set Packing heuristic [8] for

k

 ≥ 7, Restricted

k

-Set Packing for

k

 = 6,5,4 and the semi-local (2,1)-improvement [2] for 3-Set Cover. We show that our algorithm obtains a tight approximation ratio of

$H_k-0.6402+\Theta(\frac{1}{k})$

, where

H

k

is the

k

-th harmonic number. For small

k

, our results are 1.8667 for

k

 = 6, 1.7333 for

k

 = 5 and 1.5208 for

k

 = 4. Our algorithm improves the currently best approximation ratio for the

k

-Set Cover problem of any

k

 ≥ 4.

We consider the capacitated domination problem, which models a service-requirement assigning scenario and which is also a generalization of the dominating set problem. In this problem, we are given a graph with three parameters defined on the vertex set, which are cost, capacity, and demand. The objective of this problem is to compute a demand assignment of least cost, such that the demand of each vertex is fully-assigned to some of its closed neighbours without exceeding the amount of capacity they provide. In this paper, we provide the first constant factor approximation for this problem on planar graphs, based on a new perspective on the hierarchical structure of outer-planar graphs. We believe that this new perspective and technique can be applied to other capacitated covering problems to help tackle vertices of large degrees.

The view size estimation plays an important role in query optimization. It has been observed that many data follow a power law distribution. In this paper, we consider the balls in bins problem where we place balls into

N

bins when the bin selection probabilities follow a power law distribution. As a generalization to the coupon collector’s problem, we address the problem of determining the expected number of balls that need to be thrown in order to have at least one ball in each of the

N

bins. We prove that

$\Theta(\frac{N^\alpha \ln N}{c_N^{\alpha}})$

balls are needed to achieve this where

α

is the parameter of the power law distribution and

$c_N^{\alpha}=\frac{\alpha-1}{\alpha-N^{\alpha-1}}$

for

α

 ≠ 1 and

$c_N^{\alpha}=\frac{1}{\ln N}$

for

α

 = 1. Next, when fixing the number of balls that are thrown to

T

, we provide closed form upper and lower bounds on the expected number of bins that have at least one occupant. For

n

large and

α

 > 1, we prove that our bounds are tight up to a constant factor of

$\left(\frac{\alpha}{\alpha-1}\right)^{1-\frac{1}{\alpha}} \leq e^{1/e} \simeq 1.4$

.

Finding frequent items in a data stream is a fundamental problem; Given a threshold

θ

 ∈ (0,1), find items appearing more than

$\theta \cdotp N$

times in an input

stream

with length

N

. Karp, Shenker, Papadimiriou (2003) gave a simple deterministic online algorithm, which allows false positive outputs using memory of O(

θ

− 1

log

N

)

bits

, while they also gave a lower bound. Motivated by the theoretical bound of the space complexity, this paper proposes a simple randomized online algorithm using memory of O(

θ

− 2

log

2

θ

− 1

 + loglog

N

) bits where parameters for approximation are hidden in the constant. Our algorithm is

robust

for memory overflow, compared with other naïve randomized algorithms, or deterministic algorithms using memory of O(log

N

) bits. We also give some randomized algorithms for approximate counting.

We show that for all integers

t

 ≥ 8 and arbitrarily small

ε

 > 0, there exists a graph property Π (which depends on

ε

) such that

ε

-testing Π has non-adaptive query complexity

$Q=\tilde\Theta(q^{2-2/t})$

, where

$q=\tilde\Theta(\epsilon^{-1})$

is the adaptive query complexity. This resolves the question of how beneficial adaptivity is, in the context of proximity-dependent properties. This also gives evidence that the canonical transformation of Goldreich and Trevisan is essentially optimal when converting an adaptive property tester to a non-adaptive property tester.

To do so, we provide optimal adaptive and non-adaptive testers for the combined property of having maximum degree

O

(

εN

) and being a

blow-up collection

of an arbitrary base graph

H

.

This paper proposes an algorithm for

online linear optimization problem over permutations

; the objective of the online algorithm is to find a permutation of {1,…,

n

} at each trial so as to minimize the “regret” for

T

trials. The regret of our algorithm is

$O(n^2 \sqrt{T \ln n})$

in expectation for any input sequence. A naive implementation requires more than exponential time. On the other hand, our algorithm uses only

O

(

n

) space and runs in

O

(

n

2

) time in each trial. To achieve this complexity, we devise two efficient algorithms as subroutines: One is for minimization of an entropy function over the

permutahedron

P

n

, and the other is for randomized rounding over

P

n

.

The multislope ski-rental problem [11] is an extension of the classical ski-rental problem [10], where the player has several

lease

options in addition to the pure

rent

and

buy

options. In this problem an

instance

, which is the setting of the options, significantly affects the player’s performance. There is an algorithm that for a given instance, computes the best possible strategy [1]. However, the output is given in numerical values and the relational nature between the instance and the best possible performance has not been known. In this paper we prove that even for the easiest instance, a competitive ratio smaller than

e

/(

e

 − 1) ≈ 1.58 cannot be achieved. More precisely, according to the number of options, tight bounds are obtained in a closed form. Furthermore, we establish a matching upper and lower bound of the competitive ratio each for the 3-slope and 4-slope problems.

We study the complexity of one-dimensional extrema testing: given one input number, determine if it is properly contained in the interval spanned by the remaining

n

input numbers. We assume that each number is given as a finite stream of bits, in decreasing order of significance. Our cost measure, referred to as the

leading-input-bits-cost

(or LIB-cost for short), for an algorithm solving such a problem is the total number of bits that it needs to consume from its input streams.

An

input-thrifty algorithm

is one that performs favorably with respect to this LIB-cost measure. A fundamental goal in the design of such algorithms is to be more efficient on “easier” input instances, ideally approaching the minimum number of input bits needed to certify the solution, on all orderings of all input instances.

In this paper we present an input-thrifty algorithm for extrema-testing that is log-competitive in the following sense: if the best possible algorithm for a particular problem instance, including algorithms that are only required to be correct for presentations of this one instance, has worst-case (over all possible input presentations) LIB-cost

c

, then our algorithm has worst-case LIB-cost

$O(c\lg \min\{c, n\})$

.

In fact, our algorithm achieves something considerably stronger: if any input sequence (i.e. an arbitrary presentation of an arbitrary input set) can be tested by a monotonic algorithm (an algorithm that preferentially explores lower indexed input streams) with LIB-cost

c

, then our algorithm has LIB-cost

$O(c\lg \min\{c, n\})$

. Since, as we demonstrate, the cost profile of any algorithm can be matched by that of a monotonic algorithm, it follows that our algorithm is to within a log factor of optimality at the level of input sequences. We also argue that this log factor cannot be reduced, even for algorithms that are only required to be correct on input sequences with some fixed intrinsic monotonic LIB-cost

c

.

The extrema testing problem can be cast as a kind of list-searching problem, and our algorithm employs a variation of a technique called

hyperbolic sweep

that was introduced in that context. Viewed in this light, our results can be interpreted as another variant of the well-studied cow-path problem, with applications in the design of hybrid algorithms.

Given a stream of items each associated with a numerical value, its edit distance to monotonicity is the minimum number of items to remove so that the remaining items are non-decreasing with respect to the numerical value. The space complexity of estimating the edit distance to monotonicity of a data stream is becoming well-understood over the past few years. Motivated by applications on network quality monitoring, we extend the study to estimating the edit distance to monotonicity of a sliding window covering the

w

most recent items in the stream for any

w

 ≥ 1. We give a deterministic algorithm which can return an estimate within a factor of (4 + 

ε

) using

$O(\frac{1}{\epsilon ^2} \log^2(\epsilon w))$

space.

We also extend the study in two directions. First, we consider a stream where each item is associated with a value from a partial ordered set. We give a randomized (4 + 

ε

)-approximate algorithm using

$O(\frac{1}{\epsilon^2} \log \epsilon^2 w \log w)$

space. Second, we consider an out-of-order stream where each item is associated with a creation time and a numerical value, and items may be out of order with respect to their creation times. The goal is to estimate the edit distance to monotonicity with respect to the numerical value of items arranged in the order of creation times. We show that any randomized constant-approximate algorithm requires linear space.

We consider two types of folding applied to

equilateral

plane graph linkages. First, under continuous folding motions, we show how to reconfigure any

linear

equilateral tree (lying on a line) into a canonical configuration. By contrast, such reconfiguration is known to be impossible for linear (nonequilateral) trees and for (nonlinear) equilateral trees. Second, under instantaneous folding motions, we show that an equilateral plane graph has a noncrossing linear folded state if and only if it is bipartite. Not only is the equilateral constraint necessary for this result, but we show that it is strongly NP-complete to decide whether a (nonequilateral) plane graph has a linear folded state. Equivalently, we show strong NP-completeness of deciding whether an abstract metric polyhedral complex with one central vertex has a noncrossing flat folded state with a specified “outside region”. By contrast, the analogous problem for a polyhedral manifold with one central vertex (

single-vertex origami

) is only weakly NP-complete.

We present

$O(\min\{n\log^{1.5} n, n\log n+k^2\log^2\frac{n}{k}\log^2 n\})$

time algorithms for the weighted

k

-problem on a real line. Previously, the best known algorithms for this problem take

O

(

n

log

2

n

) time, or

O

(

kn

log

n

) time, or a time linear in

n

but exponential in

k

. Our techniques involve developing efficient data structures for processing queries that find a lowest point in the common intersection of a certain subset of half-planes. This subproblem is interesting in its own right.

In this paper, we consider a generalized problem formulation of computing a functional curve to approximate a point set in the plane with outliers. The goal is to seek a solution that not only optimizes its original objectives, but also somehow accommodates the impact of the outliers. Based on a new model of accommodating outliers, we present efficient geometric algorithms for various versions of this problem (e.g., the approximating functions are step functions or piecewise linear functions, the points are unweighted or weighted, etc). All our results are first known. Our new model and techniques for handling outliers may be useful to other applications as well.

We study the problem of reconstructing a simple polygon: Given a cyclically ordered vertex sequence of an unknown simple polygon

P

of

n

vertices and, for each vertex

v

of

P

, the sequence of angles defined by all the visible vertices of

v

in

P

, reconstruct the polygon

P

(up to similarity). An

O

(

n

3

log

n

) time algorithm has been proposed for this problem. We present an improved algorithm with running time

O

(

n

2

), based on new observations on the geometric structures of the problem. Since the input size (i.e., the total number of input visibility angles) is Θ(

n

2

) in the worst case, our algorithm is worst-case optimal.

We extend previous work on the parameterized complexity of local search for the Travelling Salesperson Problem (TSP). So far, its parameterized complexity has been investigated with respect to the distance measures (which define the local search area) “Edge Exchange” and “Max-Shift”. We perform studies with respect to the distance measures “Swap” and “

m

-Swap”, “Reversal” and “

m

-Reversal”, and “Edit”, achieving both fixed-parameter tractability and

W[1]

-hardness results. Moreover, we provide non-existence results for polynomial-size problem kernels and we show that some in general

W[1]

-hard problems turn fixed-parameter tractable when restricted to planar graphs.

Given a collection

${\mathcal{C}}$

of partitions of a base set

S

, the NP-hard

Consensus Clustering

problem asks for a partition of

S

which has a total Mirkin distance of at most

t

to the partitions in

${\mathcal{C}}$

, where

t

is a nonnegative integer. We present a parameterized algorithm for

Consensus Clustering

with running time

$O(4.24^k\cdot k^3+|{\mathcal C}|\cdot |S|^2)$

, where

$k:=t/|{\mathcal{C}}|$

is the average Mirkin distance of the solution partition to the partitions of

${\mathcal{C}}$

. Furthermore, we strengthen previous hardness results for

Consensus Clustering

, showing that

Consensus Clustering

remains NP-hard even when all input partitions contain at most two subsets. Finally, we study a local search variant of

Consensus Clustering

, showing W[1]-hardness for the parameter “radius of the Mirkin-distance neighborhood”. In the process, we also consider a local search variant of the related

Cluster Editing

problem, showing W[1]-hardness for the parameter “radius of the edge modification neighborhood”.

A (

k

,ℓ)-cocoloring of a graph

G

is a partition of the vertex set of

G

into at most

k

independent sets and at most ℓ cliques. Given a graph

G

and integers

k

and ℓ, the

Cocoloring Problem

is the problem of deciding if

G

has a (

k

,ℓ)-cocoloring. It is known that determining the cochromatic number (the minimum

k

 + ℓ such that

G

is (

k

,ℓ)-cocolorable) is NP-hard [24]. In 2011, Bravo et al. obtained a polynomial time algorithm for

P

4

-sparse graphs [8]. In this paper, we generalize this result by obtaining a polynomial time algorithm for (

q

,

q

 − 4)-graphs for every fixed

q

, which are the graphs such that every subset of at most

q

vertices induces at most

q

 − 4 induced

P

4

’s.

P

4

-sparse graphs are (5,1)-graphs. Moreover, we prove that the cocoloring problem is FPT when parameterized by the treewidth

tw

(

G

) or by the parameter

q

(

G

), defined as the minimum integer

q

 ≥ 4 such that

G

is a (

q

,

q

 − 4)-graph.

In this paper we study the parameterized complexity of the firefighter problem. More precisely, we show that

Saving

k

-Vertices

and its dual

Saving All But

k

-Vertices

are both W[1]-hard for parameter

k

even for bipartite graphs. We also investigate several cases for which the firefighter problem is tractable. For instance,

Saving

k

-Vertices

is fixed-parameter tractable on planar graphs for parameter

k

. Moreover, we prove a lower bound to polynomial kernelization for

Saving All But

k

-Vertices

.

Motivated by the imminent growth of massive, highly redundant genomic databases we study the problem of compressing a string database while simultaneously supporting fast random access, substring extraction and pattern matching to the underlying string(s).

Bille et al. (2011) recently showed how, given a straight-line program with

r

rules for a string

s

of length

n

, we can build an

$\ensuremath{\mathcal{O}\!\left( {r} \right)}$

-word data structure that allows us to extract any substring

s

[

i

..

j

] in

$\ensuremath{\mathcal{O}\!\left( {\log n + j - i} \right)}$

time. They also showed how, given a pattern

p

of length

m

and an edit distance

k

 ≤ 

m

, their data structure supports finding all

occ

approximate matches to

p

in

s

in

$\ensuremath{\mathcal{O}\!\left( {r (\min (m k, k^4 + m) + \log n) + \ensuremath{\mathsf{occ}}} \right)}$

time. Rytter (2003) and Charikar et al. (2005) showed that

r

is always at least the number

z

of phrases in the LZ77 parse of

s

, and gave algorithms for building straight-line programs with

$\ensuremath{\mathcal{O}\!\left( {z \log n} \right)}$

rules. In this paper we give a simple

$\ensuremath{\mathcal{O}\!\left( {z \log n} \right)}$

-word data structure that takes the same time for substring extraction but only

$\ensuremath{\mathcal{O}\!\left( {z (\min (m k, k^4 + m)) + \ensuremath{\mathsf{occ}}} \right)}$

time for approximate pattern matching.

Given two strings

S

and

T

, together with an integer representing the similarity bound, the characteristic string problem consists in finding the shortest substrings of

T

such that

S

has no substrings similar to them, in the sense that one string is similar to another if the amount of ‘dissimilarities’ between them is less than or equal to the similarity bound. Under the similarity criterion that uses Levenshtain distance to measure the amount of dissimilarities between two strings, this problem is known to be solvable in cubic time and linear space. The present article proposes a new algorithm for this problem that performs in almost quadratic time and almost linear space, under a certain class of similarity criteria, including the similarity criterion based on Levenshtain distance.

Circular patterns are those patterns whose circular permutations are also valid patterns. These patterns arise naturally in bioinformatics and computational geometry. In this paper, we consider succinct indexing schemes for a set of

d

circular patterns of total length

n

, with each character drawn from an alphabet of size

σ

. Our method is by defining the popular Burrows-Wheeler transform (BWT) on circular patterns, based on which we achieve succinct indexes with space

n

log

σ

(1 + 

o

(1)) + 

O

(

n

) + 

O

(

d

log

n

) bits, while pattern matching or dictionary matching queries can be supported efficiently.

In this paper, we define the

Range LCP

problem as follows. Preprocess a string

S

, of length

n

, to enable efficient solutions of the following query:

Given

$[i,j],\ \ 0< i \leq j \leq n$

, compute max

ℓ,

k

 ∈ {

i

,…,

j

}

LCP

(

S

ℓ

,

S

k

), where

LCP

(

S

ℓ

,

S

k

) is the length of the longest common prefix of the suffixes of

S

starting at locations ℓ and

k

. This is a natural generalization of the classical LCP problem.

Surprisingly, while it is known how to preprocess a string in linear time to enable LCP computation of two suffixes in constant time, this seems quite difficult in the

Range LCP

problem. It is trivial to answer such queries in time

O

(|

j

 − 

i

|

2

) after a linear-time preprocessing and easy to show an

O

(1) query algorithm after an

O

(|

S

|

2

) time preprocessing. We provide algorithms that solve the problem with the following complexities:

1

Preprocessing Time:

O

(|

S

|),

Space:

O

(|

S

|),

Query Time:

O

(|

j

 − 

i

|loglog

n

).

2

Preprocessing Time:

no preprocessing,

Space:

O

(|

j

 − 

i

|log|

j

 − 

i

|),

Query Time:

O

(|

j

 − 

i

|log|

j

 − 

i

|). However, the query just gives the pairs with the longest LCP,

not

the LCP itself.

3

Preprocessing Time:

O

(|

S

|log

2

|

S

|),

Space:

O

(|

S

|log

1 + 

ε

|

S

|) for arbitrary small constant

ε

,

Query Time:

O

(loglog|

S

|).

In this paper, we study the robustness over the cardinality variation for the knapsack problem. For the knapsack problem and a positive number

α

 ≤ 1, we say that a feasible solution is

α-robust

if, for any positive integer

k

, it includes an

α

-approximation of the maximum

k

-knapsack solution, where a

k

-knapsack solution is a feasible solution that consists of at most

k

items.

In this paper, we show that, for any

ε

 > 0, the problem of deciding whether the knapsack problem admits a (

ν

 + 

ε

)-robust solution is weakly NP-hard, where

ν

denotes the rank quotient of the corresponding knapsack system. Since the knapsack problem always admits a

ν

-robust knapsack solution [7], this result provides a sharp border for the complexity of the robust knapsack problem. On the positive side, we show that a max-robust knapsack solution can be computed in pseudo-polynomial time, and present a fully polynomial time approximation scheme (FPTAS) for computing a max-robust knapsack solution.

We define a variant of

k

-of-

n

testing that we call

conservative

k

-of-

n

testing. We present a polynomial-time, combinatorial algorithm for maximizing the throughput of conservative

k

-of-

n

testing, in a parallel setting. This extends previous work of Kodialam and Condon et al. on the parallel pipelined filter ordering problem, which is the special case where

k

 = 1 (or

k

 = 

n

) [1,2,3]. We also consider the problem of maximizing throughput for

standard

k

-of-

n

testing, and describe a polynomial-time algorithm for it based on the ellipsoid method.

The problem of finding the period of a vector

V

is central to many applications. Let

V

′ be a periodic vector closest to

V

under some metric. We seek this

V

′, or more precisely we seek the smallest period that generates

V

′. In this paper we consider the problem of finding the closest periodic vector in

L

p

spaces. The measures of “closeness” that we consider are the metrics in the different

L

p

spaces. Specifically, we consider the

L

1

,

L

2

and

L

 ∞ 

metrics. In particular, for a given

n

-dimensional vector

V

, we develop

O

(

n

2

) time algorithms (a different algorithm for each metric) that construct the smallest period that defines such a periodic

n

-dimensional vector

V

′. We call that vector the

closest periodic vector

of

V

under the appropriate metric. We also show (three)

O

(

n

log

n

) time constant approximation algorithms for the (appropriate) period of the closest periodic vector.

We consider an optimization version of the image segmentation problem, in which we are given a grid graph with weights on the grid cells. We are interested in finding the maximum weight subgraph such that the subgraph can be decomposed into two ”star-shaped” images. We show that this problem can be reduced to the problem of finding a maximum-weight closed set in an appropriately defined directed graph which is well known to have efficient algorithms which run very fast in practice. We also show that finding a maximum-weight subgraph that is decomposable into

m

star-shaped objects is NP-hard for some

m

 > 2.

In this paper, we propose to study the famous

maximum sum segment

problem on a sequence consisting of

n

uncertain numbers, where each number is given as an interval characterizing its possible value. Given two integers

L

and

U

, a segment of length between

L

and

U

is called a

potential maximum sum segment

if there exists a possible assignment of the uncertain numbers such that, under the assignment, the segment has maximum sum over all segments of length between

L

and

U

. We define the

maximum sum segment with uncertainty

problem, which consists of two sub-problems: (1) reporting all potential maximum sum segments; (2) counting the total number of those segments. For

L

 = 1 and

U

 = 

n

, we propose an

O

(

n

 + 

K

)-time algorithm and an

O

(

n

)-time algorithm, respectively, where

K

is the number of potential maximum sum segments. For general

L

and

U

, we give an

O

(

n

(

U

 − 

L

))-time algorithm for either problem.

A MUL-tree is a generalization of a phylogenetic tree that allows the same leaf label to be used many times. Lott

et al.

[9,10] recently introduced the problem of inferring a so-called

consensus MUL-tree

from a set of conflicting MUL-trees and gave an exponential-time algorithm for a special greedy variant. Here, we study

strict

and

majority rule consensus MUL-trees

, and present the first ever polynomial-time algorithms for building a consensus MUL-tree. We give a simple, fast algorithm for building a strict consensus MUL-tree. We also show that although it is NP-hard to find a majority rule consensus MUL-tree, the variant which we call the

singular majority rule consensus MUL-tree

is unique and can be constructed efficiently.

The combinatorial group testing problem is concerned with the design of experiments so as to minimize the number of tests needed to find the sets of items responsible for a particular phenotype (an observable property). The traditional group testing problem only considers the OR problem, i.e. the phenotype appears as long as one of the responsible items exists. In this paper, we introduce the phenotype testing problem which is a generalization of the well-studied combinatorial group testing problem. In practice, there are more than one phenotype and the responsible items and their mechanism (AND or OR) for each phenotype are unknown where an AND mechanism means that the phenotype only appears if all of the responsible items exist.

This phenotype testing problem has an important application in biological research, known as phenotype knockout study. New algorithms for designing adaptive experiments for solving the phenotype testing problem with

n

items using

O

(log

n

) tests in the worst cases are introduced. When the number of phenotypes is small, say at most 2, and the number of responsible items for each phenotype is at most 2, algorithms with near-optimal number of tests are presented.

In this paper, we introduce an index structure of texts which supports fast search of patterns with “don’t care”s in predetermined positions. This data structure is a generalization of the suffix array and has many applications especially for computational biology. We propose three algorithms to construct the index. Two of them are based on a variant of radix sort but each utilizes different types of referential information to sort suffixes by multiple characters at a time. The other is for the case when “don’t care”s appear periodically in patterns and can be combined with the others.