Combinatorial Optimization and Applications

For a fixed integer

k

 ≥ 0, a

k

-transmitter is an omnidirectional wireless transmitter with an infinite broadcast range that is able to penetrate up to

k

“walls”, represented as line segments in the plane. We develop lower and upper bounds for the number of

k

-transmitters that are necessary and sufficient to cover a given collection of line segments, polygonal chains and polygons.

The minimum spanning tree problem is one of the most fundamental algorithmic graph problems and OBDDs are a very common dynamic data structure for Boolean functions. Since in some applications graphs become larger and larger, a research branch has emerged which is concerned with the design and analysis of so-called symbolic algorithms for classical graph problems on OBDD-represented graph instances. Here, a symbolic minimum spanning tree algorithm using

O

(log

3

|

V

|) functional operations is presented, where

V

is the set of vertices of the input graph. Furthermore, answering an open problem posed by Sawitzki (2006) it is shown that every symbolic OBDD-based algorithm for the minimum spanning tree problem needs exponential space (with respect to the OBDD size of the input graph). This result even holds for planar input graphs.

This paper studies the selfish routing game in ring networks with a load-dependent linear latency on each link. We adopt the asymmetric atomic routing model. Each player selfishly chooses a route to connect his source-destination pair, aiming at a lowest latency of his route, while the system objective is to minimize the maximum latency among all routes of players. Such a routing game always has a Nash equilibrium (NE) that is a “stable state” among all players, from which no player has the incentive to deviate unilaterally. Furthermore, 16 is the current best upper bound on its price of anarchy (PoA), the worst-case ratio between the maximum latencies in a NE and in a system optimum. In this paper we show that the PoA is at most 10.16 provided cooperations within pairs of players are allowed, where any two players could change their routes simultaneously if neither would experience a longer latency and at least one would experience a shorter latency.

One approach to guarantee the performance of underwater acoustic sensor networks is to deploy multiple Surface-level Gateways (SGs) at the surface. This paper addresses the connected (or survivable) Constrained Surface-level Gateway Placement (C-SGP) problem for 3-D underwater acoustic sensor networks. Given a set of candidate locations where SGs can be placed, our objective is to place minimum number of SGs at a subset of candidate locations such that it is connected (or 2-connected) from any USN to the base station. We propose a polynomial time approximation algorithm for the connected C-SGP problem and survivable C-SGP problem, respectively. Simulations are conducted to verify our algorithms’ efficiency.

In a network environments supporting mobile entities (called robots or agents), a

black hole

is harmful site that destroys any incoming entity without leaving any visible trace. The

black-hole search

problem is the task of a team of

k

 > 1 mobile entities, starting from the same safe location and executing the same algorithm, to determine within finite time the location of the black hole. In this paper we consider the black hole search problem in asynchronous

ring

networks of

n

nodes, and focus on the

time complexity

.

It is known that any algorithm for black-hole search in a ring requires at least 2(

n

 − 2) time in the worst case. The best algorithm achieves this bound with a team of

n

 − 1 agents with an average time cost 2(

n

 − 2), equal to the worst case. In this paper we first show how the same number of agents using 2 extra time units from optimal in the worst case, can solve the problem in only

$\frac{7}{4} n-O(1)$

time on the

average

. We then prove that the optimal average case complexity

$\frac{3}{2} n-O(1)$

can be achieved without increasing the worst case using 2(

n

 − 1) agents Finally we design an algorithm that achieves asymptotically optimal both worst case and average case time complexity employing an optimal team of

k

 = 2 agents, thus improving on the earlier results that required

O

(

n

) agents.

Given a set S of

n

sensors in the plane we consider the problem of establishing an ad hoc network from these sensors using directional antennae. We prove that for each given integer 1 ≤ 

k

 ≤ 5 there is a strongly connected spanner on the set of points so that each sensor uses at most

k

such directional antennae whose range differs from the optimal range by a multiplicative factor of at most

$2 \cdot \sin(\frac{\pi}{k+1})$

