Frontiers in Algorithmics

A

certifying algorithm

is an algorithm that produces with each output, a

certificate

or witness (easy-to-verify proof) that the particular output has not been compromised by a bug. A user of a certifying program

P

(= the implementation of a certifying algorithm) inputs

x

, receives an output

y

and a certificate

w

, and then checks, either manually or by use of a checking program, that

w

proves that

y

is a correct output for input

x

. In this way, he/she can be sure of the correctness of the output without having to trust

P

. We refer the reader to the recent survey paper [9] for a detailed discussion of certifying algorithms.

The talk will review recent results and algorithmic challenges for computational geometry problems in the context of uncertain data. This is an active area of investigation in the database community, and we introduce it through the specifics of the maximal elements problem (called the skyline problem in the database community): Rather than being a point, an uncertain object is a set of points called instances, each with an associated probability; instances of the same uncertain object can be geometrically far from each other, and are mutually exclusive (i.e., at most one of them can occur). For this version of the maximal elements problem, the input is a collection of

m

uncertain objects, whose total number of instances is

n

, and the problem is to compute for each of these

n

instances the probability that it is a maximal point, i.e., that it occurs for its own object and is not dominated by any occurring instance from another object.

With a long-run accumulation of IT technologies, cloud computing becomes a new revolution after PC revolution in 1980s, the Internet revolution in 1990s, and the mobile Internet revolution in 2000s. Cloud computing is a paradigm of Internet computing, which takes software as a service oriented to a number of users with changing requirements from time to time, at the same time, takes the response of a requirement as an up-to-date best effort rather than a unique precise one. It is changing the way we share data, information and knowledge.

Services support direct reusing of application programs instead of software deployment, and improve usability of resource sharing. Clouds can be regarded as an enabler for interoperation of large scale service provisioning. Therefore, assembling of software became services aggregation under the mature understanding of interoperability.

Services interoperation may happen between a user (group) and a service, or among services. Users or their groups, services or their aggregations are all called agents here. The description of interoperability of agents focuses on three issues: their role, goal, and combination of services. The role issue characterizes the organization, roles, and actors of an agent, and describes the interaction and cooperation among them. The goal issue depicts the decomposition of goals and determines the constraint relationship among goals. While the two issues compose the problem domain, the third issue is related to the solution domain, in which process distinguishes atomic processes, and composite processes, and defines the input/output together with precondition/effect of processes respectively, the service guides the construction of service chains and aggregation of resources. Usually, the description in problem domain is qualitative, while the specification in solution domain is quantitative.

In this paper, we study pricing models for multi-slot advertisements, where advertisers can bid to place links to their sales webpages at one or multiple slots on a webpage, called the multi-slot AD auction problem. We develop and analyze several important mechanisms, including the VCG mechanism for multi-slot ads auction, the optimal social welfare solution, as well as two weighted GSP-like protocols (mixed and hybrid). Furthermore, we consider that forward-looking Nash equilibrium and prove its existence in the weighted GSP-like pricing protocols.

We prove properties and compare revenue of those different pricing models via analysis and simulation.

We consider the task of designing a truthful auction mechanism for CPU time scheduling problem. There are

m

commodities (time slots)

T

 = {

t

1

,

t

2

, ...,

t

m

} for

n

buyers

I

 = {1,2,...,

n

}. Each buyer requires a number of time slots

s

i

for its task. The valuation function of buyer

i

for a bundle of time slots

T

i

is

v

i

(

T

i

) = 

w

i

(

m

 − 

t

), where

t

is the last time slot in

T

i

and |

T

i

| = 

s

i

. The utility

u

i

of buyer

i

is

v

i

(

T

i

) − 

p

(

T

i

). It is well-known that Vickrey-Clarke-Groves (VCG) mechanism gives the incentive to bid truthfully. Although optimal social welfare is computationally feasible in CPU time scheduling problem, VCG mechanism may produce low revenue. We design an auction which also maintains the incentives for bidders to bid truthfully. In addition, we perform simulations and observe that our truthful mechanism produces more revenue than VCG on average.

In this paper, we consider the rank aggregation problem for information retrieval over Web making use of a kind of metric, the coherence, which considers both the normalized Kendall-

τ

distance and the size of overlap between two partial rankings. In general, the top-

