Algorithms and Data Structures

Our main concern is the following variant of the image segmentation problem: given a weighted grid graph and a set of vertical and/or horizontal base lines crossing through the grid, compute a maximum-weight object which can be decomposed into based rectilinear convex objects with respect to the base lines. Our polynomial-time algorithm reduces the problem to solving a polynomial number of instances of the maximum flow problem.

Given a set

${\mathcal P} =\{P_0,\ldots,P_{k-1}\}$

of

k

convex polygons having

n

vertices in total in the plane, we consider the problem of finding

k

translations

τ

0

,…,

τ

k

 − 1

of

P

0

,…,

P

k

 − 1

such that the translated copies

τ

i

P

i

are pairwise disjoint and the area or the perimeter of the convex hull of

$\bigcup_{i=0}^{k-1}\tau_iP_i$

is minimized. When

k

 = 2, the problem can be solved in linear time but no previous work is known for larger

k

except a hardness result: it is NP-hard if

k

is part of input. We show that for

k

 = 3 the translation space of

P

1

and

P

2

can be decomposed into

O

(

n

2

) cells in each of which the combinatorial structure of the convex hull remains the same and the area or perimeter function can be fully described with

O

(1) complexity. Based on this decomposition, we present a first

O

(

n

2

)-time algorithm that returns an optimal pair of translations minimizing the area or the perimeter of the corresponding convex hull.

One advantage of smart grids is that they can reduce the peak load by distributing electricity-demands over multiple short intervals. Finding a schedule that minimizes the peak load corresponds to a variant of a strip packing problem. Normally, for

strip packing problems

, a given set of axis-aligned rectangles must be packed into a fixed-width strip, and the goal is to minimize the height of the strip. The electricity-allocation application can be modelled as

strip packing with slicing:

each rectangle may be cut vertically into multiple slices and the slices may be packed into the strip as individual pieces. The

stacking constraint

forbids solutions in which a vertical line intersects two slices of the same rectangle.

We give a fully polynomial time approximation scheme for this problem, as well as a practical polynomial time algorithm that slices each rectangle at most once and yields a solution of height at most 5/3 times the optimal height.

We study the one-dimensional range minimum query (RMQ) problem in the external memory model. We provide the first space-optimal solution to the batched static version of the problem. On an instance with

N

elements and

Q

queries, our solution takes Θ(sort(

N

 + 

Q

)) = Θ(

$N+Q \over B$

log

M

/

B

$N+Q \over B$

) I/O complexity and O(

N

 + 

Q

) space, where

M

is the size of the main memory and

B

is the block size. This is a factor of O(log

M

/

B

N

) improvement in space complexity over the previous solutions. We also show that an instance of the batched

dynamic

RMQ problem with

N

updates and

Q

queries can be solved in O (

$N+Q \over B$

$\log^{2}_{M /B}$

$N+Q \over B$

) I/O complexity and O(

N

 + 

Q

) space.

Let

$\mathcal{S}$

be a connected planar polygonal subdivision with

n

edges and of total area 1. We present a data structure for point location in

$\mathcal{S}$

where queries with points far away from any region boundary are answered faster. More precisely, we show that point location queries can be answered in time

$O(1+\min(\log \frac{1}{\Delta_{p}}, \log n))$

, where Δ

p

is the distance of the query point

p

to the boundary of the region containing

p

. Our structure is based on the following result: any simple polygon

P

can be decomposed into a linear number of convex quadrilaterals with the following property: for any point

p

 ∈ 

P

, the quadrilateral containing

p

has area

$\Omega(\Delta_{p}^2)$

.

This paper addresses two versions of a fundamental problem, referred to as the All-Nearest-Larger-Neighbors (ANLN) problem, defined as follows: given a one-dimensional array

A

of

n

real-valued keys, find, for each array element

A

[

i

], the index of a nearest array element, if one exists, whose key is strictly larger than

A

[

i

].

We develop algorithms for one- and two-sided versions of the ANLN problem that run in

O

(

n

log

b

n

) time, using Θ(

b

) work-space, for all

b

 = 

O

(

n

), exhibiting a full time-space tradeoff that subsumes all known (memory-restricted) special cases. In addition, a non-trivial lower bound is developed for the time complexity of solving both versions on a pointer machine with limited work-space. This lower bound matches the time complexity of our algorithms, when restricted to constant space.

The fundamental nature of ANLN problems make them intrinsically interesting to study. They also capture the essence of a variety of other familiar problems, such as determining the forest structure associated with a given string of nested parentheses, and triangulating monotone polygons. For both of these, we describe reductions to versions of the ANLN problem, achieving the same time-space tradeoffs.

We consider a coloring problem on dynamic, one-dimensional point sets: points appearing and disappearing on a line at given times. We wish to color them with

