Algorithms and Computation

A potential way to advertise on social networks is to rely on word of mouth. What is a market approach to word of mouth social advertising? We describe an example: MyLikes, which is a new advertising platform. It lets anyone on a social network be a “publisher” of advertisements (ads). It provides a matching market so advertisers can find social publishers to advertise their products. Further, interestingly, it lets the social publishers modify the ad. As a result, a single base ad may be morphed into many. MyLikes lets publishers broadcast and communicate the ads to others in their social network. Finally, it provides a mechanism for advertisers to pay the publishers based on engagement of the social users with the ads. We describe research problems that emerge in such a marketplace for social ads.

Polygons are a paramount data structure in computational geometry. While the complexity of many algorithms on simple polygons or polygons with holes depends on the size of the input polygon, the intrinsic complexity of the problems these algorithms solve is often related to the reflex vertices of the polygon. In this paper, we give an easy-to-describe linear-time method to replace an input polygon

$\mathcal{P}$

by a polygon

$\mathcal{P}'$

such that (1)

$\mathcal{P}'$

contains

$\mathcal{P}$

, (2)

$\mathcal{P}'$

has its reflex vertices at the same positions as

$\mathcal{P}$

, and (3) the number of vertices of

$\mathcal{P}'$

is linear in the number of reflex vertices. Since the solutions of numerous problems on polygons (including shortest paths, geodesic hulls, separating point sets, and Voronoi diagrams) are equivalent for both

$\mathcal{P}$

and

$\mathcal{P}'$

, our algorithm can be used as a preprocessing step for several algorithms and makes their running time dependent on the number of reflex vertices rather than on the size of

$\mathcal{P}$

.

We propose a linear working space algorithm for reconstructing a simple polygon from the visibility angle information at vertices up to similarity. We also modify the algorithm such that its running time is sensitive to the size of visibility graph and also the diameter of a triangulation of the polygon.

This paper is concerned with the crossing number of Euclidean minimum-weight Laman graphs in the plane. We first investigate the relation between the Euclidean minimum-weight Laman graph and proximity graphs, and then we show that the Euclidean minimum-weight Laman graph is quasi-planar and 6-planar. Thus the crossing number of the Euclidean minimum-weight Laman graph is linear in the number of points.

We characterize the self-parallel (mitered) offsets of a general nonconvex polytope

$\mathcal{Q}$

in 3-space and give a canonical algorithm that constructs a straight skeleton for

$\mathcal{Q}$

.

The

Sorting by Reversals

Problem is known to be

$\cal{NP}$

-hard. A simplification,

Sorting by Signed Reversals

is polynomially computable. Motivated by the Pattern Matching with Rearrangements model, we consider

Pattern Matching with Reversals

. Since this is a generalization of the Sorting by Reversals problem, it is clearly

${\cal NP}$

-hard. We, therefore consider the simplification where reversals cannot overlap. Such a constrained version has been researched in the past for various metrics in the rearrangement model - the swap metric and the interchange metric. We show that the constrained problem can be solved in linear time. We then consider the

Approximate Pattern Matching with non-overlapping Reversals

problem, i.e. where mismatch errors are introduced. We show that the problem can be solved in quadratic time and space. Finally, we consider the on-line version of the problem. We introduce a novel signature for palindromes and show that it has a pleasing behavior, similar to the Karp-Rabin signature. It allows solving the

Pattern Matching with non-overlapping Reversals

problem on-line in linear time w.h.p.

Let

t

be a permutation (that shall play the role of the

text

) on [

n

] and a motif

p

be a sequence of

m

distinct integer(s) of [

n

],

m

 ≤ 

n

. The motif

p

occurs in

t

in position

i

if and only if

p

1

…

p

m

is order-isomorphic to

t

i

…

t

i

 + 

m

 − 1

, that is, for all 1 ≤ 

k

 < ℓ ≤ 

m

,

p

k

 > 

p

ℓ

if and only if

t

i

 + 

k

 − 1

 > 

t

i

 + ℓ − 1

. Searching for a motif

p

in a text

t

consists in identifying all occurrences of

p

in

t

. We first present a forward automaton which allows us to search for

p

in

t

in

O

(

m

2

loglog

m

 + 

n

) time. We then introduce a Morris-Pratt automaton representation of the forward automaton which allows us to reduce this complexity to

O

(

m

loglog

m

 + 

n

) at the price of an additional amortized constant term. The latter automaton occupies

O

(

m

) space. We then extend the problem to search for a set of motifs and exhibit a specific Aho-Corasick like algorithm. Next we present a sub-linear average case search algorithm running in

$O\left(\frac{m\log m}{\log\log m}+\frac{n\log m}{m\log\log m}\right)$

time, that we eventually prove to be optimal on average.

Given an LZW/LZ78 compressed text, we want to find an approximate occurrence of a given pattern of length

m

. The goal is to achieve time complexity depending on the size

n

of the compressed representation of the text instead of its length. We consider two specific definitions of approximate matching, namely the Hamming distance and the edit distance, and show how to achieve

$\mathcal{O}(n\sqrt{m}k^{2})$

and

$\mathcal{O}(n\sqrt{m}k^{3})$

running time, respectively, where

k

is the bound on the distance, both in linear space. Even for very small values of

k

, the best previously known solutions required Ω(

nm

) time. Our main contribution is applying a periodicity-based argument in a way that is computationally effective even if we operate on a compressed representation of a string, while the previous solutions were either based on a dynamic programming, or a black-box application of tools developed for uncompressed strings.

Text indexing is a fundamental problem in computer science, where the task is to index a given text (string)

T

[1..

n

], such that whenever a pattern

P

[1..

p

] comes as a query, we can efficiently report all those locations where

P

occurs as a substring of

T

. In this paper, we consider the case when

P

contains wildcard characters (which can match with any other character). The first non-trivial solution for the problem is given by Cole et al. [STOC 2004], where the index space is

O

(

n

log

k

n

) words or

O

(

n

log

k

 + 1

n

) bits and the query time is

O

(

p

 + 2

h

loglog

n

 + 

occ

), where

k

is the maximum number of wildcard characters allowed in

P

,

h

 ≤ 

k

is the number of wildcard characters in

P

and

occ

represents the number of occurrences of

P

in

T

. Even though many indexes offering different space-time trade-offs were later proposed, a clear improvement on this result is still not known. In this paper, we first propose an

O

(

n

log

k

 + 

ε

n

) bits index achieving the same query time as that of Cole et al.’s index, where 0 < 

ε

 < 1 is an arbitrary small constant. Then we propose another index of size

O

(

n

log

k

n

log

σ

) bits, but with a slightly higher query time of

O

(

p

 + 2

h

log

n

 + 

occ

), where

σ

denotes the alphabet set size.