d

coherence aggregation problem is defined as: given collection of partial rankings Π = {

τ

1

,

τ

2

, ⋯ ,

τ

K

}, how to find a final ranking

π

with specific length

d

, which maximizes the total coherence

$\Phi(\pi,\Pi)=\sum_{i=1}^K \Phi(\pi,\tau_i)$

. The corresponding complexity and algorithmic issues are discussed in this paper. Our main technical contribution is a polynomial time approximation scheme (PTAS) for a restricted top-

d

coherence aggregation problem.

Minimum Common String Partition (MCSP) has drawn much attention due to its application in genome rearrangement. In this paper, we investigate three variants of MCSP:

MCSP

c

, which requires that there are at most

c

symbols in the alphabet;

d

-MCSP, which requires the occurrence of each symbol to be bounded by

d

; and

x

-balance MCSP, which requires the length of blocks not being

x

away from the average length. We show that

MCSP

c

is NP-hard when

c

 ≥ 2. As for

d

-MCSP, we present an FPT algorithm which runs in

O

*

((

d

!)

k

) time. As it is still unknown whether an FPT algorithm only parameterized on

k

exists for the general case of MCSP, we also devise an FPT algorithm for the special case

x

-balance MCSP parameterized on both

k

and

x

.

Maximal Strip Recovery (MSR) is an optimization problem proposed by Zheng, Zhu, and Sankoff for reliably recovering syntenic blocks from genomic maps in the midst of noise and ambiguities. Given d genomic maps as sequences of gene markers, the objective of MSR-

d

is to find d subsequences, one subsequence of each genomic map, such that the total length of syntenic blocks in these subsequences is maximized. In our recent paper entitled “Inapproximability of Maximal Strip Recovery” in ISAAC 2009, we proved that MSR-

d

is APX-hard for any constant

d

 ≥ 2, and presented the first explicit lower bounds for approximating MSR-2, MSR-3, andMSR-4, even for the most basic version of the problem in which all markers are distinct and appear in positive orientation in each genomic map. In this paper, we present several further inapproximability results for MSR-

d

and its variants CMSR-

d

,

δ

-gap-MSR-

d

, and

δ

-gap-CMSR-

d

. One of our main results is that MSR-d is NP-hard to approximate within Ω(

d

/ log

d

) even if all markers appear in positive orientation in each genomic map. From the other direction, we show that there is a polynomial-time 2

d

-approximation algorithm for MSR-

d

even if d is not a constant but is part of the input.

In this paper, we study an interesting geometric partition problem, called optimal field splitting, which arises in Intensity-Modulated Radiation Therapy (IMRT). In current clinical practice, a multileaf collimator (MLC) with a maximum leaf spread constraint is used to deliver the prescribed radiation intensity maps (IMs). However, the maximum leaf spread of an MLC may require to split a large IM into several overlapping sub-IMs with each being delivered separately. We develop an efficient algorithm for solving the field splitting problem while minimizing the total variation of the resulting sub-IMs, thus improving the treatment delivery efficiency. Our basic idea is to formulate the field splitting problem as computing a shortest path in a directed acyclic graph, which expresses a special “layered” structure. The edge weights in the graph can be computed by solving an optimal vector decomposition problem using local searching and the proximity scaling technique as we can prove the L

$^\natural$

-convexity and totally unimodularity of the problem. Moreover, the edge weights of the graph satisfy the Monge property, which enables us to solve this shortest path problem by examining only a small portion of the graph, yielding a time-efficient algorithm.

We investigate the problems of scheduling

n

weighted jobs to

m

identical machines with availability constraints. We consider two different models of availability constraints: the preventive model where the unavailability is due to preventive machine maintenance, and the fixed job model where the unavailability is due to a priori assignment of some of the

n

jobs to certain machines at certain times. Both models have applications such as turnaround scheduling or overlay computing. In both models, the objective is to minimize the total weighted completion time. We assume that

m

is a constant, and the jobs are non-resumable. For the preventive model, it has been shown that there is no approximation algorithm if all machines have unavailable intervals even when

w

i

 = 

p

i