k

colors so that at any time, any sequence of

p

(

k

) consecutive points, for some function

p

, contains at least one point of each color.

We prove that no such function

p

(

k

) exists in general. However, in the restricted case in which points appear gradually, but never disappear, we give a coloring algorithm guaranteeing the property at any time with

p

(

k

) = 3

k

 − 2. This can be interpreted as coloring point sets in ℝ

2

with

k

colors such that any bottomless rectangle containing at least 3

k

 − 2 points contains at least one point of each color. Here a bottomless rectangle is an axis-aligned rectangle whose bottom edge is below the lowest point of the set. For this problem, we also prove a lower bound

p

(

k

) > 

ck

, where

c

 > 1.67. Hence, for every

k

there exists a point set, every

k

-coloring of which is such that there exists a bottomless rectangle containing

ck

points and missing at least one of the

k

colors.

Chen

et al.

(2009) proved that no such function

p

(

k

) exists in the case of general axis-aligned rectangles. Our result also complements recent results from Keszegh and Pálvölgyi on cover-decomposability of octants (2011, 2012).

In the Hospitals/Residents (HR) problem, agents are partitioned into hospitals and residents. Each agent wishes to be matched to an agent (or agents) in the other set and has a strict preference over these potential matches. A matching is stable if there are no blocking pairs, i.e., no pair of agents that prefer each other to their assigned matches. Such a situation is undesirable as it could lead to a deviation in which the blocking pair form a private arrangement outside the matching. This however assumes that the blocking pair have social ties or communication channels to facilitate the deviation. Relaxing the stability definition to take account of the potential lack of social ties between agents can yield larger stable matchings.

In this paper, we define the Hospitals/Residents problem under Social Stability (HRSS) which takes into account social ties between agents by introducing a

social network graph

to the HR problem. Edges in the social network graph correspond to resident-hospital pairs in the HR instance that know one another. Pairs that do not have corresponding edges in the social network graph can belong to a matching

M

but they can never block

M

. Relative to a relaxed stability definition for HRSS, called

social stability

, we show that socially stable matchings can have different sizes and the problem of finding a maximum socially stable matching is NP-hard, though approximable within 3/2. Furthermore we give polynomial time algorithms for special cases of the problem.

We consider the problem of finding a 1-planar drawing for a general graph, where a 1-planar drawing is a drawing in which each edge participates in at most one crossing. Since this problem is known to be

NP

-hard we investigate the parameterized complexity of the problem with respect to the vertex cover number, tree-depth, and cyclomatic number. For these parameters we construct fixed-parameter tractable algorithms. However, the problem remains

NP

-complete for graphs of bounded bandwidth, pathwidth, or treewidth.

In this paper we show that the

θ

-graph with 4 cones has constant stretch factor, i.e., there is a path between any pair of vertices in this graph whose length is at most a constant times the Euclidean distance between that pair of vertices. This is the last

θ

-graph for which it was not known whether its stretch factor was bounded.

Karpinski and Nekrich (2008) introduced the problem of parameterized range majority, which asks to preprocess a string of length

n

such that, given the endpoints of a range, one can quickly find all the distinct elements whose relative frequencies in that range are more than a threshold

τ

. Subsequent authors have reduced their time and space bounds such that, when

τ

is given at preprocessing time, we need either

$\mathcal{O}\!\left( {n \lg (1 / \tau) } \right)$

space and optimal

$\mathcal{O}\!\left( {1 / \tau} \right)$

query time or linear space and

$\mathcal{O}\!\left( {(1 / \tau) \lg \lg \sigma} \right)$

query time, where

σ

is the alphabet size. In this paper we give the first linear-space solution with optimal

$\mathcal{O}\!\left( {1 / \tau} \right)$

query time. For the case when

τ

is given at query time, we significantly improve previous bounds, achieving either

$\mathcal{O}\!\left( {n \lg \lg \sigma} \right)$

space and optimal

$\mathcal{O}\!\left( {1 / \tau} \right)$

query time or compressed space and

$\mathcal{O}\!\left( {(1 / \tau) \lg \frac{\lg (1 / \tau)}{\lg \lg n}} \right)$

query time. Along the way, we consider the complementary problem of parameterized range minority that was recently introduced by Chan et al. (2012), who achieved linear space and

$\mathcal{O}\!\left( {1 / \tau} \right)$

query time even for variable

τ

. We improve their solution to use either nearly optimally compressed space with no slowdown, or optimally compressed space with nearly no slowdown. Some of our intermediate results, such as density-sensitive query time for one-dimensional range counting, may be of independent interest.

In the Control Message Aggregation (CMA) problem, control packets are generated over time at the nodes of a tree

T

and need to be transmitted to the root of

T