. Moreover, given a minimum spanning tree on the set of points the spanner can be constructed in additional

O

(

n

) time. In addition, we prove NP completeness results for

k

 = 2 antennae.

In this work we consider the problem of maximizing the PageRank of a given target node in a graph by adding

k

new links. We consider the case that the new links must point to the given target node (backlinks). Previous work [7] shows that this problem has no fully polynomial time approximation schemes unless

P

 = 

NP

. We present a polynomial time algorithm yielding a PageRank value within a constant factor from the optimal. We also consider the naive algorithm where we choose backlinks from nodes with high PageRank values compared to the outdegree and show that the naive algorithm performs much worse on certain graphs compared to the constant factor approximation scheme.

Query evaluation in an XML database requires reconstructing XML subtrees rooted at nodes found by an XML query. Since XML subtree reconstruction can be expensive, one approach to improve query response time is to use reconstruction views - materialized XML subtrees of an XML document, whose nodes are frequently accessed by XML queries. For this approach to be efficient, the principal requirement is a framework for view selection. In this work, we are the first to formalize and study the problem of XML reconstruction view selection. The input is a tree

T

, in which every node

i

has a size

c

i

and profit

p

i

, and the size limitation

C

. The target is to find a subset of subtrees rooted at nodes

i

1

, ⋯ ,

i

k

respectively such that

$c_{i_1}+\cdots +c_{i_k}\le C$

, and

$p_{i_1}+\cdots +p_{i_k}$

is maximal. Furthermore, there is no overlap between any two subtrees selected in the solution. We prove that this problem is NP-hard and present a fully polynomial-time approximation scheme (FPTAS) as a solution.

The connected dominating set (CDS) problem is a well studied NP-hard problem with many important applications. Dorn et al. [ESA2005, LNCS3669,pp95-106] introduce a new technique to generate

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

time and fixed-parameter algorithms for a number of non-local hard problems, including the CDS problem in planar graphs. The practical performance of this algorithm is yet to be evaluated. We perform a computational study for such an evaluation. The results show that the size of instances can be solved by the algorithm mainly depends on the branchwidth of the instances, coinciding with the theoretical result. For graphs with small or moderate branchwidth, the CDS problem instances with size up to a few thousands edges can be solved in a practical time and memory space. This suggests that the branch-decomposition based algorithms can be practical for the planar CDS problem.

The classical and well-studied group testing problem is to find

d

defectives in a set of

n

elements by group tests, which tell us for any chosen subset whether it contains defectives or not. Strategies are preferred that use both a small number of tests close to the information-theoretic lower bound

d

log

n

, and a small constant number of stages, where tests in every stage are done in parallel, in order to save time. They should even work if

d

is completely unknown in advance. An essential ingredient of such competitive and minimal-adaptive group testing strategies is an estimate of

d

within a constant factor. More precisely,

d

shall be underestimated only with some given error probability, and overestimated only by a constant factor, called the competitive ratio. The latter problem is also interesting in its own right. It can be solved with

O

(log

n

) randomized group tests of a certain type. In this paper we prove that Ω(log

n

) tests are really needed. The proof is based on an analysis of the influence of tests on the searcher’s ability to distinguish between any two candidate numbers with a constant ratio. Once we know this lower bound, the next challenge is to get optimal constant factors in the

O

(log

n

) test number, depending on the desired error probability and competitive ratio. We give a method to derive upper bounds and conjecture that our particular strategy is already optimal.

Experts working for railway operators still have to devote much time and effort to creating plans for rolling stock allocation. In this paper, we formulate the railway rolling stock allocation problem as a set partitioning multi-commodity flow (SPMCF) problem and we propose a search-based heuristic approach for SPMCF. We show that our approach can obtain an approximate solution near the optimum in shorter time than CPLEX for real-life problems. Since our approach deals with a wide variety of constraint expressions, it would be applicable for developing practical plans automatically for many railway operators.

Given a directed graph

G