For a linear code, deep holes are defined to be vectors that are further away from codewords than all other vectors. The problem of deciding whether a received word is a deep hole for generalized Reed-Solomon codes is proved to be co-NP-complete [9][5]. For the extended Reed-Solomon codes

$RS_q(\mathbb{F}_q,k)$

, a conjecture was made to classify deep holes in [5]. Since then a lot of effort has been made to prove the conjecture, or its various forms. In this paper, we classify deep holes completely for generalized Reed-Solomon codes

RS

p

(

D

,

k

), where

p

is a prime,

$|D| > k \geqslant \frac{p-1}{2}$

. Our techniques are built on the idea of deep hole trees, and several results concerning the Erdös-Heilbronn conjecture.

We study the graph isomorphism problem for graph classes defined by sets of forbidden subgraphs. We show that there is a complexity dichotomy in case the set of forbidden subgraphs is finite. More precisely, we show that the problem is polynomial-time solvable if the forbidden set contains a forest of subdivided stars and is graph isomorphism complete otherwise. We also show that, assuming that the graph isomorphism problem is not polynomial-time solvable in general, there is no such dichotomy for the cases of infinite sets of forbidden subgraphs. To this end, we conditionally show that there exists a graph class closed under taking subgraphs with intermediate isomorphism problem, i.e., a class on which the isomorphism problem is neither polynomial-time solvable nor graph isomorphism complete.

Let

$\mathbb{F}$

be a field of characteristic ≠ 2. The

determinantal complexity

of a polynomial

$P\in\mathbb{F}[x_1, \dots, x_n]$

is defined as the smallest size of a matrix

M

whose entries are linear polynomials of

x

i

’s over

$\mathbb{F}$

, such that

$P=\det (M)$

as polynomials in

$\mathbb{F}[x_1, \dots, x_n]$

. To determine the determinantal complexity of the permanent polynomial is a long-standing open problem.

Let

$\mathbb{K}$

be an

extension field

of

$\mathbb{F}$

; then

P

can be viewed as a polynomial over

$\mathbb{K}$

. We are interested in the comparison between the determinantal complexity of

P

over

$\mathbb{K}$

(denoted as

$\mathtt{dc}_{\mathbb{K}}(P)$

), and that of

P

over

$\mathbb{F}$

(denoted as

$\mathtt{dc}_{\mathbb{F}}(P)$

). It is clear that

$\mathtt{dc}_{\mathbb{K}}(P)\leq \mathtt{dc}_\mathbb{F}(P)$

, and the question is whether strict inequality can happen. In this note we consider polynomials defined over ℚ. For

$P=x_1^2+\dots+x_n^2$

, there exists a constant multiplicative gap between

dc

ℝ

(

P

) and

dc

ℂ

(

P

): we prove

dc

ℝ

(

P

) ≥ 

n

while ⌈

n

/2⌉ + 1 ≥ 

dc

ℂ

(

P

). We also consider additive constant gaps: (1) there exists a quadratic polynomial

Q

 ∈ ℚ[

x

,

y

], such that

dc

ℚ

(

Q

) = 3 and

$\mathtt{dc}_{\overline{\mathbb{Q}}}(Q)=2$

; (2) there exists a cubic polynomial

C

 ∈ ℚ[

x

,

y

] with a rational zero, such that

dc

ℚ

(

C

) = 4 and

$\mathtt{dc}_{\overline{\mathbb{Q}}}(C)=3$

. For additive constant gaps, geometric criteria are presented to decide when

$\mathtt{dc}_{\mathbb{Q}}=\mathtt{dc}_{\overline{\mathbb{Q}}}$

.

Social networks are often analyzed through a graph model of the network. The

dot product model

assumes that two individuals are connected in the social network if their attributes or opinions are similar. In the model, a

d

-dimensional vector a

v

represents the extent to which individual

v

has each of a set of

d

attributes or opinions. Then two individuals

u

and

v

are assumed to be friends, that is, they are connected in the graph model, if and only if a

u

· a

v

 ≥ 

t

, for some fixed, positive threshold

t

. The resulting graph is called a

d-dot product graph.

.

We consider two measures for diversity and clustering in social networks by using a

d

-dot product graph model for the network. Diversity is measured through the size of the largest independent set of the graph, and clustering is measured through the size of the largest clique. We obtain a tight result for the diversity problem, namely that it is polynomial-time solvable for

d

 = 2, but

NP

-complete for

d

 ≥ 3. We show that the clustering problem is polynomial-time solvable for

d

 = 2. To our knowledge, these results are also the first on the computational complexity of combinatorial optimization problems on dot product graphs.

We also consider the situation when two individuals are connected if their preferences are not opposite. This leads to a variant of the standard dot product graph model by taking the threshold

t

to be zero. We prove in this case that the diversity problem is polynomial-time solvable for any fixed

d

.

For a graph

G

, let

Z

(

G

,

λ

) be the partition function of the monomer-dimer system defined by ∑ 

k

m

k

(

G

)

λ

k

, where

m

k

(

G

) is the number of matchings of size

k

in

G

. We consider graphs of bounded degree and develop a sublinear-time algorithm for estimating log

Z

(

G

,

λ

) at an arbitrary value

λ

 > 0 within additive error

εn

with high probability. The query complexity of our algorithm does not depend on the size of

G

and is polynomial in 1/

ε

, and we also provide a lower bound quadratic in 1/

ε

for this problem. This is the first analysis of a sublinear-time approximation algorithm for a #

P

-complete problem. Our approach is based on the correlation decay of the Gibbs distribution associated with

Z

(

G

,

λ

). We show that our algorithm approximates the probability for a vertex to be covered by a matching, sampled according to this Gibbs distribution, in a near-optimal sublinear time. We extend our results to approximate the average size and the entropy of such a matching within an additive error with high probability, where again the query complexity is polynomial in 1/

ε

and the lower bound is quadratic in 1/

ε

. Our algorithms are simple to implement and of practical use when dealing with massive datasets. Our results extend to other systems where the correlation decay is known to hold as for the independent set problem up to the critical activity.

We define and analyze an anonymization problem in undirected graphs, which is motivated by certain privacy issues in social networks. The goal is to remove a small number of vertices from the graph such that in the resulting subgraph every occurring vertex degree occurs many times.

We prove that the problem is NP-hard for trees, and also for a number of other highly structured graph classes. Furthermore we provide polynomial time algorithms for other graph classes (like threshold graphs), and thereby establish a sharp borderline between hard and easy cases of the problem. Finally we perform a parametrized analysis, and we concisely characterize combinations of natural parameters that allow FPT algorithms.

A graph drawn in the plane with

n

vertices is

fan-crossing free

if there is no triple of edges

e

,

f

and

g

, such that

e

and

f

have a common endpoint and

g

crosses both

e

and

f

. We prove a tight bound of 4

n

 − 9 on the maximum number of edges of such a graph for a straight-edge drawing. The bound is 4