. To optimize the overall cost, these transmissions can be delayed and different packets can be aggregated, that is a single transmission can include all packets from a subtree rooted at the root of

T

. The cost of this transmission is then equal to the total edge length of this subtree, independently of the number of packets that are sent. A sequence of transmissions that transmits all packets is called a

schedule

. The objective is to compute a schedule with minimum cost, where the cost of a schedule is the sum of all the transmission costs and delay costs of all packets. The problem is known to be

$\mathbb{NP}$

-hard, even for trees of depth 2. In the online scenario, it is an open problem whether a constant-competitive algorithm exists.

We address the special case of the problem when

T

is a chain network. For the online case, we present a 5-competitive algorithm and give a lower bound of 2 + 

φ

 ≈ 3.618, improving the previous bounds of 8 and 2, respectively. Furthermore, for the offline version, we give a polynomial-time algorithm that computes the optimum solution.

The Karp-Rabin fingerprint of a string is a type of hash value that due to its strong properties has been used in many string algorithms. In this paper we show how to construct a data structure for a string

S

of size

N

compressed by a context-free grammar of size

n

that answers fingerprint queries. That is, given indices

i

and

j

, the answer to a query is the fingerprint of the substring

S

[

i

,

j

]. We present the first

O

(

n

) space data structures that answer fingerprint queries without decompressing any characters. For Straight Line Programs (SLP) we get

O

(log

N

) query time, and for Linear SLPs (an SLP derivative that captures LZ78 compression and its variations) we get

O

(loglog

N

) query time. Hence, our data structures has the same time and space complexity as for random access in SLPs. We utilize the fingerprint data structures to solve the longest common extension problem in query time

O

(log

N

logℓ) and

O

(logℓloglogℓ + loglog

N

) for SLPs and Linear SLPs, respectively. Here, ℓ denotes the length of the LCE.

We consider beacons, an analog of geographical greedy routing, motivated by sensor network applications. A beacon

b

is a point object that can be activated to create a ‘magnetic pull’ towards itself everywhere in a polygonal domain

P

. We explore the properties of beacons and their effect on points in polygons, as well as demonstrate polynomial-time algorithms to compute a variety of structures defined by the action of beacons on

P

. We establish a polynomial-time algorithm for routing from a point

s

to a point

t

using a discrete set of candidate beacons, as well as a 2-approximation and a PTAS for routing between beacons placed without restriction in

P

.

We study an offline interval scheduling problem where every job has exactly one associated interval on every machine. To schedule a set of jobs, exactly one of the intervals associated with each job must be selected, and the intervals selected on the same machine must not intersect. We show that deciding whether all jobs can be scheduled is NP-complete already in various simple cases. In particular, by showing the NP-completeness for the case when all the intervals associated with the same job end at the same point in time (also known as just-in-time jobs), we solve an open problem posed by Sung and Vlach (J. Sched., 2005). We also study the related problem of maximizing the number of scheduled jobs. We prove that the problem is NP-hard even for two machines and unit-length intervals. We present a 2/3-approximation algorithm for two machines (and intervals of arbitrary lengths).

We present improved upper bounds on the spanning ratio of a large family of

θ

-graphs. A

θ

-graph partitions the plane around each vertex into

m

disjoint cones, each having aperture

θ

 = 2

π

/

m

. We show that for any integer

k

 ≥ 1,

θ

-graphs with 4

k

 + 4 cones have spanning ratio at most 1 + 2 sin(

θ

/2) / (cos(

θ

/2) − sin(

θ

/2)). We also show that

θ

-graphs with 4

k

 + 3 and 4

k

 + 5 cones have spanning ratio at most cos(

θ

/4) / (cos(

θ

/2) − sin(3

θ

/4)). This is a significant improvement on all families of

θ

-graphs for which exact bounds are not known. For example, the spanning ratio of the

θ

-graph with 7 cones is decreased from at most 7.5625 to at most 3.5132. We also improve the upper bounds on the competitiveness of the

θ

-routing algorithm for these graphs to 1 + 2 sin(

θ

/2) / (cos(

θ

/2) − sin(

θ

/2)) on

θ

-graphs with 4

k

 + 4 cones and to 1 + 2 sin(

θ

/2) ·cos(

θ

/4) / (cos(

θ

/2) − sin(3

θ

/4)) on

θ

-graphs with 4

k

 + 3 and 4

k

 + 5 cones. For example, the routing ratio of the

θ

-graph with 7 cones is decreased from at most 7.5625 to at most 4.0490.

Access graphs, which have been used previously in connection with competitive analysis and relative worst order analysis to model locality of reference in paging, are considered in connection with relative interval analysis. The algorithms LRU, FIFO, FWF, and FAR are compared using the path, star, and cycle access graphs. In this model, some of the expected results are obtained. However, although LRU is found to be strictly better than FIFO on paths, it has worse performance on stars, cycles, and complete graphs, in this model. We solve an open question from [Dorrigiv, López-Ortiz, Munro, 2009], obtaining tight bounds on the relationship between LRU and FIFO with relative interval analysis.