with non negative cost on the arcs, a directed tree cover of

G

is a rooted directed tree such that either head or tail (or both of them) of every arc in

G

is touched by

T

. The minimum directed tree cover problem (DTCP) is to find a directed tree cover of minimum cost. The problem is known to be

NP

-hard. In this paper, we show that the weighted Set Cover Problem (SCP) is a special case of DTCP. Hence, one can expect at best to approximate DTCP with the same ratio as for SCP. We show that this expectation can be satisfied in some way by designing a purely combinatorial approximation algorithm for the DTCP and proving that the approximation ratio of the algorithm is max {2, ln (

D

 + 

)} with

D

 + 

is the maximum outgoing degree of the nodes in

G

.

A spanning subgraph of a given graph

G

is called a

spanning star forest

of

G

if it is a collection of node-disjoint trees of depth at most 1 (such trees are called

stars

). The

size

of a spanning star forest is the number of leaves in all its components. The goal of the

spanning star forest problem

[12] is to find the maximum-size spanning star forest of a given graph.

In this paper, we study this problem in

c

-dense graphs, where for

c

 ∈ (0,1), a graph of

n

vertices is called

c-dense

if it contains at least

cn

2

/2 edges [2]. We design a

$(\alpha+(1-\alpha)\sqrt{c}-\epsilon)$

-approximation algorithm for spanning star forest in

c

-dense graphs for any

ε

> 0, where

$\alpha=\frac{193}{240}$

is the best known approximation ratio of the spanning star forest problem in general graphs [3]. Thus, our approximation ratio outperforms the best known bound for this problem when dealing with

c

-dense graphs. We also prove that for any

c

 ∈ (0,1), there is a constant

ε

 = 

ε

(

c

) > 0 such that approximating spanning star forest in

c

-dense graphs within a factor of 1 − 

ε

is

NP

-hard. We then demonstrate that for weighted versions (both node- and edge- weighted) of this problem, we cannot get

any

approximation algorithm with strictly better performance guarantee in

c

-dense graphs than that of the best possible approximation algorithm for general graphs. Finally, we give strong hardness-of-approximation results for a closely related problem, the minimum dominating set problem, in

c

-dense graphs.

We give a sufficient condition, which guarantees that for arbitrary Hamiltonian cycle

C

, there exists a [

k

,

k

 + 1]-factor containing

C

. This improves a previous result of Cai, Li, and Kano [7].

The Yao and Theta graphs are defined for a given point set and a fixed integer

k

 > 0. The space around each point is divided into

k

cones of equal angle, and each point is connected to a nearest neighbor in each cone. The difference between Yao and Theta graphs is in the way the nearest neighbor is defined: Yao graphs minimize the Euclidean distance between a point and its neighbor, and Theta graphs minimize the Euclidean distance between a point and the orthogonal projection of its neighbor on the bisector of the hosting cone. We prove that, corresponding to each edge of the Theta graph Θ

6

, there is a path in the Yao graph

Y

6

whose length is at most 8.82 times the edge length. Combined with the result of Bonichon, Gavoille, Hanusse and Ilcinkas, who prove an upper bound of 2 on the stretch factor of Θ

6

, we obtain an upper bound of 17.7 on the stretch factor of

Y

6

.

The best known expected time for the all pairs shortest path problem on a directed graph with non-negative edge costs is

O

(

n

2

log

n

) by Moffat and Takaoka. Let the solution set be the set of vertices to which the given algorithm has established shortest paths. The Moffat-Takaoka algorithm maintains complexities before and after the critical point in balance, which is the moment when the size of the solution set is

n

 − 

n

/log

n

. In this paper, we remove the concept of critical point and the data structure, called a batch list, whereby we make the algorithm simpler and seamless, resulting in a simpler analysis and speed-up.

A distance-

k

matching in a graph

G

is matching

M

in which the distance between any two edges of

M

is at least

k

. A distance-2 matching is more commonly referred to as an induced matching. In this paper, we show that when