for all jobs. In this paper, we assume there is one machine permanently available and the processing time of each job is equal to its weight for all jobs. We develop the first PTAS when there are constant number of unavailable intervals. One main feature of our algorithm is that the classification of large and small jobs is with respect to each individual interval, thus not fixed. This classification allows us (1) to enumerate the assignments of large jobs efficiently; (2) and to move small jobs around without increasing the objective value too much, and thus derive our PTAS. Then we show that there is no FPTAS in this case unless

P

 = 

NP

.

For fixed job model, we first show that if job weights are arbitrary then there is no constant approximation for a single machine with 2 fixed jobs or for two machines with one fixed job on each machine, unless

P

 = 

NP

. As the preventive model, we assume that the weight of a job is the same as its processing time for all jobs. We show that the PTAS for the preventive model can be extended to solve this problem when the number of fixed jobs and the number of machines are both constants.

This paper studies the space complexity of the

ε

-approximate quantiles problem, which asks for some data structure that enables us to determine, after reading a whole data stream, a

φ

-quantile (for any 0 ≤ 

φ

 ≤ 1) of the stream within some error bound

ε

. The best known algorithm for the problem uses

$O(\frac{1}{\varepsilon}\log \varepsilon N)$

words where

N

is the total number of items in the stream, or uses

$O(\frac{1}{\varepsilon}\log |U|)$

words where

U

is the set of possible items. It is known that the space lower bound of the problem is

$\Omega(\frac{1}{\varepsilon})$

words; however, improvement of this bound is elusive.

In this paper, we prove that any comparison-based algorithm for finding

ε

-approximate quantiles needs

$\Omega(\frac{1}{\varepsilon} \log \frac{1}{\varepsilon})$

words.

A width-bounded separator is a simple structured hyperplane which divides the given set into two balanced subsets, while at the same time maintaining a low density of the set within a given distance to the hyperplane. For a given set

Q

of

n

grid points in a

d

-dimensional Euclidean space, we develop an improved (Monte carlo) algorithm to find a

w

-wide separator

L

in

$\tilde{O}(n^{1\over d})$

sublinear time such that

Q

has at most

$({d\over d+1}+o(1))n$

points on one either side of the hyperplane

L

, and at most

$c_dwn^{d-1\over d}$

points within

$\frac{w}{2}$

distance to

L

, where

c

d

is a constant for fixed

d

. This improves the existing

$\tilde{O}(n^{2\over d})$

algorithm by Fu and Chen. Furthermore, we derive an

$\Omega(n^{1\over d})$

time lower bound for any randomized algorithm that tests if a given hyperplane satisfies the conditions of width-bounded separator. This lower bound almost matches the upper bound.

A plane graph is a drawing of a planar graph in the plane such that no two edges cross each other. In a rooted plane graph, an outer (directed) edge is designated as the root. For a given positive integer

n

 ≥ 1, we give an

O

(1)-time delay algorithm that enumerates all plane graphs with exactly

n

vertices using

O

(

n

) space. Our algorithm can generates only plane graphs such that the size of each inner face is bounded from above by a prescribed integer

g

 ≥ 3 in the same time and space complexity.

In this paper we describe implementations of two general methods for solving puzzles on

any

structured lattice. We define the puzzle as a graph induced by (finite portion of) the lattice, and apply a back-tracking method for iteratively find all solutions by identifying parts of the puzzle (or transformed versions of them) with subgraphs of the puzzle, such that the entire puzzle graph is covered without overlaps by the graphs of the parts. Alternatively, we reduce the puzzle problem to a submatrix-selection problem, and solve the latter problem by using the “dancing-links” trick of Knuth. A few expediting heuristics are discussed, and experimental results on various lattice puzzles are presented.

Many exact algorithms for

$\mathcal{NP}$

-hard graph problems adopt the old Davis-Putman branch-and-reduce paradigm. The performance of these algorithms often suffers from the increasing number of graph modifications, such as deletions, that reduce the problem instance and have to be “taken back” frequently during the search process. The use of efficient data structures is necessary for fast graph modification modules as well as fast take-back procedures. In this paper, we investigate practical implementation-based aspects of exact algorithms by providing a hybrid graph representation that addresses the take-back challenge and combines the advantage of

${\mathcal{O}}(1)$

adjacency-queries in adjacency-matrices with the advantage of efficient neighborhood traversal in adjacency-lists.

We consider the problem of evaluating certain exponential sums. These sums take the form