n

 − 8 if the edges are Jordan curves. We also discuss generalizations to monotone graph properties.

The game of cops and robber, introduced by Nowakowski and Winkler in 1983, is played by two players on a graph

G

, one controlling

k

cops and the other one robber, all positioned on

V

G

. The players alternate in moving their pieces to distance at most 1 each. The cops win if they capture the robber, the robber wins by escaping indefinitely. The cop-number of

G

, that is the smallest

k

such that

k

cops win the game, has recently been a widely studied parameter.

Intersection graph classes are defined by their geometric representations: the vertices are represented by certain geometrical shapes and two vertices are adjacent if and only if their representations intersect. Some well-known intersection classes include interval and string graphs. Various properties of many of these classes have been studied recently, including an interest in their game-theoretic properties.

In this paper we show an upper bound on the cop-number of string graphs and sharp bounds on the cop-number of interval filament graphs, circular graphs, circular arc graphs and function graphs. These results also imply polynomial algorithms determining cop-number for all these classes and their sub-classes.

We show that every

n

-vertex planar graph admits a simultaneous embedding with no mapping and with fixed edges with any (

n

/2)-vertex planar graph. In order to achieve this result, we prove that every

n

-vertex plane graph has an induced outerplane subgraph containing at least

n

/2 vertices. Also, we show that every

n

-vertex planar graph and every

n

-vertex planar partial 3-tree admit a simultaneous embedding with no mapping and with fixed edges.

Given a directed graph

D

 = (

V

,

A

) we define its intersection graph

I

(

D

) = (

A

,

E

) to be the graph having

A

as a node-set and two nodes of

I

(

D

) are adjacent if their corresponding arcs share a common node that is the tail of at least one of these arcs. We call them facility location graphs since they arise from the classical uncapacitated facility location problem. In this paper we show that facility location graphs are hard to recognize but they are easy to recognize when the underlying graph is triangle-free. We also determine the complexity of the vertex coloring, the stable set and the facility location problem for triangle-free facility location graphs.

We study two local search and a greedy algorithm for scheduling. The worst-case performance guarantees are well-known but seem to be contrived and too pessimistic for practical applications. For unrestricted machines, Brunsch et al. [3] showed that the worst-case performance guarantees of these algorithms are not robust if the job sizes are subject to random noise. However, in the case of restricted related machines the worst-case bounds turned out to be robust even in the presence of random noise. We show that if the machine speeds rather than the job sizes are perturbed, also the performance guarantees for restricted machines decrease thus yielding a stronger result.

We consider a variant of the online buffer management problem in network switches, called the

k

-frame throughput maximization problem (

k

-FTM). This problem models the situation where a large frame is fragmented into

k

packets and transmitted through the Internet, and the receiver can reconstruct the frame only if he/she accepts all the

k

packets. Kesselman et al. introduced this problem and showed that its competitive ratio is unbounded even when

k

 = 2. They also introduced an “order-respecting” variant of

k

-FTM, called

k

-OFTM, where inputs are restricted in some natural way. They proposed an online algorithm and showed that its competitive ratio is at most

$\frac{ 2kB }{ \lfloor B/k \rfloor } + k$

for any

B

 ≥ 

k

, where

B

is the size of the buffer. They also gave a lower bound of

$\frac{ B }{ \lfloor 2B/k \rfloor }$

for deterministic online algorithms when 2

B

 ≥ 

k

and

k

is a power of 2.

In this paper, we improve upper and lower bounds on the competitive ratio of

k

-OFTM. Our main result is to improve an upper bound of

O

(

k

2

) by Kesselman et al. to

$\frac{5B + \lfloor B/k \rfloor - 4}{\lfloor B/2k \rfloor} = O(k)$

for

B

 ≥ 2

k

. Note that this upper bound is tight up to a multiplicative constant factor since the lower bound given by Kesselman et al. is Ω(

k

). We also give two lower bounds. First we give a lower bound of

$\frac{2B}{\lfloor{B/(k-1)} \rfloor} + 1$

on the competitive ratio of deterministic online algorithms for any

k

 ≥ 2 and any

B

 ≥ 

k

 − 1, which improves the previous lower bound of

$\frac{B}{ \lfloor 2B/k \rfloor }$

by a factor of almost four. Next, we present the first nontrivial lower bound on the competitive ratio of randomized algorithms. Specifically, we give a lower bound of

k

 − 1 against an oblivious adversary for any

k

 ≥ 3 and any

B

. Since a deterministic algorithm, as mentioned above, achieves an upper bound of about 10

k

, this indicates that randomization does not help too much.

When considering the NP-hard problem of scheduling precedence constrained tasks with preemptions on identical parallel machines with the goal of minimising the maximum lateness, approximation algorithms are commonly studied. It is desirable to characterise in some way the circumstances under which a given algorithm will provide an optimal solution. This paper considers a well-known scheduling algorithm called the Brucker-Garey-Johnson Algorithm, known to produce optimal schedules whenever the precedence constraints are in the form of in-trees. A new class of partial orders is presented and it is proved not only that the Brucker-Garey-Johnson Algorithm will solve every problem instance constrained by a partial order from that class but also that no larger class has this property.

Drawing a random variate from a given binomial distribution

B

(

n

,

p

) is an important subroutine in many large-scale simulations. The naive algorithm takes

$\mathcal{O}(n)$

time and has no precision loss, however, this method is often too slow in many settings. The problem of sampling from a binomial distribution in sublinear time has been extensively studied and implemented in such packages as R [22] and the GNU Scientific Library (GSL) [10], however, all known sublinear-time algorithms involve precisions loss, which introduces artifacts into the sampling, such as discontinuities.

In this paper, we present the first algorithm, to the best of our knowledge, that samples binomial distributions in sublinear time with no precision loss.

For a CNF formula

F

we define its 1-conflict graph as follows: Two clauses

C

,

D

 ∈ 

F

are connected by an edge if they have a nontrivial resolvent – that is, if there is a unique literal

u

 ∈ 

C

for which

$\bar{u} \in D$

. Let lc

1

(

F

) denote the maximum degree of this graph.

A

k

-CNF formula is a CNF formula in which each clause has exactly

k

distinct literals. We show that (1) a

k

-CNF formula

F

with lc

1

(

F

) ≤ 

k

 − 1 is satisfiable; (2) there are unsatisfiable

k

-CNF formulas

F

with lc

1

(

F

) = 

k

; (3) there is a polynomial time algorithm deciding whether a

k

-CNF formula

F

with lc

1

(

F

) = 

k

is satisfiable; (4) satisfiability of

k

-CNF formulas

F

with lc

1

(

F

) ≤ 

k

 + 1 is NP-hard.

Furthermore, we show that if

F

is a

k

-CNF formula and lc

1

(

F

) ≤ 