G

is weakly chordal, the size of the largest induced matching in

G

is equal to the minimum number of co-chordal subgraphs of

G

needed to cover the edges of

G

, and that the co-chordal subgraphs of a minimum cover can be found in polynomial time. Using similar techniques, we show that the distance-

k

matching problem for

k

 > 1 is tractable for weakly chordal graphs when

k

is even, and is NP-hard when

k

is odd. For dually chordal graphs, we use properties of hypergraphs to show that the distance-

k

matching problem is solvable in polynomial time whenever

k

is odd, and NP-hard when

k

is even. Motivated by our use of hypergraphs, we define a class of hypergraphs which lies strictly in between the well studied classes of acyclic hypergraphs and normal hypergraphs.

Given an undirected graph

G

 = (

V

,

E

) with positive edge weights and two vertices

s

and

t

, the next-to-shortest path problem is to find an

st

-path which length is minimum among all

st

-paths of lengths strictly larger than the shortest path length. In this paper we give an

O

(|

V

|log|

V

| + |

E

|) time algorithm for this problem, which improves the previous result of

O

(|

V

|

2

) time for sparse graphs.

Given a graph

G

 = (

V

,

E

) in which a fugitive hides on vertices or along edges, graph searching problems are usually to find the minimum number of searchers required to capture the fugitive. In this paper, we consider the problem of finding the minimum number of steps to capture the fugitive. We introduce the fast edge-searching problem in the edge search model, which is the problem of finding the minimum number of steps (called the fast edge-search time) to capture the fugitive. We establish relations between the fast edge-search time and the fast search number. While the family of graphs whose fast search number is at most

k

is not minor-closed for any positive integer

k

 ≥ 2, we show that the family of graphs whose fast edge-search time is at most

k

is minor-closed. We establish relations between the fast (edge-)searching and the node searching. These relations allow us to transform the problem of computing node search numbers to the problem of computing fast edge-search time or fast search numbers. Using these relations, we prove that the problem of deciding, given a graph

G

and an integer

k

, whether the fast (edge-)search number of

G

is less than or equal to

k

is NP-complete; and it remains NP-complete for Eulerian graphs. We also prove that the problem of determining whether the fast (edge-)search number of

G

is a half of the number of odd vertices in

G

is NP-complete; and it remains NP-complete for planar graphs with maximum degree 4. We present a linear time approximation algorithm for the fast edge-search time that always delivers solutions of at most

$(1+\frac{|V|-1}{|E|+1})$

times the optimal value. This algorithm also gives us a tight upper bound on the fast search number of the graph. We also show a lower bound on the fast search number using the minimum degree and the number of odd vertices.

Given an edge-weighted undirected graph

G

 = (

V

,

E

,

c

,

w

), where each edge

e

 ∈ 

E

has a cost

c

(

e

) and a weight

w

(

e

), a set

S

 ⊆ 

V

of terminals and a positive constant

D

0

, we seek a minimum cost Steiner tree where all terminals appear as leaves and its diameter is bounded by

D

0

. Note that the diameter of a tree represents the maximum weight of path connecting two different leaves in the tree. Such problem is called the minimum cost diameter-constrained Steiner tree problem. This problem is NP-hard even when the topology of Steiner tree is fixed. In present paper we focus on this restricted version and present a fully polynomial time approximation scheme (FPTAS) for computing a minimum cost diameter-constrained Steiner tree under a fixed topology.

In modern networks, devices are equipped with multiple wired or wireless interfaces. By switching among interfaces or by combining the available interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost. In this paper, we consider the problem of guarantee the connectivity of a network

G

 = (

V

,

E

) while keeping as low as possible the maximum cost set of active interfaces at the single nodes. Nodes

V

represent the devices, edges

E

represent the connections that can be established. We study the problem of minimizing the maximum cost set of active interfaces among the nodes of the network in order to ensure connectivity. We prove that the problem is NP-hard for any fixed Δ ≥ 3 and