$$\sum_{x_1,x_2, \ldots, x_n \in \mathbb{Z}_N } e^{\frac{2 \pi i}{N} {f(x_1,x_2, \ldots, x_n)} },$$

where each

x

i

is summed over a ring ℤ

N

, and

f

(

x

1

,

x

2

,...,

x

n

) is a multivariate polynomial with integer coefficients. We show that the sum can be evaluated in polynomial time in

n

and log

N

when

f

is a quadratic polynomial. This is true even when the factorization of

N

is unknown. Previously, this was known for a prime modulus

N

. On the other hand, for very specific families of polynomials of degree ≥ 3 we show the problem is #P-hard, even for any fixed prime or prime power modulus. This leads to a complexity dichotomy theorem — a complete classification of each problem to be either computable in polynomial time or #P-hard — for a class of exponential sums. These sums arise in the classifications of graph homomorphisms and some other counting CSP type problems, and these results lead to complexity dichotomy theorems. For the polynomial-time algorithm, Gauss sums form the basic building blocks; for the hardness result we prove group-theoretic necessary conditions for tractability.

A

d-interval

is the union of

d

disjoint intervals on the real line. A

d-track interval

is the union of

d

disjoint intervals on

d

disjoint parallel lines called tracks, one interval on each track. As generalizations of the ubiquitous interval graphs,

d

-interval graphs and

d

-track interval graphs have wide applications, traditionally to scheduling and resource allocation, and more recently to bioinformatics. In this paper, we prove that recognizing

d

-track interval graphs is NP-complete for any constant

d

 ≥ 2. This confirms a conjecture of Gyárfás and West in 1995. Previously only the complexity of the

d

 = 2 case was known. Our proof in fact implies that several restricted variants of this graph recognition problem, i.e, recognizing balanced

d

-track interval graphs, unit

d

-track interval graphs, and (2,...,2)

d

-track interval graphs, are all NP-complete. This partially answers another question recently raised by Gambette and Vialette. We also prove that recognizing depth-two 2-track interval graphs is NP-complete, even for the unit case. In sharp contrast, we present a simple linear-time algorithm for recognizing depth-two unit

d

-interval graphs. These and other results of ours give partial answers to a question of West and Shmoys in 1984 and a similar question of Gyárfás and West in 1995. Finally, we give the first bounds on the track number and the unit track number of a graph in terms of the number of vertices, the number of edges, and the maximum degree, and link the two numbers to the classical concepts of arboricity.

Distributed dining philosophers is regarded as one of the most representative resource allocation problems. Many strategies are employed for avoiding deadlock and starvation, the two well-known problems in Distributed Dining Philosophers Problem(DDPP). In this paper, the formal semantics of DDPP are originally proposed by using category theory based on the Chandy-Mirsa’s acyclic directed graph strategy. The goal is to demonstrate how category theory is used in precisely defining categorical semantics and diagrammatically describing philosophers’ priority, states-transition, and composition of processes, rather than to design a new algorithm to solve the DDPP. Compared with other formal techniques, category theory not only provides a good mathematical structure for formalizing different relationships and interactions at different abstract levels, but also its diagrammatical representation strengthens the traceability and understandability of philosophers’ priority and states-transformation; additionally, its universal constructions (like colimit) offer the ability to manipulate and reason about system configuration.

We consider the

Capacitated Domination

problem, which models a service-requirement assignment scenario and is a generalization to the well-known

Dominating Set

problem. In this problem, given a graph with three parameters defined on each vertex, namely cost, capacity, and demand, we want to find an assignment of demands to vertices of least cost such that the demand of each vertex is satisfied subject to the capacity constraint of each vertex providing the service.

In terms of polynomial time approximations, we present logarithmic approximation algorithms with respect to different demand assignment models on general graphs. On the other hand, from the perspective of parameterization, we prove that this problem is

W[1]

-hard when parameterized by a structure of the graph called treewidth. Based on this hardness result, we present exact fixed-parameter tractable algorithms with respect to treewidth and maximum capacity of the vertices. This algorithm is further extended to obtain pseudo-polynomial time approximation schemes for planar graphs.