k

, then we can find in polynomial time a satisfying assignment (if

F

is satisfiable) or a treelike resolution refutation with at most |

F

| leaves (if

F

is unsatisfiable). Here, |

F

| is the number of clauses of

F

.

An important but strongly NP-hard problem in automated cartography is how to best place textual labels for point features on a static map. We examine the complexity of various generalizations of this problem for dynamic and/or interactive maps. Specifically, we show that it is strongly PSPACE/complete to decide whether there is a smooth dynamic labeling (function from time to static labelings) when the points move, when points are added and removed, or when the user pans, rotates, and/or zooms their view of the points.

A pair of clauses in a CNF formula constitutes a conflict if there is a variable that occurs positively in one clause and negatively in the other. A CNF formula without any conflicts is satisfiable. The Lovász Local Lemma implies that a CNF formula with clauses of size exactly

k

(a

k-CNF formula

), is satisfiable unless some clause conflicts with at least

$\frac{2^k}{e}$

clauses. It does not, however, give any good bound on how many conflicts an unsatisfiable formula has globally. We show here that every unsatisfiable

k

-CNF formula requires Ω(2.69

k

) conflicts and there exist unsatisfiable

k

-CNF formulas with

O

(3.51

k

) conflicts.

We consider the following variant of a classical pursuit-evasion problem:

how many pursuers are needed to capture a single (adversarial) evader on the surface of a 3-dimensional polyhedral body?

The players remain on the closed polyhedral surface, have the same maximum speed, and are always aware of each others’ current positions. This generalizes the classical lion-and-the-man game, originally proposed by Rado [12], in which the players are restricted to a two-dimensional circular arena. The extension to a polyhedral surface is both theoretically interesting and practically motivated by applications in robotics where the physical environment is often approximated as a polyhedral surface. We analyze the game under the discrete-time model, where the players take alternate turns, however, by choosing an appropriately small time step

t

 > 0, one can approximate the continuous time setting to an arbitrary level of accuracy. Our main result is that 4 pursuers always suffice (upper bound), and that 3 are sometimes necessary (lower bound), for catching an adversarial evader on any polyhedral surface with genus zero. Generalizing this bound to surfaces of genus

g

, we prove the sufficiency of (4

g

 + 4) pursuers. Finally, we show that 4 pursuers also suffice under the “weighted region” constraints where the movement costs through different regions of the (genus zero) surface have (different) multiplicative weights.

Let

P

be a

d

-dimensional

n

-point set. A partition

$\mathcal{T}$

of

P

is called a

Tverberg

partition if the convex hulls of all sets in

$\mathcal{T}$

intersect in at least one point. We say

$\mathcal{T}$

is

t-tolerated

if it remains a Tverberg partition after deleting any

t

points from

P

. Soberón and Strausz proved that there is always a

t

-tolerated Tverberg partition with ⌈

n

/ (

d

 + 1)(

t

 + 1) ⌉ sets. However, so far no nontrivial algorithms for computing or approximating such partitions have been presented.

For

d

 ≤ 2, we show that the Soberón-Strausz bound can be improved, and we show how the corresponding partitions can be found in polynomial time. For

d

 ≥ 3, we give the first polynomial-time approximation algorithm by presenting a reduction to the (untolerated) Tverberg problem. Finally, we show that it is coNP-complete to determine whether a given Tverberg partition is

t

-tolerated.

Abstract Voronoi diagrams [15,16] are based on bisecting curves enjoying simple combinatorial properties, rather than on the geometric notions of sites and distance. They serve as a unifying concept. Once the bisector system of any concrete type of Voronoi diagram is shown to fulfill the AVD axioms, structural results and efficient algorithms become available without further effort; for example, the first optimal algorithms for constructing nearest Voronoi diagrams of disjoint convex objects, or of line segments under the Hausdorff metric, have been obtained this way [18]. One of these axioms stated that all Voronoi regions must be pathwise connected, a property quite useful in divide&conquer and randomized incremental construction algorithms. Yet, there are concrete Voronoi diagrams where this axiom fails to hold.

In this paper we consider, for the first time, abstract Voronoi diagrams with disconnected regions. By combining the randomized incremental construction technique [18] with trapezoidal decomposition [21] we obtain an algorithm that runs in expected time

$O(s^2 n \sum_{j=3}^n {{m_j}/{j}})$

, where

s

is the maximum number of faces a Voronoi region in a subdiagram of three sites can have, and

m

j

denotes the average number of faces per region in any subdiagram of

j

sites. In the connected case, where

s

 = 1 = 

m

j

, this results in the known optimal bound

$O( n \ \sum_{j=3}^n 1/j) \ = \ O(n \log n)$

.

We study the problem of visibility in polyhedral terrains in the presence of multiple viewpoints. We consider three fundamental visibility structures: the visibility map, the colored visibility map, and the Voronoi visibility map. We study the complexity of each structure for both 1.5D and 2.5D terrains, and provide efficient algorithms to construct them. Our algorithm for the visibility map in 2.5D terrains improves on the only existing algorithm in this setting.

We show that the maximum independent set problem (MIS) on an

n

-vertex graph can be solved in 1.2002

n

n

O

(1)

time and polynomial space, which is even faster than Robson’s 1.2109

n

n

O

(1)

-time exponential-space algorithm published in 1986. We also obtain improved algorithms for MIS in graphs with maximum degree 6 and 7. Our algorithms are obtained by effectively using fast algorithms for MIS in low-degree graphs and making careful analyses for MIS in high-degree graphs.

We reduce (in polynomial time) the enumeration of minimal dominating sets in interval and permutation graphs to the enumeration of paths in directed acyclic graphs(DAGs). As a consequence, we can enumerate with linear delay, after a polynomial time pre-processing, minimal dominating sets in interval and permutation graphs. We can also count them in polynomial time. This improves considerably upon previously known results on interval graphs, and up to our knowledge no output polynomial time algorithm for the enumeration of minimal dominating sets and their counting were known for permutation graphs.

We introduce and study the problem

Mutual Planar Duality

, which asks for planar graphs

G

1

and

G

2

whether

G

1

can be embedded such that its dual is isomorphic to

G

2

. We show NP-completeness for general graphs and give a linear-time algorithm for biconnected graphs.

We consider the

common dual relation

~, where

G

1

~

G

2

if and only they admit embeddings that result in the same dual graph. We show that ~ is an equivalence relation on the set of biconnected graphs and devise a succinct, SPQR-tree-like representation of its equivalence classes. To solve

Mutual Planar Duality

for biconnected graphs, we show how to do isomorphism testing for two such representations in linear time.

A special case of

Mutual Planar Duality

is testing whether a graph is self-dual. Our algorithm can handle the case of biconnected graphs in linear time and our NP-hardness proof extends to self-duality and also to map self-duality testing (which additionally requires to preserve the embedding).