k

 ≥ 10, with Δ being the maximum degree, and

k

being the number of different interfaces among the network. We also show that the problem cannot be approximated within

O

(log|

V

|). We then provide approximation and exact algorithms for the general problem and for special cases, respectively.

Given an unreliable communication network, we seek a most reliable source (MRS) of the network, which maximizes the expected number of nodes that are reachable from it. The problem of computing an MRS in general graphs is #P-hard. However, this problem in tree networks has been solved in a linear time. A tree network has a weakness of low capability of failure tolerance. Embedding rings into it by adding some additional certain edges to it can enhance its failure tolerance, resulting in another class of sparse networks, called the ring-tree networks. This class of network also has an underlying tree-like topology, leading to its advantage of being easily administrated. This paper concerns with an important case whose underlying topology is a strip graph, called

λ

–rings network, and focuses on an unreliable

λ

–rings network where each link has an independent operational probability while all nodes are immune to failures. We apply the Divide-and-Conquer approach to design a fast algorithm for computing its an MRS, and employ a binary division tree (BDT) to analyze its time complexity to be

$O(\|\lambda\|^2_2+\lceil\mathrm{log}|\lambda|\rceil\cdot\|\lambda\|_1)$

.

An Underwater Acoustic Wireless Sensor Network (UA-WSN) consists of many resource-constrained Underwater Sensor Nodes (USNs), which are deployed to perform collaborative monitoring tasks over a given region. One way to preserve network connectivity while guaranteing other network QoS is to deploy some Relay Nodes (RNs) in the networks, in which RNs’ function is more powerful than USNs and their cost is more expensive. This paper addresses Constrained Low-interference Relay Node Deployment (C-LRND) problem for 3-D UA-WSNs in which the RNs are placed at a subset of candidate locations to ensure connectivity between the USNs, under both the number of RNs deployed and the value of total incremental interference constraints. We first prove that it is NP-hard, then present a general approximation algorithm framework and get two polynomial time

O

(1)-approximation algorithms.

The file distribution from a source node to

n

sink nodes along a structured overlay network can be done in time Θ(log

n

). In this paper, we model the problem of finding an optimal overlay network for file distribution as a combinatorial optimization problem, i.e., finding a weighted spanning tree which connects the source node and sink nodes and has the minimum file distribution time. We use an edge-based file distribution protocol, in which after a node receives a file it then transfers the file to its neighbor nodes one after another in a sequential order. We give the formulation of file distribution time, and use it as the objective function. The corresponding combinatorial optimization problem is NP-hard in general. We present a heuristic algorithm which derives an overlay network with file distribution time Θ(log

n

) and show that the derived overlay network is optimal if the file transfer delays between all pairs of nodes are the same.

Satellites collecting data store packets in queues and transmit these packets to ground stations within their view. In a given time step, a ground station may see several satellites, but can receive a packet from only one of them. A satellite can send each packet from its queue to a ground station in its view. We consider the problem of finding an assignment of satellites to ground stations that results in all ground stations receiving a packet while optimally balancing the sizes of remaining queues at satellites. We give a polynomial time algorithm for solving this problem which requires

O

((

m

 + 

n

)

3

n

) arithmetic operations, where

m

is the number of satellite queues and

n

is the number of ground stations.

We introduce a new class of games called the

networked common goods game

(NCGG), which generalizes the well-known

common goods game

[12]. We focus on a fairly general subclass of the game where each agent’s utility functions are the same across all goods the agent is entitled to and satisfy certain natural properties (diminishing return and smoothness). We give a comprehensive set of technical results listed as follows.

We show the optimization problem faced by a single agent can be solved efficiently in this subclass. The discrete version of the problem is however NP-hard but admits a

fully polynomial time approximation scheme

(FPTAS).

We show uniqueness results of pure strategy Nash equilibrium of NCGG, and that the equilibrium is fully characterized by the structure of the network and independent of the choices and combinations of agent utility functions.

We show NCGG is a

potential game