We extend previous studies on NP-hard problems dealing with the decomposition of nonnegative integer vectors into sums of few homogeneous segments. These problems are motivated by radiation therapy and database applications. If the segments may have only positive integer entries, then the problem is called

Vector Explanation

 + 

. If arbitrary integer entries are allowed in the decomposition, then the problem is called

Vector Explanation

. Considering several natural parameterizations (including maximum vector entry, maximum difference between consecutive vector entries, maximum segment length), we obtain a refined picture of the computational (in-)tractability of these problems. In particular, we show that in relevant cases

Vector Explanation

 + 

is algorithmically harder than

Vector Explanation

.

The collective motion of a set of moving entities like people, birds, or other animals, is characterized by groups arising, merging, splitting, and ending. Given the trajectories of these entities, we define and model a structure that captures all of such changes using the Reeb graph, a concept from topology. The

trajectory grouping structure

has three natural parameters, namely group size, group duration, and entity inter-distance. These parameters allow us to obtain detailed or global views of the data. We prove complexity bounds on the maximum number of maximal groups that can be present, and give algorithms to compute the grouping structure efficiently. Furthermore, we showcase the results of experiments using data generated by the NetLogo flocking model and from the Starkey project. Although there is no ground truth for the groups in this data, the experiments show that the trajectory grouping structure is plausible and has the desired effects when changing the essential parameters. Our research provides the first complete study of trajectory group evolvement, including combinatorial, algorithmic, and experimental results.

There have been many instances in the literature where an algorithm with running time of the form

O

(

na

) is improved to an algorithm with running time

O

(

n

a

/

log

b

n

) for some constants a and b. The “four Russians” algorithm for Boolean matrix multiplication is perhaps one of the most well known examples.

In this talk, we will look at a few selected recent examples of this phenomenon, including the

3-SUM

problem, the problem of detecting

affine

degeneracy in a point set,

Klee’s measure

problem, and the

all-pairs shortest paths

problem. (The selection is not comprehensive but is biased towards the speaker’s own expertise.) Bit tricks, table lookups, and constructions of small decision trees are used to achieve many of these polylogarithmic-factor speedups, but often the applications of these techniques require interesting ideas.

After the number of vertices,

Vertex Cover Number

is the largest of the classical graph parameters and has more and more frequently been used as a separate parameter in parameterized problems, including problems that are not directly related to the

Vertex Cover Number

. Here we consider the

treewidth

and

pathwidth

problems parameterized by

k

, the size of a minimum vertex cover of the input graph. We show that the

pathwidth

and

treewidth

can be computed in

O

*

(3

k

) time. This complements recent polynomial kernel results for

treewidth

and

pathwidth

parameterized by the

Vertex Cover Number

.

Given a polygonal domain (or polygon with holes) in the plane, we study the problem of computing the visibility polygon of any query point. As a special case of visibility problems, we also study the ray-shooting problem of finding the first point on the polygon boundaries that is hit by any query ray. These are fundamental problems in computational geometry and have been studied extensively. We present new algorithms and data structures that improve the previous results.

We study the applicability of lift-and-project methods to the

Set Cover

and

Knapsack

problems. Inspired by recent work of Karlin, Mathieu, and Nguyen [IPCO 2011], who examined this connection for

Knapsack

, we consider the applicability and limitations of these methods for

Set Cover

, as well as extending extending the existing results for

Knapsack

.

For the

Set Cover

problem, Cygan, Kowalik, and Wykurz [IPL 2009] gave sub-exponential-time approximation algorithms with approximation ratios better than ln

n

. We present a very simple combinatorial algorithm which has nearly the same time-approximation tradeoff as the algorithm of Cygan et al. We then adapt this to an

LP

-based algorithm using the

LP

hierarchy of Lovász and Schrijver. However, our approach involves the trick of “lifting the objective function”. We show that this trick is essential, by demonstrating an integrality gap of (1 − 

ε

)ln

n

at level Ω(

n

) of the stronger

LP

hierarchy of Sherali and Adams (when the objective function is not lifted).

Finally, we show that the

SDP

hierarchy of Lovász and Schrijver (LS

 + 

) reduces the integrality gap for

Knapsack

to (1 + 

ε

) at level

O

(1). This stands in contrast to

Set Cover

(where the work of Aleknovich, Arora, and Tourlakis [STOC 2005] rules out any improvement using LS

 + 

), and extends the work of Karlin et al., who demonstrated such an improvement only for the more powerful

SDP

hierarchy of Lasserre. Our LS

 + 