The NP-hard

Subset Interconnection Design

problem is motivated by applications in designing vacuum systems and scalable overlay networks. It has as input a set

V

and a collection of subsets

V

1

,

V

2

, …,

V

m

, and asks for a minimum-cardinality edge set

E

such that for the graph

G

 = (

V

,

E

) all induced subgraphs

G

[

V

1

],

G

[

V

2

], …,

G

[

V

m

] are connected. It has also been studied under the name

Minimum Topic-Connected Overlay

. We study

Subset Interconnection Design

in the context of polynomial-time data reduction rules that preserve optimality. Our contribution is threefold: First, we point out flaws in earlier polynomial-time data reduction rules. Second, we provide a fixed-parameter tractability result for small subset sizes and tree-like output graphs. Third, we show linear-time solvability in case of a constant number

m

of subsets, implying fixed-parameter tractability for the parameter

m

. To achieve our results, we elaborate on polynomial-time data reduction rules (partly “repairing” previous flawed ones) which also may be of practical use in solving

Subset Interconnection Design

.

We introduce a method of applying Myhill-Nerode methods from formal language theory to hypergraphs and show how this method can be used to obtain the following parameterized complexity results.

Hypergraph Cutwidth

(deciding whether a hypergraph on

n

vertices has cutwidth at most

k

) is linear-time solvable for constant

k

.

For hypergraphs of constant

incidence treewidth

(treewidth of the incidence graph),

Hypertree Width

and variants cannot be solved by simple finite tree automata. The proof leads us to conjecture that

Hypertree Width

is W[1]-hard for this parameter.

We study the problem of augmenting a weighted graph by inserting edges of bounded total cost while minimizing the diameter of the augmented graph. Our main result is an FPT 4-approximation algorithm for the problem.

Let

$\cal{D}$

= {

d

1

,

d

2

,...

d

D

} be a given set of

D

string documents of total length

n

. Our task is to index

$\cal{D}$

such that the

k

most relevant documents for an online query pattern

P

of length

p

can be retrieved efficiently. There exist linear space data structures of

O

(

n

) words for answering such queries in optimal

O

(

p

 + 

k

) time. In this paper, we describe a compact index of size |

CSA

|+

n

log

D

 + 

o

(

n

log

D

) bits with near optimal time,

O

(

p

 + 

k

log

*

n

), for the basic relevance metric

term-frequency

, where |

CSA

| is the size (in bits) of a compressed full-text index of

$\cal{D}$

, and log

*

n

is the iterated logarithm of

n

.

Starting with Munro and Paterson (1980), the selection or median-finding problem has been extensively studied in the read-only memory model and in streaming models. Munro and Paterson’s deterministic algorithm and its subsequent refinements require at least polylogarithmic or logarithmic space, whereas the algorithms by Munro and Raman (1996) and Raman and Ramnath (1999) can be made to use just

O

(1) storage cells but take

O

(

n

1 + 

ε

) time for an arbitrarily small constant

ε

 > 0.

In this paper, we show that faster selection algorithms in read-only memory are possible if the input is a sequence of integers. For example, one algorithm uses

O

(1) storage cells and takes

$O(n\lg U)$

time where

U

is the universe size. Another algorithm uses

O

(1) storage cells and takes

$O(n\lg n\lg\lg U)$

time. We also describe an

O

(

n

)-time algorithm for finding an approximate median using

$O(\lg^\epsilon U)$

storage cells.

All our algorithms are simple and deterministic. Interestingly, one of our algorithms is inspired by ‘centroids’ of binary trees and finds an approximate median by repeatedly invoking a textbook algorithm for the ‘majority’ problem. This technique could be of independent interest.

In this paper we introduce

trajectory-based labeling

, a new variant of dynamic map labeling where a movement trajectory for the map viewport is given. We define a general labeling model and study the active range maximization problem in this model. The problem is

$\cal NP$

-complete and

$\mathcal W[1]$

-hard. In the restricted, yet practically relevant case that no more than

k

labels can be active at any time, we give polynomial-time algorithms. For the general case we present a practical ILP formulation with an experimental evaluation as well as approximation algorithms.

We perform a thorough study of various characteristics of the asynchronous push-pull protocol for spreading a rumor on Erdős-Rényi random graphs

G

n

,

p

, for any

p

 > 

c

ln (

n

)/

n

,

c

 > 1. In particular, we prove tight bounds for the total time that is needed until the information has spread to all nodes. Moreover, we quantify precisely the robustness of the protocol with respect to transmission and node failures.

In this paper, we study

unit cost buyback problem

, i.e., the buyback problem with fixed cancellation cost for each cancelled item. The input is a sequence of elements

e

1

,

e

2

,…,

e

n

, each of which has a weight

w

(

e

i

). We assume that weights have an upper and a lower bound, i.e.,

l

 ≤ 

w

(

e

i

) ≤ 

u

for any

i

. Given the

i

th element

e

i

, we either accept

e

i

or reject it with no cost, subject to some constraint on the set of accepted elements. In order to accept a new element

e

i

, we could cancel some previous selected elements at a cost which is proportional to the number of elements canceled. Our goal is to maximize the profit, i.e., the sum of the weights of elements accepted (and not canceled) minus the total cancellation cost occurred. We construct optimal online algorithms and prove that they are the best possible, when the constraint is a matroid constraint or the unweighted knapsack constraint.

We consider the random phone call model introduced by Demers et al. [8], which is a well-studied model for information dissemination on networks. One basic protocol in this model is the so-called

Push

protocol which proceeds in synchronous rounds. Starting with a single node which knows of a rumor, every informed node calls a random neighbor and informs it of the rumor in each round. The

Push-Pull

protocol works similarly, but additionally every uninformed node calls a random neighbor and may learn the rumor from that neighbor.

While it is well-known that both protocols need Θ(log

n

) rounds to spread a rumor on a complete network with

n

nodes, we are interested by how much we can speed up the spread of the rumor by enabling nodes to make more than one call in each round. We propose a new model where the number of calls of a node

u

is chosen independently according to a probability distribution

R

with bounded mean determined at the beginning of the process. We provide both lower and upper bounds on the rumor spreading time depending on statistical properties of

R

such as the mean or the variance. If

R

follows a power law distribution with exponent ∈ (2,3), we show that the

Push-Pull

protocol spreads a rumor in Θ(loglog

n

) rounds.

We show that the value of a finite-state concurrent reachability game can be approximated to arbitrary precision in

TFNP[NP]

, that is, in the polynomial time hierarchy. Previously, no better bound than

PSPACE

was known for this problem. The proof is based on formulating a variant of the state reduction algorithm for Markov chains using arbitrary precision floating point arithmetic and giving a rigorous error analysis of the algorithm.