, and give an implementation of best/better response Nash dynamics that lead to fast convergence to an

ε

-approximate pure strategy Nash equilibrium.

Lastly, we show the

price of anarchy

of NCGG can be as large as Ω(

n

1 − 

ε

) (for any

ε

> 0), which means selfish behavior in NCGG can lead to extremely inefficient social outcomes.

Many

fixed-parameter tractable

algorithms using a bounded search tree have been repeatedly improved, often by describing a larger number of branching rules involving an increasingly complex case analysis. We introduce a novel and general branching strategy that branches on the forbidden subgraphs of a relaxed class of graphs. By using the class of

P

4

-sparse graphs as the relaxed graph class, we obtain efficient bounded-search tree algorithms for several parameterized deletion problems. For the cograph edge-deletion problem and the trivially perfect edge-deletion problem, the branching strategy yields the first non-trivial bounded-search tree algorithms. For the cograph vertex deletion problem, the running time of our simple bounded search algorithm matches those previously designed with the help of complicated case distinctions and non-trivial running time analysis [16] and computer-aided branching rules [7].

A plane graph is a drawing of a planar graph in the plane such that no two edges cross each other. A rooted plane graph has a designated outer vertex. For given positive integers

n

 ≥ 1 and

g

 ≥ 3, let

${\cal G}_3(n,g)$

denote the set of all triconnected rooted plane graphs with exactly

n

vertices such that the size of each inner face is at most

g

. In this paper, we give an algorithm that enumerates all plane graphs in

${\cal G}_3(n,g)$

. The algorithm runs in constant time per each by outputting the difference from the previous output.

The graph reconstruction conjecture is a long-standing open problem in graph theory. The conjecture has been verified for all graphs with at most 11 vertices. Further, the conjecture has been verified for regular graphs, trees, disconnected graphs, unit interval graphs, separable graphs with no pendant vertex, outer-planar graphs, and unicyclic graphs. We extend the list of graph classes for which the conjecture holds. We give a proof that bipartite permutation graphs are reconstructible.

A transformation from Propositional Projection Temporal Logic (PPTL) as well as Propositional Interval Temporal Logic (PITL) with infinite models to monadic second order logic with one successor (S1S) is presented in this paper. To this end, intervals where PPTL and PITL formulas are interpreted over are represented as

$\mathfrak{T}$

-structures. Further, the semantics of PPTL and PITL formulas are redefined over

$\mathfrak{T}$

-structures. Moreover, according to

$\mathfrak{T}$

-structure semantics, a PPTL or PITL formula is translated to a formula in S1S. As a result, many mature theoretical and technical results, such as decidability etc. for S1S can be easily inherited by PPTL and PITL.

Given a graph

G

 = (

V

,

E

), the

edge dominating set

problem is to find a minimum set

M

 ⊆ 

E

such that each edge in

E

–

M

has at least one common endpoint with an edge in

M

. The edge dominating set problem is an important graph problem and has been extensively studied. It is well known that the problem is NP-hard, even when the graph is restricted to a planar or bipartite graph with maximum degree 3. In this paper, we show that the edge dominating set problem in graphs with maximum degree 3 can be solved in

O

*

(1.2721

n

) time and polynomial space, where

n

is the number of vertices in the graph. We also show that there is an

O

*

(2.2306

k

)-time polynomial-space algorithm to decide whether a graph with maximum degree 3 has an edge dominating set of size

k

or not. Above two results improve previously known results on exact and parameterized algorithms for this problem.

In this paper we consider the problem of computing an approximate ellipsoid in the streaming model of computation, motivated by a 3/2-factor approximation algorithm for computing approximate balls. Our contribution is twofold: first, we show how to compute an approximate ellipsoid as done in the approximate ball algorithm, and second, construct an input to show that the approximation factor can be unbounded, unlike the algorithm for computing approxinmate balls. Though the ratio of volumes can become unbounded, we show that there exists a direction in which the ratio of widths is bounded by a factor of 2.