The problem of Minimum Congestion Hypergraph Embedding in a Weighted Cycle (MCHEWC) is to embed the hyperedges of a hypergraph as paths in a weighted cycle such that the maximum congestion, i.e. the maximum product of the weight of an edge and the number of times that the edge is passed by the embedding, is minimized. It is known that the problem, the same as the unweighted case, is NP-hard. The aim of this paper is to present a polynomial time approximation scheme (PTAS) for the problem.

Given a tree with nonnegative edge cost and nonnegative vertex weight, and a number

k

 ≥ 0, we consider the following four cut problems: cutting vertices of weight at most or at least

k

from the tree by deleting some edges such that the remaining part of the graph is still a tree and the total cost of the edges being deleted is minimized or maximized. The MinMstCut problem (cut vertices of weight

at most

k

and

minimize

the total cost of the edges being deleted) can be solved in linear time and space and the other three problems are NP-hard. In this paper, we design an

O

(

ln

/

ε

)-time

O

(

l

2

/

ε

 + 

n

)-space algorithm for MaxMstCut, and

O

(

ln

(1/

ε

 + log

n

))-time

O

(

l

2

/

ε

 + 

n

)-space algorithms for MinLstCut and MaxLstCut, where

n

is the number of vertices in the tree,

l

the number of leaves, and

ε

> 0 the prescribed error bound.

Wireless Communication Networks based on Frequency Division Multiplexing (FDM in short) plays an important role in the field of communications, in which each request can be satisfied by assigning a frequency. To avoid interference, each assigned frequency must be different to the neighboring assigned frequencies. Since frequency is a scarce resource, the main problem in wireless networks is how to utilize the frequency as fully as possible. In this paper, we consider the call control problem. Given a fixed bandwidth of frequencies and a sequence of communication requests, in handling each request, we must immediately choose an available frequency to accept (or reject) it. The objective of call control problem is to maximize the number of accepted requests. We study the asymptotic performance, i.e., the number of requests in the sequence and the number of available frequencies are very large positive integers. In this paper, we give a 7/3-competitive algorithm for call control problem in cellular network, improving the previous 2.5-competitive result. Moreover, we investigate the triangle-free cellular network, propose a 9/4-competitive algorithm and prove that the lower bound of competitive ratio is at least 5/3.

The newsvendor problem describes the dilemma of a newspaper salesman—how many papers should he purchase each day to resell, when he doesn’t know the demand? We develop approaches for this well known problem in operations research, both for when the actual demand is known at the end of each day, and for when just the amount sold is known, i.e., the demand is

censored

. We present three results: (1) the first known algorithm with a bound on its worst-case performance for the censored demand newsvendor problem, (2) an algorithm with improved worst-case performance bounds for the regular newsvendor problem compared to previously known algorithms, and (3) more precise bounds on the performance of the two algorithms when they are seeded with an approximate “guess” on the optimal solution. In addition (4) we test the algorithms in a variety of simulated and real world conditions, and compare the results to those by previously known approaches. Our tests indicate that our algorithms perform comparably and often better than known approaches.

Given a set

S

 = {

b

1

, ⋯ ,

b

n

} of integers and an integer

s

, the subset sum problem is to decide if there is a subset

S

′ of

S

such that the sum of elements in

S

′ is exactly equal to

s

. We present an online approximation scheme for this problem. It updates in

O

(log

n

) time and gives a (1 + 

ε

)-approximation solution in

$O((\log n+{1\over \epsilon^2}{(\log{1\over\epsilon})^{O(1)}})\log n)$

time. The online approximation for target

s

is to find a subset of the items that have been received. The bin packing problem is to find the minimum number of bins of size one to pack a list of items

a

1

, ⋯ ,

a

n

of size in [0,1]. Let function bp(

L

) be the minimum number of bins to pack all items in the list

L

. We present an online approximate algorithm for the function bp(

L

) in the bin packing problem, where

L

is the list of the items that have been received. It updates in

O

(log

n

) updating time and gives a (1 + 

ε

)-approximation solution app(

L

) for bp(

L

) in

$O((\log n)^2+({1\over \epsilon})^{O({1\over\epsilon})})$

time to satisfy app(

L

) ≤ (1 + 

ε

)bp(

L

) + 1.

In this paper we investigate the structural properties of

k

-path separable graphs, that are the graphs that can be separated by a set of

k