We address the problem of computing a Walrasian equilibrium price in an ascending auction with gross substitutes valuations. In particular, an auction market is considered where there are multiple differentiated items and each item may have multiple units. Although the ascending auction is known to find an equilibrium price vector in finite time, little is known about its time complexity. The main aim of this paper is to analyze the time complexity of the ascending auction globally and locally, by utilizing the theory of discrete convex analysis. An exact bound on the number of iterations is given in terms of the ℓ

 ∞ 

distance between the initial price vector and an equilibrium, and an efficient algorithm to update a price vector is designedbased on a min-max theorem for submodular function minimization.

We study the online pricing problem where there are

m

identical items on sale and a sequence of users

u

1

,

u

2

,… arrive one by one. Each

u

i

has a non-increasing acceptable price function

ϕ

i

(·) where

ϕ

i

(

x

) is the highest unit price

u

i

is willing to pay for

x

items. Upon the arrival of a user, the seller needs to decide the number of items to be sold to the user and at what price. The goal is to maximize the revenue of the seller, which is the sum of money paid by all users.

For the case when the items are divisible and can be sold fractionally, we improve the results of Zhang

et al.

[19]. We design a new deterministic algorithm

$\mathcal{D}_p$

-DIV and prove that it has competitive ratio

$O( \prod_{j=1}^{\log^* h - 1} \log^{(j)} h )$

where

h

is the highest unit price a user is willing to pay; our algorithm is substantially better than the

$O(h^{ 3 \log_2^{-1/2} h })$

-competitive algorithm of Zhang

et al.

We also prove that no randomized algorithm can do better than Ω(log

h

)-competitive.

For the case when items are indivisible, there is no known result. We show in this paper that any deterministic algorithm for this case must have competitive ratio at least Ω(

h

)-competitive. Then, we give the first competitive randomized algorithm

mathcalR

p

-indiv with competitive ratio

$O( \prod_{j=1}^{\log^* h - 1} \log^{(j)} h )$

. If

h

is known ahead of time, we can reduce the competitive ratio to

O

(log

h

). Besides, we prove that no randomized algorithm can do better than Ω(log

h

)-competitive.

In recent years a large number of problems have been considered in external memory models of computation, where the complexity measure is the number of blocks of data that are moved between slow external memory and fast internal memory (also called I/Os). In practice, however, internal memory time often dominates the total running time once I/O-efficiency has been obtained. In this paper we study algorithms for fundamental problems that are simultaneously I/O-efficient and internal memory efficient in the RAM model of computation.

Given a partition of an

n

element set into equivalence classes, we consider time-space tradeoffs for representing it to support the query that asks whether two given elements are in the same equivalence class. This has various applications including for testing whether two vertices are in the same connected component in an undirected graph or in the same strongly connected component in a directed graph.

We consider the problem in several models.

Concerning labeling schemes where we assign labels to elements and the query is to be answered just by examining the labels of the queried elements (without any extra space): if each vertex is required to have a unique label, then we show that a label space of

$\sum_{i=1}^n \lfloor{n \over i} \rfloor$

is necessary and sufficient. In other words,

$\lg n + \lg \lg n + O(1)$

bits of space are necessary and sufficient for representing each of the labels. This slightly strengthens the known lower bound and is in contrast to the known necessary and sufficient bound of

$\lceil \lg n \rceil$

for the label length, if each vertex need not get a unique label.

Concerning succinct data structures for the problem when the

n

elements are to be uniquely assigned labels from label set {1,…,

n

}, we first show that

$\Theta(\sqrt n)$

bits are necessary and sufficient to represent the equivalence class information. This space includes the space for implicitly encoding the vertex labels. We can support the query in such a structure in

$O(\lg n)$

time in the standard word RAM model.

We then develop structures where the queries can be answered

in

$O(\lg \lg n)$

time using

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

bits, and

in

O

(1) time using

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

bits of space.

We also develop a dynamic structure that uses

$O(\sqrt n \lg n)$

bits to support equivalence queries and unions in

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

worst case time or

O

(

α

(

n

)) expected amortized time where

α

(

n

) is the inverse Ackermann function.

A Bloom filter is a method for reducing the space (memory) required for representing a set by allowing a small error probability. In this paper we consider a Sliding Bloom Filter: a data structure that, given a stream of elements, supports membership queries of the set of the last

n

elements (a sliding window), while allowing a small error probability and a slackness parameter. The problem of sliding Bloom filters has appeared in the literature in several communities, but this work is the first theoretical investigation of it.

We formally define the data structure and its relevant parameters and analyze the time and memory requirements needed to achieve them. We give a low space construction that runs in

O

(1) time per update with high probability (that is, for all sequences with high probability all operations take constant time) and provide an almost matching lower bound on the space that shows that our construction has the best possible space consumption up to an additive lower order term.

Let

G

denote an

n

-vertex two-directional orthogonal ray graph. A bicolored 2D representation of

G

requires only

O

(

n

) space, regardless of the number of edges in

G

. Given such a compact representation of

G

, and a (possibly negative) weight for each vertex, we show how to compute a maximum weight matching of

G

in

O

(

n

log

2

n

) time. The classic problem of scheduling weighted unit tasks with release times and deadlines is a special case of this problem, and we obtain an

O

(

n

log

n

) time bound for this special case. As an application of our more general result, we obtain an

O

(

n

log

2

n

)-time algorithm for computing the VCG outcome of a sealed-bid unit-demand auction in which each item has two associated numerical parameters (e.g., third-party “quality” and “seller reliability” scores) and each bid specifies the amount an agent is willing to pay for any item meeting specified lower bound constraints with respect to these two parameters.

Klavík et al. [arXiv:1207.6960] recently introduced a generalization of recognition called the

bounded representation problem

which we study for the classes of interval and proper interval graphs. The input gives a graph

G

and in addition for each vertex

v

two intervals

$\mathfrak{L}_v$

and

$\mathfrak{R}_v$

called

bounds

. We ask whether there exists a bounded representation in which each interval

$\mathfrak{I}_v$

has its left endpoint in

$\mathfrak{L}_v$

and its right endpoint in

$\mathfrak{R}_v$

. We show that the problem can be solved in linear time for interval graphs and in quadratic time for proper interval graphs.

Robert’s Theorem states that the classes of proper interval graphs and unit interval graphs are equal. Surprisingly, the bounded representation problem is polynomially solvable for proper interval graphs and

NP

-complete for unit interval graphs [Klavík et al., arxiv:1207.6960]. So unless

P

=

NP

, the proper and unit interval representations behave very differently.

The bounded representation problem belongs to a wider class of restricted representation problems. These problems are generalizations of the well-understood recognition problem, and they ask whether there exists a representation of

G

satisfying some additional constraints. The bounded representation problems generalize many of these problems.

We study the induced subgraph isomorphism problem and the general subgraph isomorphism problem for small pattern graphs.