based rounding and analysis are quite different from theirs (in particular, not relying on the decomposition theorem they prove for the Lasserre hierarchy), and to the best of our knowledge represents the first explicit demonstration of such a reduction in the integrality gap of LS

 + 

relaxations after a constant number of rounds.

We consider the problem of computing the time-convex hull of a point set under the general

L

p

metric in the presence of a straight-line highway in the plane. The traveling speed along the highway is assumed to be faster than that off the highway, and the shortest time-path between a distant pair may involve traveling along the highway. The time-convex hull TCH(

P

) of a point set

P

is the smallest set containing both

P

and

all

shortest time-paths between any two points in TCH(

P

). In this paper we give an algorithm that computes the time-convex hull under the

L

p

metric in optimal

$\mathcal{O}(n\log n)$

time for a given set of

n

points and a real number

p

with 1 ≤ 

p

 ≤ ∞.

We consider the problem of merging individual text documents, motivated by the single-file merge algorithms of document-based version control systems. Abstracting away the merging of conflicting edits to an external conflict resolution function (possibly implemented by a human), we consider the efficient identification of conflicting regions. We show how to implement tree-based document representation to quickly answer a data structure inspired by the “blame” query of some version control systems. A “blame” query associates every line of a document with the revision in which it was last edited. Our tree uses this idea to quickly identify conflicting edits. We show how to perform a merge operation in time proportional to the sum of the logarithms of the shared regions of the documents, plus the cost of conflict resolution. Our data structure is functional and therefore confluently persistent, allowing arbitrary version DAGs as in real version-control systems. Our results rely on concurrent traversal of two trees with short circuiting when shared subtrees are encountered.

We give an

O

(

n

log

3

n

)-time linear-space algorithm that, given a plane 3-tree

G

with

n

vertices and a set

S

of

n

points in the plane, determines whether

G

has a point-set embedding on

S

(i.e., a planar straight-line drawing of

G

where each vertex is mapped to a distinct point of

S

), improving the

O

(

n

4/3 + 

ε

)-time

O

(

n

4/3

)-space algorithm of Moosa and Rahman. Given an arbitrary plane graph

G

and a point set

S

, Di Giacomo and Liotta gave an algorithm to compute 2-bend point-set embeddings of

G

on

S

using

O

(

W

3

) area, where

W

is the length of the longest edge of the bounding box of

S

. Their algorithm uses

O

(

W

3

) area even when the input graphs are restricted to plane 3-trees. We introduce new techniques for computing 2-bend point-set embeddings of plane 3-trees that takes only

O

(

W

2

) area. We also give approximation algorithms for point-set embeddings of plane 3-trees. Our results on 2-bend point-set embeddings and approximate point-set embeddings hold for partial plane 3-trees (e.g., series-parallel graphs and Halin graphs).

We present a dynamic data structure representing a graph

G

, which allows addition and removal of edges from

G

and can determine the number of appearances of a graph of a bounded size as an induced subgraph of

G

. The queries are answered in constant time. When the data structure is used to represent graphs from a class with bounded expansion (which includes planar graphs and more generally all proper classes closed on topological minors, as well as many other natural classes of graphs with bounded average degree), the amortized time complexity of updates is polylogarithmic.

We formalize a problem we call

combinatorial pair testing

(CPT), which has applications to the identification of uncooperative or unproductive participants in pair programming, massively distributed computing, and crowdsourcing environments. We give efficient adaptive and nonadaptive CPT algorithms and we show that our methods use an optimal number of testing rounds to within constant factors. We also provide an empirical evaluation of some of our methods.

The edge intersection graphs of paths on a grid (or EPG graphs) are graphs whose vertices can be represented as simple paths on a rectangular grid such that two vertices are adjacent if and only if the corresponding paths share at least one edge of the grid. We consider the case of single-bend paths, namely, the class known as

B

1

-EPG graphs. The motivation for studying these graphs comes from the context of circuit layout problems. It is known that recognizing

B

1

-EPG graphs is NP-complete, nevertheless, optimization problems when given a set of paths in the grid are of considerable practical interest.

In this paper, we show that the coloring problem and the maximum independent set problem are both NP-complete for

B

1

-EPG graphs, even when the EPG representation is given. We then provide efficient 4-approximation algorithms for both of these problems, assuming the EPG representation is given. We conclude by noting that the maximum clique problem can be optimally solved in polynomial time for

B

1

-EPG graphs, even when the EPG representation is not given.

For every

n

 ∈ ℕ, we present a set

S

n

of

O

(

n

5/3

) points in the plane such that every planar 3-tree with

n

vertices has a straight-line embedding in the plane in which the vertices are mapped to a subset of

S

n

. This is the first subquadratic upper bound on the size of universal point sets for planar 3-trees, as well as for the class of 2-trees and serial parallel graphs.