shortest paths. We identify several graph families having such path separability, and we show that this property is closed under minor taking. In particular we establish a list of forbidden minors for 1-path separable graphs.

Let

C

be a set of colors, and let

ω

(

c

) be an integer cost assigned to a color

c

in

C

. An edge-coloring of a graph

G

is to color all the edges of

G

so that any two adjacent edges are colored with different colors in

C

. The cost

ω

(

f

) of an edge-coloring

f

of

G

is the sum of costs

ω

(

f

(

e

)) of colors

f

(

e

) assigned to all edges

e

in

G

. An edge-coloring

f

of

G

is optimal if

ω

(

f

) is minimum among all edge-colorings of

G

. In this paper, we show that the problem of finding an optimal edge-coloring of a tree

T

can be simply reduced in polynomial time to the minimum weight perfect matching problem for a new bipartite graph constructed from

T

. The reduction immediately yields an efficient simple algorithm to find an optimal edge-coloring of

T

in time

, where

n

is the number of vertices in

T

, Δ is the maximum degree of

T

, and

N

ω

is the maximum absolute cost |

ω

(

c

)| of colors

c

in

C

. We then show that our result can be extended for multitrees.

We study the minimum diameter color-spanning set problem which has recently drawn some attention in the database community. We show that the problem can be solved in polynomial time for

L

1

and

L

 ∞ 

metrics, while it is NP-hard for all other

L

p

metrics even in two dimensions. However, we can efficiently compute a constant factor approximation.

Given a set of

n

equal size and non-overlapping axis-aligned squares, we need to choose exactly one point in each square to make the area of a convex hull of the resulting point set as large as possible. Previous algorithm [10] on this problem gives an optimal algorithm with

O

(

n

3

) running time. In this paper, we propose an approximation algorithm which runs in

O

(

n

log

n

) time and gives a convex hull with area larger than the area of the optimal convex hull minus the area of one square.

A polygon

P

admits a

sweep

if two mobile guards can detect an unpredictable, moving target inside

P

, no matter how fast the target moves. For safety, two guards are required to always be mutually visible, and thus, they should move on the polygon boundary. Our objective in this paper is to find an optimum sweep such that the sum of the distances travelled by the two guards in the sweep is minimized. We present an

O

(

n

2

) time and

O

(

n

) space algorithm, where

n

is the number of vertices of the given polygon. This new result is obtained by converting the problem of sweeping simple polygons with two guards into that of finding a shortest path between two nodes in a graph of size

O

(

n

).

We study problems in computational geometry from the viewpoint of adaptive algorithms. Adaptive algorithms have been extensively studied for the sorting problem, and in this paper we generalize the framework to geometric problems. To this end, we think of geometric problems as permutation (or rearrangement) problems of arrays, and define the “presortedness” as a distance from the input array to the desired output array. We call an algorithm

adaptive

if it runs faster when a given input array is closer to the desired output, and furthermore it does not make use of any information of the presortedness. As a case study, we look into the planar convex hull problem for which we discover two natural formulations as permutation problems. An interesting phenomenon that we prove is that for one formulation the problem can be solved adaptively, but for the other formulation no adaptive algorithm can be better than an optimal output-sensitive algorithm for the planar convex hull problem.

Monitoring and surveillance are important aspects in modern wireless sensor networks. In applications of wireless sensor networks, it often asks for the sensors to quickly move from the interior of a specified region to the region’s perimeter, so as to form a barrier coverage of the region. The region is usually given as a simple polygon or even a circle. In comparison with the traditional concept of full area coverage, barrier coverage requires fewer sensors for detecting intruders, and can thus be considered as a good approximation of full area coverage.

In this paper, we present an

O

(

n

2.5

log

n

) time algorithm for moving

n

sensors to the perimeter of the given circle such that the new positions of sensors form a regular

n

-gon and the maximum of the distances travelled by mobile sensors is minimized. This greatly improves upon the previous time bound

O

(

n

3.5

log

n

). Also, we describe an

O

(

n

4

) time algorithm for moving

n

sensors, whose initial positions are on the perimeter of the circle, to form a regular

n

-gon such that the sum of the travelled distances is minimized. This solves an open problem posed in [2]. Moreover, our algorithms are simpler and have more explicit geometric flavor.