We present a new general method for detecting induced subgraphs of a host graph isomorphic to a fixed pattern graph by reduction to polynomial testing for non-identity with zero over a field of finite characteristic. It yields new upper time bounds for several pattern graphs on five vertices and provides an alternative combinatorial method for the majority of pattern graphs on four and three vertices. Since our method avoids the large overhead of fast matrix multiplication, it can be of practical interest even for larger pattern graphs.

Next, we derive new upper time bounds on counting the number of isomorphisms between a fixed pattern graph with an independent set of size

s

and a subgraph of the host graph. We also consider a weighted version of the counting problem, when one counts the number of isomorphisms between the pattern graph and lightest subgraphs, providing a slightly slower combinatorial algorithm.

Say that an edge of a graph

G

dominates itself and every other edge sharing a vertex of it. An edge dominating set of a graph

G

 = (

V

,

E

) is a subset of edges

E

′ ⊆ 

E

which dominates all edges of

G

. In particular, if every edge of

G

is dominated by exactly one edge of

E

′ then

E

′ is a dominating induced matching. It is known that not every graph admits a dominating induced matching, while the problem to decide if it does admit it is NP-complete. In this paper we consider the problems of finding a minimum weighted dominating induced matching, if any, and counting the number of dominating induced matchings of a graph with weighted edges. We describe an exact algorithm for general graphs that runs in

O

*

(1.1939

n

) time and polynomial (linear) space, for solving these problems. This improves over the existing exact algorithms for the problems in consideration.

In this paper, we study the approximability of the metric Traveling Salesman Problem (TSP) and prove new explicit inapproximability bounds for that problem. The best up to now known hardness of approximation bounds were 185/184 for the symmetric case (due to Lampis) and 117/116 for the asymmetric case (due to Papadimitriou and Vempala). We construct here two new bounded occurrence CSP reductions which improve these bounds to 123/122 and 75/74, respectively. The latter bound is the first improvement in more than a decade for the case of the asymmetric TSP. One of our main tools, which may be of independent interest, is a new construction of a bounded degree wheel amplifier used in the proof of our results.

The 2-opt heuristic is a very simple local search heuristic for the traveling salesman problem. While it usually converges quickly in practice, its running-time can be exponential in the worst case.

In order to explain the performance of 2-opt, Englert, Röglin, and Vöcking (

Algorithmica

, to appear) provided a smoothed analysis in the so-called one-step model on

d

-dimensional Euclidean instances. However, translating their results to the classical model of smoothed analysis, where points are perturbed by Gaussian distributions with standard deviation

σ

, yields a bound that is only polynomial in

n

and 1/

σ

d

.

We prove bounds that are polynomial in

n

and 1/

σ

for the smoothed running-time with Gaussian perturbations. In particular our analysis for Euclidean distances is much simpler than the existing smoothed analysis.

Given a set of points

Q

in the plane, define the

$\frac{r}{2}$

-

Disk Graph

,

Q

(

r

), as a generalized version of the Unit Disk Graph: the vertices of the graph is

Q

and there is an edge between two points in

Q

iff the distance between them is at most

r

. In this paper, motivated by applications in wireless sensor networks, we study the following geometric problem of color-spanning sets: given

n

points with

m

colors in the plane, choosing

m

points

P

with distinct colors such that the

$\frac{r}{2}$

-Disk Graph,

P

(

r

), is connected and

r

is minimized. When at most two points are of the same color

c

i

(or, equivalently, when a color

c

i

spans at most two points), we prove that the problem is NP-hard to approximate within a factor 3 − 

ε

. And we present a tight factor-3 approximation for this problem. For the more general case when each color spans at most

k

points, we present a factor-(2

k

-1) approximation. Our solutions are based on the applications of the famous Hall’s Marriage Theorem on bipartite graphs, which could be useful for other problems.

In this paper, we study the

train delivery

problem which is a generalization of the bin packing problem, and is also equivalent to a one dimensional version of the vehicle routing problem with unsplittable demands. We give an APTAS for the general problem with time complexity

$O(n^{O(\epsilon^{-4})})$

, which is better than the previous one

$O(n^{(\frac{1}{\epsilon})^{O(\frac{1}{\epsilon})}})$

, where

n

is the number of input elements.

The (distance)

k

-sector is a generalization of the concept of bisectors proposed by Asano, Matoušek and Tokuyama. We prove the uniqueness of the 4-sector of two points in the Euclidean plane. Despite the simplicity of the unique 4-sector (which consists of a line and two parabolas), our proof is quite non-trivial. We begin by establishing uniqueness in a small region of the plane, which we show may be perpetually expanded afterward.

Given a polyhedron, the number of its unfolding is obtained by the Matrix-Tree Theorem. For example, a cube has 384 ways of unfolding (i.e., cutting edges). By omitting mutually isomorphic unfoldings, we have 11 essentially different (i.e., nonisomorphic) unfoldings. In this paper, we address how to count the number of nonisomorphic unfoldings for any (i.e., including nonconvex) polyhedron. By applying this technique, we also give the numbers of nonisomorphic unfoldings of all regular-faced convex polyhedra (i.e., Platonic solids, Archimedean solids, Johnson-Zalgaller solids, Archimedean prisms, and antiprisms), Catalan solids, bipyramids and trapezohedra. For example, while a truncated icosahedron (a Buckminsterfullerene, or a soccer ball fullerene) has 375,291,866,372,898,816, 000 (approximately 3.75 ×10

20

) ways of unfolding, it has 3,127,432,220, 939,473,920 (approximately 3.13 ×10

18

) nonisomorphic unfoldings. A truncated icosidodecahedron has 21,789,262,703,685,125,511,464,767,107, 171,876,864,000 (approximately 2.18 ×10

40

) ways of unfolding, and has 181,577,189,197,376, 045,928,994,520,239,942,164,480 (approximately 1.82 ×10

38

) nonisomorphic unfoldings.

For a given set of

n

colored points with

k

colors in the plane, we study the problem of computing the smallest color-spanning axis-parallel square. First, for a dynamic set of colored points on the real line, we propose a dynamic structure with

O

(log

2

n

) update time per insertion and deletion for maintaining the smallest color-spanning interval. Next, we use this result to compute the smallest color-spanning square. Although we show there could be Ω(

kn

) minimal color-spanning squares, our algorithm runs in

O

(

n

log

2

n

) time and

O

(

n

) space.

We consider the problem of planning a shortest tour through a collection of neighborhoods in the plane, where each neighborhood is a disk whose radius is an

i

.

i

.

d

. random variable drawn from a known probability distribution. This is a

stochastic

version of the classic traveling salesman problem with neighborhoods (TSPN). Planning such tours under uncertainty, a fundamental problem in its own right, is motivated by a number of applications including the following data gathering problem in sensor networks: a robotic

data mule

needs to collect data from

n