In the graph packing problem we are given several graphs and have to map them into a single host graph

G

such that each edge of

G

is used at most once. Much research has been devoted to the packing of trees, especially to the case where the host graph must be planar. More formally, the problem is: Given any two trees

T

1

and

T

2

on

n

vertices, we want a simple planar graph

G

on

n

vertices such that the edges of

G

can be colored with two colors and the subgraph induced by the edges colored

i

is isomorphic to

T

i

, for

i

 ∈ {1,2}.

A clear exception that must be made is the star tree which cannot be packed together with any other tree. But a popular hypothesis states that this is the only exception, and all other pairs of trees admit a planar packing. Previous proof attempts lead to very limited results only, which include a tree and a spider tree, a tree and a caterpillar, two trees of diameter four and two isomorphic trees.

We make a step forward and prove the hypothesis for any two binary trees. The proof is algorithmic and yields a linear time algorithm to compute a plane packing, that is, a suitable two-edge-colored host graph along with a planar embedding for it. In addition we can also guarantee several nice geometric properties for the embedding: vertices are embedded equidistantly on the

x

-axis and edges are embedded as semi-circles.

We consider communities whose vertices are predominantly connected, i.e., the vertices in each community are stronger connected to other community members of the same community than to vertices outside the community. Flake et al. introduced a hierarchical clustering algorithm that finds predominantly connected communities of different coarseness depending on an input parameter. We present a simple and efficient method for constructing a clustering hierarchy according to Flake et al. that supersedes the necessity of choosing feasible parameter values and guarantees the completeness of the resulting hierarchy, i.e., the hierarchy contains all clusterings that can be constructed by the original algorithm for any parameter value. However, predominantly connected communities are not organized in a single hierarchy. Thus, we further develop a framework that, after precomputing at most 2(

n

 − 1) maximum flows, admits a linear time construction of a clustering Ω(

S

) of predominantly connected communities that contains a given community

S

and is maximum in the sense that any further clustering of predominantly connected communities that also contains

S

is hierarchically nested in Ω(

S

). We further generalize this construction yielding a clustering with similar properties for

k

given communities in

O

(

kn

) time. This admits the analysis of a network’s structure with respect to various communities in different hierarchies.

Multicore shared cache processors pose a challenge for designers of embedded systems who try to achieve minimal and predictable execution time of workloads consisting of several jobs. To address this challenge the cache is statically partitioned among the cores and the jobs are assigned to the cores so as to minimize the makespan. Several heuristic algorithms have been proposed that jointly decide how to partition the cache among the cores and assign the jobs. We initiate a theoretical study of this problem which we call the joint cache partition and job assignment problem.

By a careful analysis of the possible cache partitions we obtain a constant approximation algorithm for this problem. For some practical special cases we obtain a 2-approximation algorithm, and show how to improve the approximation factor even further by allowing the algorithm to use additional cache. We also study possible improvements that can be obtained by allowing dynamic cache partitions and dynamic job assignments.

We define a natural restriction of the well known scheduling problem on unrelated machines in which machines are ordered by “strength”. We call this restriction the

ordered unrelated machines scheduling problem

. We show that our joint cache partition and job assignment problem is harder than this scheduling problem. The ordered unrelated machines scheduling problem is of independent interest and we give a polynomial time algorithm for certain natural workloads.

Given a weighted

n

-vertex graph

G

with integer edge-weights taken from a range [ − 

M

,

M

], we show that the minimum-weight simple path visiting

k

vertices can be found in time

$\tilde{O}(2^k \mathrm{poly}(k) M n^\omega) = O^*(2^k M)$

. If the weights are reals in [1,

M

], we provide a (1 + 

ε

)-approximation which has a running time of

$\tilde{O}(2^k \mathrm{poly}(k) n^\omega(\log\log M + 1/\varepsilon))$

. For the more general problem of

k

-tree, in which we wish to find a minimum-weight copy of a

k

-node tree

T

in a given weighted graph

G

, under the same restrictions on edge weights respectively, we give an exact solution of running time

$\tilde{O}(2^k \mathrm{poly}(k) M n^3) $

and a (1 + 

ε

)-approximate solution of running time

$\tilde{O}(2^k \mathrm{poly}(k) n^3(\log\log M + 1/\varepsilon))$

. All of the above algorithms are randomized with a polynomially-small error probability.

We design compressed persistent indices that store a bit vector of size

n

and support a sequence of

k

bit-flip update operations, such that rank and select queries at any version can be supported efficiently. In particular, we present partially and fully persistent compressed indices for offline and online updates that support all operations in time polylogarithmic in

n

and

k

. This improves upon the space or time complexities of straightforward approaches, when

$k=O(\frac{n}{\log n})$

, which is common in biological applications. We also prove that any partially persistent index that occupies

O

((

n

 + 

k

)log(

nk

)) bits requires

ω

(1) time to support the rank query at a given version.

Stencil computations on low dimensional grids are kernels of many scientific applications including finite difference methods used to solve partial differential equations. On typical modern computer architectures such stencil computations are limited by the performance of the memory subsystem, namely by the bandwidth between main memory and the cache. This work considers the computation of star stencils, like the 5-point and 7-point stencil, in the external memory model. The analysis focuses on the constant of the leading term of the non-compulsory I/Os. Optimizing stencil computations is an active field of research, but so far, there has been a significant gap between the lower bounds and the performance of the algorithms. In two dimensions, matching constants for lower and upper bounds are provided closing a gap of 4. In three dimensions, the bounds match up to a factor of

$\sqrt{2}$

improving the known results by a factor of 2

$\sqrt{3}\sqrt{B}$

, where B is the block (cache line) size of the external memory model. For higher dimensions n, the presented lower bounds improve the previously known by a factor between 4 and 6 leaving a gap of

$\sqrt[n-1]{n!} \thickapprox{{n} \over{e}}$

.

We introduce a variation of the graph isomorphism problem, where, given two graphs

G

1

 = (

V

1

,

E

1

) and

G

2

 = (

V

2

,

E

2

) and three integers

l

,

d

, and

k

, we seek for a set

D

 ⊆ 

V

1

and a one-to-one mapping

f

:

V

1

 → 

V

2

such that |

D

| ≤ 

k

and for every vertex

v

 ∈ 

V

1

 ∖ 

D

and every vertex

$u\in N_{G_1}^l(v)\setminus D$

we have

$f(u)\in N_{G_2}^d(f(v))$

. Here, for a graph

G

and a vertex

v

, we use

$N_{G}^i(v)$

to denote the set of vertices which have distance at most

i

to

v

in

G

. We call this problem

Neighborhood-Preserving Mapping

(NPM). The main result of this paper is a complete dichotomy of the classical complexity of NPM on trees with respect to different values of

l

,

d

,

k

. Additionally, we present two dynamic programming algorithms for the case that one of the input trees is a path.

We investigate the implications of the exponential time hypothesis on algorithms for scheduling and packing problems. Our main focus is to show tight lower bounds on the running time of these algorithms. For exact algorithms we investigate the dependence of the running time on the number

n

of items (for packing) or jobs (for scheduling). We show that many of these problems, including

SubsetSum

,

Knapsack

,

BinPacking

, 〈

P

2 | |

C

max

〉, and 〈

P

2 | | ∑ 

w

j

C

j

〉, have a lower bound of 2

o

(

n

)

× ∥ 

I

 ∥ 

O

(1)

. We also develop an algorithmic framework that is able to solve a large number of scheduling and packing problems in time 2

O

(

n

)

× ∥ 

I

 ∥ 

O

(1)

. Finally, we show that there is no PTAS for

MultipleKnapsack

and 2

d-Knapsack

with running time

$2^{o}({\frac{1}{\epsilon }}) \times \parallel I \parallel^{O(1)}$

and

$n^{o({\frac{1}{\epsilon }})} \times \parallel{I}\parallel^{O(1)}$

.

The weighted monotone and antimonotone satisfiability problems on normalized circuits, abbreviated

wsat

 + 

[

t

] and

wsat

−

[

t

], are canonical problems in the parameterized complexity theory. We study the parameterized complexity of

wsat

−

[

t

] and

wsat

 + 

[

t

], where

t

 ≥ 2, with respect to the genus of the circuit. For

wsat

−

[

t

], we give a fixed-parameter tractable (FPT) algorithm when the genus of the circuit is

n

o

(1)

, where

n

is the number of the variables in the circuit. For

wsat

 + 

[2] (

i.e.

, weighted monotone

cnf-sat

) and

wsat

 + 

[3], which are both

W

[2]-complete, we also give FPT algorithms when the genus is

n

o

(1)

. For

wsat

 + 

[

t

] where

t

 > 3, we give FPT algorithms when the genus is

$O(\sqrt{\log{n}})$

. We also show that both

wsat

−

[

t

] and

wsat

 + 

[

t

] on circuits of genus

n

Ω(1)

have the same

W

-hardness as the general

wsat

 + 

[

t

] and

wsat

−

[

t

] problem (

i.e.

, with no restriction on the genus), thus drawing a precise map of the parameterized complexity of

wsat

−

[

t

], and of

wsat

 + 

[

t

], for

t

 = 2,3, with respect to the genus of the underlying circuit.

As a byproduct of our results, we obtain, via standard parameterized reductions, tight results on the parameterized complexity of several problems with respect to the genus of the underlying graph.