geographically distributed wireless sensor nodes whose communication range

r

is a random variable influenced by environmental factors.

We propose a polynomial-time algorithm that achieves a factor

O

(loglog

n

) approximation of the

expected length of an optimal tour

. In data mule applications, the problem has an additional complexity: the radii of the disks are only

revealed

when the robot reaches the disk boundary (transmission success). For this

online

version of the stochastic TSPN, we achieve an approximation ratio of

O

(log

n

). In the special case, where the disks with their

mean radii

are disjoint, we achieve an

O

(1) approximation even for the online case.

We study the problem of finding and characterizing subgraphs with small

bipartiteness ratio

. We give a bicriteria approximation algorithm

SwpDB

such that if there exists a subset

S

of volume at most

k

and bipartiteness ratio

θ

, then for any 0 < 

ε

 < 1/2, it finds a set

S

′ of volume at most 2

k

1 + 

ε

and bipartiteness ratio at most

$4\sqrt{\theta/\epsilon}$

. By combining a truncation operation, we give a local algorithm

LocDB

, which has asymptotically the same approximation guarantee as the algorithm

SwpDB

on both the volume and bipartiteness ratio of the output set, and runs in time

O

(

ε

2

θ

− 2

k

1 + 

ε

ln

3

k

), independent of the size of the graph. Finally, we give a spectral characterization of the small dense bipartite-like subgraphs by using the

k

th

largest

eigenvalue of the Laplacian of the graph.

Čech complexes reveal valuable topological information about point sets at a certain scale in arbitrary dimensions, but the sheer size of these complexes limits their practical impact. While recent work introduced approximation techniques for filtrations of (Vietoris-)Rips complexes, a coarser version of Čech complexes, we propose the approximation of Čech filtrations directly.

For fixed dimensional point set

S

, we present an approximation of the Čech filtration of

S

by a sequence of complexes of size linear in the number of points. We generalize well-separated pair decompositions (WSPD) to well-separated simplicial decomposition (WSSD) in which every simplex defined on

S

is covered by some element of WSSD. We give an efficient algorithm to compute a linear-sized WSSD in fixed dimensional spaces. Using a WSSD, we then present a linear-sized approximation of the filtration of Čech complex of

S

.

We also present a generalization of the known fact that the Rips complex approximates the Čech complex by a factor of

$\sqrt{2}$

. We define a class of complexes that interpolate between Čech and Rips complexes and that, given any parameter

ε

 > 0, approximate the Čech complex by a factor (1 + 

ε

). Our complex can be represented by

O

(

n

⌈1/2

ε

⌉

) simplices, up to purely combinatorial operations, without any hidden dependence on the ambient dimension of the point set. Our results are based on an interesting link between Čech complex and coresets for minimum enclosing ball of high-dimensional point sets. As a consequence of our analysis, we show improved bounds on coresets that approximate the radius of the minimum enclosing ball.

We show that #SAT is polynomial-time tractable for classes of CNF formulas whose incidence graphs have bounded symmetric clique-width (or bounded clique-width, or bounded rank-width). This result strictly generalizes polynomial-time tractability results for classes of formulas with signed incidence graphs of bounded clique-width and classes of formulas with incidence graphs of bounded modular treewidth, which were the most general results of this kind known so far.

This work concerns two kinds of spatial equilibria. Given a multiset of

n

points in Euclidean space equipped with the ℓ

2

-norm, we call a location a

plurality point

if it is closer to at least as many given points as any other location. A location is called a

Condorcet point

if there exists no other location which is closer to an absolute majority of the given points. In

d

-dimensional Euclidean space ℝ

d

, we show that the plurality points and the Condorcet points are equivalent. When the given points are not collinear, the Condorcet point (which is also the plurality point) is unique in ℝ

d

if such a point exists. To the best of our knowledge, no efficient algorithm has been proposed for finding the point if the dimension is higher than one. In this paper, we present an

O

(

n

d

 − 1

log

n

)-time algorithm for any fixed dimension

d

 ≥ 2.

Patterned self-assembly tile set synthesis (PATS) aims at finding a minimum tile set to uniquely self-assemble a given rectangular pattern. For

k

 ≥ 1,

k

-PATS is a variant of PATS that restricts input patterns to those with at most

k

colors. We prove the

$\mathcal{NP}$

-hardness of 29-PATS, where the best known is that of 60-PATS.

Kademlia [3] is currently the most widely used searching algorithm in p2p (peer-to-peer) networks. This work studies an essential question about Kademlia from a mathematical perspective: how long does it take to locate a node in the network? To answer it, we introduce a random graph

$\mathcal{K}$

and study how many steps are needed to locate a given vertex in

$\mathcal{K}$

using Kademlia’s algorithm, which we call the

routing time

. Two slightly different versions of

$\mathcal{K}$

are studied. In the first one, vertices of

$\mathcal{K}$

are labeled with fixed IDs. In the second one, vertices are assumed to have randomly selected IDs. In both cases, we show that the routing time is about

c

log

n

, where

n

is the number of nodes in the network and

c

is an explicitly described constant.

We consider the

generalized minimum Manhattan network problem

(GMMN). The input to this problem is a set

R

of

n

pairs of terminals, which are points in ℝ

2

. The goal is to find a minimum-length rectilinear network that connects every pair in

R

by a

Manhattan path

, that is, a path of axis-parallel line segments whose total length equals the pair’s Manhattan distance. This problem is a natural generalization of the extensively studied

minimum Manhattan network problem

(MMN) in which

R

consists of all possible pairs of terminals. Another important special case is the well-known

rectilinear Steiner arborescence problem

(RSA). As a generalization of these problems, GMMN is NP-hard. No approximation algorithms are known for general GMMN. We obtain an

O

(log

n

)-approximation algorithm for GMMN. Our solution is based on a stabbing technique, a novel way of attacking Manhattan network problems. Some parts of our algorithm generalize to higher dimensions, yielding a simple

O

(log

d

 + 1

n

)-approximation algorithm for the problem in arbitrary fixed dimension

d

. As a corollary, we obtain an exponential improvement upon the previously best

O

(

n

ε

)-ratio for MMN in

d

dimensions [ESA’11]. En route, we show that an existing

O

(log

n

)-approximation algorithm for 2D-RSA generalizes to higher dimensions.

Let

P

be an undirected path graph of

n

vertices. Each edge of

P

has a positive length and a constant capacity. Every vertex has a nonnegative supply, which is an unknown value but is known to be in a given interval. The goal is to find a point on

P

to build a facility and move all vertex supplies to the facility such that the maximum regret is minimized. The previous best algorithm solves the problem in

O

(

n

log

2

n

) time and

O

(

n

log

n

) space. In this paper, we present an

O

(

n

log

n

) time and

O

(

n

) space algorithm, and our approach is based on new observations and algorithmic techniques.