In the

Boundary Labeling

problem, we are given a set of

n

points, referred to as

sites

, inside an axis-parallel rectangle

R

, and a set of

n

pairwise disjoint rectangular labels that are attached to

R

from the outside. The task is to connect the sites to the labels by non-intersecting rectilinear paths, so-called

leaders

, with at most one bend.

In this paper, we study the problem

Two-Sided Boundary Labeling with Adjacent Sides

, where labels lie on two adjacent sides of the enclosing rectangle. We present a polynomial-time algorithm that computes a crossing-free leader layout if one exists. So far, such an algorithm has only been known for the cases that labels lie on one side or on two opposite sides of

R

(where a crossing-free solution always exists). For the more difficult case where labels lie on adjacent sides, we show how to compute crossing-free leader layouts that maximize the number of labeled points or minimize the total leader length.

We consider the problem of batch scheduling on parallel machines where jobs have release times, deadlines, and identical processing times. The goal is to schedule these jobs in batches of size at most

B

on

m

identical machines. Previous work on this problem primarily focused on finding feasible schedules. Motivated by the problem of minimizing energy, we consider problems where the number of batches is significant. Minimizing the number of batches on a single processor previously required an impractical

O

(

n

8

) dynamic programming algorithm. We present a

O

(

n

3

) algorithm for simultaneously minimizing the number of batches and maximum completion time, and give improved guarantees for variants with infinite size batches, agreeable release times, and batch “budgets”. Finally, we give a pseudo-polynomial algorithm for general batch-count-sensitive objective functions and correct errors in previous results.

Let

$\mathcal{D}$

be a set of

n

pairwise disjoint unit disks in the plane. We describe how to build a data structure for

$\mathcal{D}$

so that for any point set

P

containing exactly one point from each disk, we can quickly find the onion decomposition (convex layers) of

P

.

Our data structure can be built in

O

(

n

log

n

) time and has linear size. Given

P

, we can find its onion decomposition in

O

(

n

log

k

) time, where

k

is the number of layers. We also provide a matching lower bound.

Our solution is based on a recursive space decomposition, combined with a fast algorithm to compute the union of two disjoint onion decompositions.

We study planar point location in a collection of disjoint fat regions, and investigate the complexity of

local updates

: replacing any region by a different region that is “similar” to the original region. (i.e., the size differs by at most a constant factor, and distance between the two regions is a constant times that size).We show that it is possible to create a linear size data structure that allows for insertions, deletions, and queries in logarithmic time, and allows for local updates in sub-logarithmic time on a pointer machine. We also give results parameterized by the fatness and similarity of the objects considered.

We present a parameterized enumeration algorithm for

Kemeny Rank Aggregation

, the problem of determining an

optimal aggregation

, a total order that is at minimum total

τ-distance

(

k

t

) from the input multi-set of

m

total orders (

votes

) over a set of alternatives (

candidates

), where the

τ

-distance between two total orders is the number of pairs of candidates ordered differently. Our

$O^*(4^{k_t\over m})$

-time algorithm constitutes a significant improvement over the previous

$O^*(36^{k_t\over m})$

upper bound.

The analysis of our algorithm relies on the notion of locally-optimal aggregations, total orders whose total

τ

-distances from the votes do not decrease by any single swap of two candidates adjacent in the ordering. As a consequence of our approach, we provide not only an upper bound of

$4^{k_t\over m}$

on the number of optimal aggregations, but also the first parameterized bound,

$4^{k_t\over m}$

, on the number of locally-optimal aggregations, and demonstrate that it is tight. Furthermore, since our results rely on a known relation to

Weighted Directed Feedback Arc Set

, we obtain new results for this problem along the way.

From automatically translating documents to analyzing electoral voting patterns; from computing personalized movie recommendations to predicting flu epidemics: all of these tasks are possible due to the success and proliferation of the MapReduce parallel programming paradigm. Yet almost ten years after the system was introduced, we still do not have a good understanding of what problems can and cannot be efficiently computed in MapReduce.

In this talk I will give an overview of the MapReduce framework, and explain its connections to both Valiant’s Bulk Synchronous Parallel (BSP) model and the classical PRAM model of parallel computing. To demonstrate the power of the MapReduce model I will present the

Sample and Prune

approach that finds an approximate coreset of a manageable size, thereby reducing the problem from the realm of ‘Big Data’ to that of ‘Small Data.’

I will conclude by discussing other considerations that make a large difference when working with MapReduce in practice, but have so far resisted a careful theoretical analysis.

We reinterpret classic Gray codes for binary strings, permutations, combinations, binary trees, and set partitions using a simple greedy algorithm. The algorithm begins with an initial object and an ordered list of operations, and then repeatedly creates a new object by applying the first possible operation to the most recently created object.