Computing and Combinatorics

Overview:

We study a classical scheduling problem that has been investigated for more than forty years. Consider a sequence of jobs

σ

 = 

J

1

, …,

J

n

that has to be scheduled on

m

identical parallel machines. Each job

J

t

has an individual processing time

p

t

, 1 ≤ 

t

 ≤ 

n

. Preemption of jobs is not allowed. The goal is to minimize the makespan, i.e. the maximum completion time of any job in the constructed schedule. In the offline variant of the problem all jobs of

σ

are known in advance. In the online variant the jobs arrive one by one. Each incoming job

J

t

has to be assigned immediately to one of the machines without knowledge of any future jobs

J

t

′

,

t

′ > 

t

.

Optimal stopping theory considers the design of online algorithms for stopping a random sequence subject to an optimization criterion. For example, the famous secretary problem asks to identify a stopping rule that maximizes the probability of selecting the maximum element in a sequence presented in uniformly random order. In a similar vein, the prophet inequality of Krengel, Sucheston, and Garling establishes the existence of an online algorithm for selecting one element from a sequence of independent random numbers, such that the expected value of the chosen element is at least half the expectation of the maximum.

A rich set of problems emerges when one combines these models with notions from combinatorial optimization by allowing the algorithm to select multiple elements from the sequence, subject to a combinatorial feasibility constraint on the set selected. A sequence of results during the past ten years have contributed greatly to our understanding of these problems. I will survey some of these developments and their applications to topics in algorithmic game theory.

We reconsider the balloon popping problem, an intriguing combinatorial problem introduced in order to bound the competitiveness of ascending auctions with anonymous bidders with respect to the best fixed-price scheme. Previous works show that the optimal solution for this problem is in the range [1.6595,2]. We give a new lower bound of 1.68 and design an

O

(

n

5

) algorithm for computing upper bounds as a function of the number of bidders

n

. Our algorithm provides an experimental evidence that the correct upper bound is smaller than 2, thus disproving a currently believed conjecture, and can be used to test the validity of a new conjecture we propose, according to which the upper bound would decrease to

π

2

/6 + 1/4 ≈ 1.8949.

We study the performance of Subgame Perfect Equilibria, a solution concept which better captures the players’ rationality in sequential games with respect to the classical myopic dynamics based on the notions of improving deviations and Nash Equilibria, in the context of sequential isolation games. In particular, for two important classes of sequential isolation games, we show upper and lower bounds on the Sequential Price of Anarchy, that is the worst-case ratio between the social performance of an optimal solution and that of a Subgame Perfect Equilibrium, under the two classical social functions mostly investigated in the scientific literature, namely, the minimum utility per player and the sum of the players’ utilities.

Network bargaining

is a natural extension of the classical, 2-player

Nash bargaining

solution to the network setting. Here one is given an exchange network

G

connecting a set of players

V

in which edges correspond to potential contracts between their endpoints. In the standard model, a player may engage in at most one contract, and feasible outcomes therefore correspond to matchings in the underlying graph. Kleinberg and Tardos [STOC’08] recently proposed this model, and introduced the concepts of

stability

and

balance

for feasible outcomes. The authors characterized the class of instances that admit such solutions, and presented a polynomial-time algorithm to compute them.

In this paper, we generalize the work of Kleinberg and Tardos by allowing agents to engage into more complex contracts that span more than two agents. We provide suitable generalizations of the above stability and balance notions, and show that many of the previously known results for the matching case extend to our new setting. In particular, we can show that a given instance admits a stable outcome only if it also admits a balanced one. Like Bateni et al. [ICALP’10] we exploit connections to cooperative games. We fully characterize the core of these games, and show that checking its non-emptiness is NP-complete. On the other hand, we provide efficient algorithms to compute core elements for several special cases of the problem, making use of compact linear programming formulations.

A cooperative bin packing game is an

N

-person game, where the player set

N

consists of

k

bins of capacity 1 each and

n

items of sizes

a

1

, ⋯ ,

a

n

. The value of a coalition of players is defined to be the maximum total size of items in the coalition that can be packed into the bins of the coalition. We adopt the taxation model proposed by Faigle and Kern (1993) [6] and show that the 1/4-core is nonempty for all instances of the bin packing game. This strengthens the main result in [3].

In an

L

(2,1)-coloring of a graph, the vertices are colored with colors from an ordered set such that neighboring vertices get colors that have distance at least 2 and vertices at distance 2 in the graph get different colors. We consider the problem of finding an

L

(2,1)-coloring using a minimum range of colors in an online setting where the vertices arrive in consecutive time steps together with information about their neighbors and vertices at distance two among the previously revealed vertices. For this, we restrict our attention to paths and cycles.

Offline, paths can easily be colored within the range {0,…,4} of colors. We prove that, considering deterministic algorithms in an online setting, the range {0,…,6} is necessary and sufficient while a simple greedy strategy needs range {0,…,7}.

Advice complexity is a recently developed framework to measure the complexity of online problems. The idea is to measure how many bits of advice about the yet unknown parts of the input an online algorithm needs to compute a solution of a certain quality. We show a sharp threshold on the advice complexity of the online

L

(2,1)-coloring problem on paths and cycles. While achieving color range {0,…,6} does not need any advice, improving over this requires a number of advice bits that is linear in the size of the input. Thus, the

L

(2,1)-coloring problem is the first known example of an online problem for which sublinear advice does not help.

We further use our advice complexity results to prove that no randomized online algorithm can achieve a better expected competitive ratio than

$\frac{5}{4}(1-\delta)$

, for any

δ

 > 0.

Given two bounded convex sets

X

 ⊆ ℝ

m

and

Y

 ⊆ ℝ

n

, specified by membership oracles, and a continuous convex-concave function

F

:

X

×

Y

 → ℝ, we consider the problem of computing an

ε

-approximate saddle point, that is, a pair (

x

*

,

y

*

) ∈ 

X

×

Y

such that

$\sup_{y\in Y} F(x^*,y)\le \inf_{x\in X}F(x,y^*)+\varepsilon .$

Grigoriadis and Khachiyan (1995), based on a randomized variant of fictitious play, gave a simple algorithm for computing an

ε

-approximate saddle point for matrix games, that is, when

F

is bilinear and the sets

X

and

Y

are simplices. In this paper, we extend their method to the general case. In particular, we show that, for functions of constant “width”, an

ε

-approximate saddle point can be computed using

O

*

(

n

 + 

m

) random samples from log-concave distributions over the convex sets

X

and

Y

. As a consequence, we obtain a simple randomized polynomial-time algorithm that computes such an approximation faster than known methods for problems with bounded width and when

ε

 ∈ (0,1) is a fixed, but arbitrarily small constant. Our main tool for achieving this result is the combination of the randomized fictitious play with the recently developed results on sampling from convex sets. A full version of this paper can be found at

http://arxiv.org/abs/1301.5290

.

Recent research shows that significant energy saving can be achieved in wireless sensor networks (WSNs) with a mobile base station that collects data from sensor nodes via short-range communications. However, a major performance bottleneck of such WSNs is the significantly increased latency in data collection due to the low movement speed of mobile base stations. In this paper we study the problem of finding a data collection path for a mobile base station moving along a fixed track in a wireless sensor network to minimize the latency of data collection. The main contribution is an

O

(

mn

log

n

) expected time algorithm, where

n

is the number of sensors in the networks and

m

is the complexity of the fixed track.

In this paper, we study the random methods for parameterized problems. For the Parameterized

P

2

-Packing problem, by randomly partitioning the vertices, a randomized parameterized algorithm of running time

O

*

(6.75

k

) is obtained, improving the current best result

O

*

(8

k

). For the Parameterized Co-Path Packing problem, we study the kernel and randomized algorithm for the degree-bounded instance, and then by using the iterative compression technique, a randomized algorithm of running time

O

*

(3

k

) is given for the Parameterized Co-Path Packing problem, improving the current best result

O

*

(3.24

k

).

Dynamic Voltage Scaling (DVS) is a technique which allows the processors to change speed when executing jobs. Most of the previous works either study single processor or multiple parallel processors. In this paper, we consider a network of DVS enabled processors. Every job needs to go along a certain path in the network and has a certain workload finished on any processor it goes through before it moves on to the next processor. Our objective is to minimize the total energy consumption while finishing every job before its deadline. Due to the intrinsic complexity of this problem, we only focus on line networks with two nodes and a simple one-level tree network (a star). We show that in some of these simple cases, the optimal schedule can be computed efficiently and interleaving is not needed to achieve optimality. However, in both types of networks, how to find the optimal sequence of execution remains a big challenge for jobs with general workloads.

We consider online scheduling on

m

batch machines with delivery times. In this paper online means that jobs arrive over time and the characteristics of jobs are unknown until their arrival times. Once the processing of a job is completed it is delivered to the destination. The objective is to minimize the time by which all jobs have been delivered. For each job

J

j

, its processing time and delivery time are denoted by

p

j

and

q

j

, respectively. We first consider a restricted model: the jobs have agreeable processing and delivery times, i.e., for any two jobs

J

i

and

J

j

,

p

i

 > 

p

j

implies

q

i

 ≥ 

q

j

. For the restrict case, we provide a best possible online algorithm with competitive ratio 1 + 

α

m

, where

α

m

 > 0 is determined by

$\alpha_m^2+m\alpha_m=1$

. Then we present an online algorithm with a competitive ratio of

$1+2/\lfloor\sqrt{m}\rfloor$

for the general case.

In marketing products with negative externalities, a schedule which specifies an order of consumer purchase decisions is crucial, since in the social network of consumers, the decision of each consumer is negatively affected by the choices of her neighbors. In this paper, we study the problems of finding a marketing schedule for two asymmetric products with negative externalites. The goals are two-fold: maximizing the sale of one product and ensuring regret-free purchase decisions. We show that the maximization is NP-hard, and provide efficient algorithms with satisfactory performance guarantees. Two of these algorithms give regret-proof schedules, i.e. they reach Nash equilibria where no consumers regret their previous decisions. Our work is the first attempt to address these marketing problems from an algorithmic point of view.

We are given a set of jobs, each one specified by its release date, its deadline and its processing volume (work), and a single (or a set of) speed-scalable processor(s). We adopt the standard model in speed-scaling in which if a processor runs at speed

s

then the energy consumption is

s

α

units of energy per time unit, where

α

 > 1. Our goal is to find a schedule respecting the release dates and the deadlines of the jobs so that the total energy consumption is minimized. While most previous works have studied the preemptive case of the problem, where a job may be interrupted and resumed later, we focus on the non-preemptive case where once a job starts its execution, it has to continue until its completion without any interruption. As the preemptive case is known to be polynomially solvable for both the single-processor and the multiprocessor case, we explore the idea of transforming an optimal preemptive schedule to a non-preemptive one. We prove that the preemptive optimal solution does not preserve enough of the structure of the non-preemptive optimal solution, and more precisely that the ratio between the energy consumption of an optimal non-preemptive schedule and the energy consumption of an optimal preemptive schedule can be very large even for the single-processor case. Then, we focus on some interesting families of instances: (i) equal-work jobs on a single-processor, and (ii) agreeable instances in the multiprocessor case. In both cases, we propose constant factor approximation algorithms. In the latter case, our algorithm improves the best known algorithm of the literature. Finally, we propose a (non-constant factor) approximation algorithm for general instances in the multiprocessor case.

In the classic selection problem the task is to find the

k

th smallest of

N

elements. We study the complexity of this problem on a space-bounded random-access machine: The input is given in a read-only array and the capacity of workspace is limited. We prove that the linear-time prune-and-search algorithm—presented in most textbooks on algorithms—can be adjusted to use

O

(

N

) bits instead of Θ(

N

) words of extra space. Prior to our work, the best known algorithm by Frederickson could perform the task with

O

(

N

) bits of extra space in

O

(

N

log

*

N

) time. In particular, our result separates the space-restricted random-access model and the multi-pass streaming model (since we can bypass the Ω(

N

log

*

N

) lower bound known for the latter model). We also generalize our algorithm for the case when the size of the workspace is

O

(

S

) bits,

$\lg^3{N} \leq S \leq N$

. The running time of our generalized algorithm is

$O(N \lg^{*}(N/S) + N \lg{} N / \lg{} S)$

, slightly improving over the bound

$O(N \lg^{*}(N \lg{} N/S) + N \lg{} N / \lg{} S)$

of Frederickson’s algorithm. Of independent interest, the wavelet stack—a structure we used for repeated pruning—may also be useful in other applications.

In this paper, Nondeterministic Büchi Automata (NBA) are equivalently transformed as a new kind of deterministic omega automata, Deterministic Partitioned Automata (DPA). Different from the existing automata, at most three different transitions may occur between two states of a DPA. This leads to a determinization construction of NBA with smaller state complexity but larger transition complexity. Compared with the existing determinization constructions of NBA, the new one is intuitive and easily implementable since it is completely based on subset construction. In addition, we have proved that both nondeterministic and deterministic partitioned automata share the same expressive power with NBA.

We consider the question of constructing pseudorandom generators that simultaneously have linear circuit complexity (in the output length), exponential security (in the seed length), and a large stretch (linear or polynomial in the seed length). We refer to such a pseudorandom generator as an

asymptotically optimal PRG

. We present a simple construction of an asymptotically optimal PRG from any one-way function

f

:{0,1}

n

 → {0,1}

n

which satisfies the following requirements:

1.

f

can be computed by linear-size circuits;

2.

f

is 2

βn

-hard to invert for some constant

β

 > 0, and the min-entropy of

f

(

x

) on a random input

x

is at least

γn

for a constant

γ

 > 0 such that

β

/3 + 

γ

 > 1.

Alternatively, building on the work of Haitner, Harnik and Reingold (SICOMP 2011), one can replace the second requirement by:

2

′

.

f

is 2

βn

-hard to invert for some constant

β

 > 0 and it is

regular

in the sense that the preimage size of every output of

f

is fixed (but possibly unknown).

Previous constructions of PRGs from one-way functions can do without the entropy or regularity requirements, but even the best such constructions achieve slightly sub-exponential security (Vadhan and Zheng, STOC 2012).

Our construction relies on a technical result about hardcore functions that may be of independent interest. We obtain a family of hardcore functions

$\mathcal H = \{h:\{0,1\}^n\to\{0,1\}^{\alpha n}\}$

that can be computed by linear-sized circuits for any 2

βn

-hard one-way function

f

:{0,1}

n

 → {0,1}

n

where

β

 > 3

α

. Our construction of asymptotically optimal PRGs uses such hardcore functions, which can be obtained via linear-size computable affine hash functions (Ishai, Kushilevitz, Ostrovsky and Sahai, STOC 2008).

In this paper we present a new fast algorithm for finding minimal reset words for finite synchronizing automata, which is a problem appearing in many practical applications. The problem is known to be computationally hard, so our algorithm is exponential in the worst case, but it is faster than the algorithms used so far and it performs well on average. The main idea is to use a bidirectional BFS and radix (Patricia) tries to store and compare subsets. Also a number of heuristics are applied. We give both theoretical and practical arguments showing that the effective branching factor is considerably reduced. As a practical test we perform an experimental study of the length of the shortest reset word for random automata with

n

 ≤ 300 states and 2 input letters. In particular, we obtain a new estimation of the expected length of the shortest reset word

$\approx 2.5\sqrt{n-5}$

.

Let

P

be a simple polygon with

m

vertices and let

$\mathcal{U}$

be a set of

n

points in

P

. We consider the points of

$\mathcal{U}$

to be “users”. We consider a game with two players

$\mathcal{P}_1$

and

$\mathcal{P}_2$

. In this game,

$\mathcal{P}_1$

places a point facility inside

P

, after which

$\mathcal{P}_2$

places another point facility inside

P

. We say that a user

$u \in \mathcal{U}$

is served by its nearest facility, where distances are measured by the geodesic distance in

P

. The objective of each player is to maximize the number of users they serve. We show that for any given placement of a facility by

$\mathcal{P}_1$

, an optimal placement for

$\mathcal{P}_2$

can be computed in

O

(

m

 + 

n

(log

n

 + log

m

)) time. We also provide a polynomial-time algorithm for computing an optimal placement for

$\mathcal{P}_1$

.

We demonstrate how polyhedral methods of mathematical programming can be developed for and applied to computing optimal solutions for large instances of a classical geometric optimization problem with an uncountable number of constraints and variables.

The

Art Gallery Problem

(AGP) asks for placing a minimum number of stationary guards in a polygonal region

P

, such that all points in

P

are guarded. The AGP is NP-hard, even to approximate. Due to the infinite number of points to be guarded as well as possible guard positions, applying mathematical programming methods for computing provably optimal solutions is far from straightforward.

In this paper, we use an iterative primal-dual relaxation approach for solving AGP instances to optimality. At each stage, a pair of LP relaxations for a finite candidate subset of primal covering and dual packing constraints and variables is considered; these correspond to possible guard positions and points that are to be guarded.

Of particular interest are additional cutting planes for eliminating fractional solutions. We identify two classes of facets, based on

Edge Cover

and

Set Cover

(SC) inequalities. Solving the separation problem for the latter is NP-complete, but exploiting the underlying geometric structure of the AGP, we show that large subclasses of fractional SC solutions cannot occur for the AGP. This allows us to separate the relevant subset of facets in polynomial time.

Finally, we characterize all facets for finite AGP relaxations with coefficients in {0, 1, 2}. We demonstrate the practical usefulness of our approach with improved solution quality and speed for a wide array of large benchmark instances.

We consider various hitting and piercing problems for the family of axis-parallel rectangles induced by a point set. Selection Lemmas on induced objects are classical results in discrete geometry that have been well studied and have applications in many geometric problems like weak epsilon nets and slimming Delaunay triangulations. Selection Lemma type results typically bound the maximum number of induced objects that are hit/pierced by a single point. First, we prove an exact result on the strong and the weak variant of the First Selection Lemma for rectangles. We also show bounds for the Second Selection Lemma which improve upon previous bounds when there are near-quadratic number of induced rectangles. Next, we consider the hitting set problem for induced rectangles. This is a special case of the geometric hitting set problem which has been extensively studied. We give efficient algorithms and show exact combinatorial bounds on the hitting set problem for two special classes of induced axis-parallel rectangles. Finally, we show that the minimum hitting set problem for all induced lines is NP-Complete.

A common task in automatically reconstructing a three dimensional city model from its two dimensional map is to compute all the possible roofs over the ground plans. A

roof

over a simple polygon in the

xy

-plane is a terrain over the polygon such that each face

f

of the terrain is supported by a plane passing through at least one polygon edge and making a dihedral angle

$\frac{\pi}{4}$

with the

xy

-plane [3]. This definition, however, allows roofs with faces isolated from the boundary of the polygon and local minimum edges inducing pools of rainwater. Recently, Ahn et al. [1,2] introduced “realistic roofs” over a simple rectilinear polygon

P

with

n

vertices by imposing two additional constraints under which no isolated faces and no local minimum vertices are allowed. Their definition is, however, too restrictive that it excludes a large number of roofs with no local minimum edges. In this paper, we propose a new definition of realistic roofs corresponding to the class of roofs without isolated faces and local minimum edges. We investigate the geometric and combinatorial properties of realistic roofs and show that the maximum possible number of distinct realistic roofs over

P

is at most

$1.3211^m{m \choose \lfloor \frac{m}{2} \rfloor}$

, where

$m=\frac{n-4}{2}$

. We also present an algorithm that generates all combinatorial representations of realistic roofs.

Suppose that each vertex of a graph

G

is either a supply vertex or a demand vertex and is assigned a supply or a demand. All demands and supplies are nonnegative constant numbers in a steady network, while they are functions of a variable

λ

in a parametric network. Each demand vertex can receive “power” from exactly one supply vertex through edges in

G

. One thus wishes to partition

G

to connected components by deleting edges from

G

so that each component has exactly one supply vertex whose supply is at least the sum of demands in the component. The “partition problem” asks whether

G

has such a partition. If

G

has no such partition, one wishes to find the maximum number

r

*

,

$0\le r^* \textless 1$

, such that

G

has such a partition when every demand is reduced to

r

*

times the original demand. The “maximum supply rate problem” asks to compute

r

*

. In this paper, we deal with a network in which

G

is a tree, and first give a polynomial-time algorithm for the maximum supply rate problem for a steady tree network, and then give an algorithm for the partition problem on a parametric tree network, which takes pseudo-polynomial time if all the supplies and demands are piecewise linear functions of

λ

.

We investigate the minimum independent dominating set in perturbed graphs

${\mathfrak g}(G, p)$

of input graph

G

 = (

V

,

E

), obtained by negating the existence of edges independently with a probability

p

 > 0. The minimum independent dominating set (MIDS) problem does not admit a polynomial running time approximation algorithm with worst-case performance ratio of

n

1 − 

ε

for any

ε

 > 0. We prove that the size of the minimum independent dominating set in

${\mathfrak g}(G, p)$

, denoted as

$i({\mathfrak g}(G, p))$

, is asymptotically almost surely in Θ(log|

V

|). Furthermore, we show that the probability of

$i({\mathfrak g}(G, p)) \ge \sqrt{\frac{4|V|}{p}}$

is no more than 2

− |

V

|

, and present a simple greedy algorithm of proven worst-case performance ratio

$\sqrt{\frac{4|V|}{p}}$

and with polynomial expected running time.

Given a set

S

, two collections

C

r

and

C

b

of non-empty subsets of

S

and a positive integer

k

 < |

S

|, the minimum degree hypergraph (MDH) problem is to find a subset

S

′ of

S

such that

S

′ ∩ 

B

 ≠ ∅ for all

B

 ∈ 

C

b

and |

S

′ ∩ 

R

| ≤ 

k

for all

R

 ∈ 

C

r

. This paper presents a linear-time algorithm for the MDH problem with

C

r

 ∪ 

C

b

having the consecutive ones property. The presented algorithm improves the previous upper bound from

O

(|

S

|

2

).

The investigation of the asymptotic behaviour of various graph parameters in powers of a fixed graph

G

 = (

V

,

E

) is motivated by problems in information theory and extremal combinatorics. Considering various parameters and/or various notions of graph powers we can arrive at different notions of graph capacities, of which the Shannon capacity is best known. Here we study a related notion of the so-called conjunctive capacity of a graph

G

,

C

AND

(

G

), introduced and studied by Gargano, Körner and Vaccaro [5], [6]. To determine

C

AND

(

G

) is a convex programming problem. In this paper we show that the optimal solution to this problem is unique and describe the structure of the solution in any (simple) graph. We show that its reciprocal value

$vc_C(G):=\frac{1}C_{\text{AND}(G)}$

is an optimal solution of the newly introduced problem of Minimum Capacitary Vertex Cover that is closely related to the LP-relaxation of the Minimum Vertex Cover Problem. We also describe its close connection with the binding number/binding set of a graph, and with the strong crown decomposition of graphs introduced in [2].

We consider the

facility location problem with submodular penalty

(FLPSP) and the

facility location problem with linear penalty

(FLPLP), two extensions of the classical

facility location problem

(FLP). First, we introduce a general algorithmic framework for a class of covering problems with

submodular

penalty, extending the recent result of Geunes et al. [11] with

linear

penalty. This framework leverages existing approximation results for the original covering problems to obtain corresponding results for their submodular penalty counterparts. Specifically, any LP-based

α

-approximation for the original covering problem can be leveraged to obtain an

$1/\left(1-e^{-1/\alpha}\right)$

-approximation algorithm for the counterpart with submodular penalty. Consequently, any LP-based approximation algorithm for the classical FLP (as a covering problem) can yield, via this framework, an approximation algorithm for the submodular penalty counterpart. Second, by exploiting some special properties of FLP, we present an LP rounding algorithm which has the currently best 2-approximation ratio over the previously best 2.50 by Hayrapetyan et al. [13] for the FLPSP and another LP rounding algorithm which has the currently best 1.5148-approximation ratio over the previously best 1.853 by Xu and Xu [27] for the FLPLP, respectively.

We present a unified semidefinite programming hierarchies rounding approximation algorithm for a class of maximum graph bisection problems with improved approximation ratios.

We consider the universal facility location problem in which the goal is to assign clients to facilities in order to minimize the sum of connection and facility costs. The connection cost is proportional to the distance each client has to travel to its assigned facility, whereas the cost of a facility is a non-decreasing function depending on the number of clients assigned to the facility. This model generalizes several variants of facility location problems. We present a (5.83 + 

ε

) approximation algorithm for this problem based on local search technique.

For a given graph

G

with positive integral cost and delay on edges, distinct vertices

s

and

t

, cost bound

C

 ∈ 

Z

 + 

and delay bound

D

 ∈ 

Z

 + 

, the

k

bi-constraint path (

k

BCP) problem is to compute

k

disjoint

st

-paths subject to

C

and

D

. This problem is known NP-hard, even when

k

 = 1 [4]. This paper first gives a simple approximation algorithm with factor-(2,2), i.e. the algorithm computes a solution with delay and cost bounded by 2*

D

and 2*

C

respectively. Later, a novel improved approximation algorithm with ratio

$(1+\beta,\,\max\{2,\,1+\ln\frac{1}{\beta}\})$

is developed by constructing interesting auxiliary graphs and employing the cycle cancellation method. As a consequence, we can obtain a factor-(1.369, 2) approximation algorithm by setting

$1+\ln\frac{1}{\beta}=2$

and a factor-(1.567, 1.567) algorithm by setting

$1+\beta=1+\ln\frac{1}{\beta}$

. Besides, by setting

β

 = 0, an approximation algorithm with ratio (1,

O

(ln

n

)), i.e. an algorithm with only a single factor ratio

O

(ln

n

) on cost, can be immediately obtained. To the best of our knowledge, this is the first non-trivial approximation algorithm for the

k

BCP problem that strictly obeys the delay constraint.

Given a vertex-weighted undirected graph

G

 = (

V

,

E

,

w

) and a positive integer

k

, we consider the

k

-separator problem: it consists in finding a minimum-weight subset of vertices whose removal leads to a graph where the size of each connected component is less than or equal to

k

. We show that this problem can be solved in polynomial time for some graph classes: for cycles and trees by a dynamic programming approach and by using a peculiar graph transformation coupled with recent results from the literature for

m

K

2

-free, (

G

1

,

G

2

,

G

3

,

P

6

)-free, interval-filament, asteroidal triple-free, weakly chordal, interval and circular-arc graphs. Approximation algorithms are also presented.

Dynamic

graph theory is a novel, growing area that deals with graphs that change over time and is of great utility in modelling modern wireless, mobile and dynamic environments. As a graph evolves, possibly arbitrarily, it is challenging to identify the graph properties that can be preserved over time and understand their respective computability.

In this paper we are concerned with the

treewidth

of dynamic graphs. We focus on

metatheorems

, which allow the generation of a series of results based on general properties of classes of structures. In graph theory two major metatheorems on treewidth provide complexity classifications by employing structural graph measures and finite model theory. Courcelle’s Theorem gives a general tractability result for problems expressible in monadic second order logic on graphs of bounded treewidth, and Frick & Grohe demonstrate a similar result for first order logic and graphs of bounded local treewidth.

We extend these theorems by showing that dynamic graphs of bounded (local) treewidth where the length of time over which the graph evolves and is observed is finite and bounded can be modelled in such a way that the (local) treewidth of the underlying graph is maintained. We show the application of these results to problems in dynamic graph theory and dynamic extensions to static problems. In addition we demonstrate that certain widely used dynamic graph classes naturally have bounded local treewidth.

We investigate square-orthogonal drawings of non-planar graphs with vertices represented as unit grid squares. We present quadratic-time algorithms to construct the square-orthogonal drawings of 5-graphs, 6-graphs, and 8-graphs such that each edge in the drawing contains at most two, two, and three bends, respectively. In particular, the novel analysis method we use to split a vertex so as to build some specific propagation channels in our algorithms is an interesting technique and may be of independent interest. Moreover, we show that the decision problem of determining whether an 8-graph has a square-orthogonal drawing without edge-bends is NP-complete.

We study the tree edit distance problem with edge deletions and edge insertions as edit operations. We reformulate a special case of this problem as

Covering Tree with Stars

(CTS): given a tree

T

and a set

$\cal{S}$

of stars, can we connect the stars in

$\cal{S}$

by adding edges between them such that the resulting tree is isomorphic to

T

? We prove that in the general setting, CST is NP-complete, which implies that the tree edit distance considered here is also NP-hard, even when both input trees having diameters bounded by 10. We also show that, when the number of distinct stars is bounded by a constant

k

, CTS can be solved in polynomial time by presenting a dynamic programming algorithm running in

$O(|V(T)|^2\cdot k\cdot |V({\cal S})|^{2k})$

time.

Mutation region detection is the first step of searching for a disease gene and has facilitated the identification of several hundred human genes that can harbor mutations leading to a disease phenotype. Recently, the

closest shared center

problem (CSC) was proposed as a core to solve the mutation region detection problem when the pedigree is not given [9]. A ratio-2 approximation algorithm was proposed for the closest shared center problem. In this paper, we will design a polynomial time approximation scheme for this problem.

Scaffold filling is a new combinatorial optimization problem in genome sequencing. The one-sided scaffold filling problem can be described as: given an incomplete genome

I

and a complete (reference) genome

G

, fill the missing genes into

I

such that the number of common (string) adjacencies between the resulting genome

I

′ and

G

is maximized. This problem is NP-complete for genome with duplicated genes and the best known approximation factor is 1.33, which uses a greedy strategy. In this paper, we prove a better lower bound of the optimal solution, and devise a new algorithm by exploiting the maximum matching method and a local improvement technique, which improves the approximation factor to 1.25.

In this work, we study the one-sided block ordering problem with block-interchange distance. Given two signed permutations

π

and

σ

of size

n

, where

π

represents a partially assembled genome consisting of several blocks (contigs) and

σ

represents a completely assembled genome, the one-sided block ordering problem is to order (assemble) the blocks of

π

such that the block-interchange distance between the assembly of

π

and

σ

is minimized. In addition to genome rearrangements and phylogeny reconstruction, the one-sided block ordering problem is useful in genome resequencing, because its algorithms can be used to assemble the contigs of partially assembled resequencing genomes based on their completely assembled genomes. By using permutation groups, we design an efficient algorithm to solve the one-sided block ordering problem with block-interchange distance in

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

time. Moreover, we show that the assembly of

π

can be done in

$\mathcal{O}(n)$

time and its block-interchange distance from

σ

can also be calculated in advance in

$\mathcal{O}(n)$

time.

The interaction of two RNA molecules involves a complex interplay between folding and binding that warranted recent developments in RNA-RNA interaction algorithms. However, biological mechanisms in which more than two RNAs take part in an interaction exist.

We formulate multiple RNA interaction as a computational problem, which not surprisingly turns out to be NP-complete. Our experiments with approximation algorithms and heuristics for the problem suggest that this formulation is indeed useful to determine interaction patterns of multiple RNAs when information about which RNAs interact is not necessarily available (as opposed to the case of two RNAs where one must interact with the other), and because the resulting RNA structure often cannot be predicated by existing algorithms when RNAs are simply handled in pairs. We show instances of multiple RNA interaction that are accurately predicted by our algorithms.

We consider graphs without loops or parallel edges in which every edge is assigned + or −. Such a signed graph is balanced if its vertex set can be partitioned into parts

V

1

and

V

2

such that all edges between vertices in the same part have sign + and all edges between vertices of different parts have sign − (one of the parts may be empty). It is well-known that every connected signed graph with

n

vertices and

m

edges has a balanced subgraph with at least

$\frac{m}{2} + \frac{n-1}{4}$

edges and this bound is tight. We consider the following parameterized problem: given a connected signed graph

G

with

n

vertices and

m

edges, decide whether

G

has a balanced subgraph with at least

$\frac{m}{2} + \frac{n-1}{4}+\frac{k}{4}$

edges, where

k

is the parameter.

We obtain an algorithm for the problem of runtime 8

k

(

kn

)

O

(1)

. We also prove that for each instance (

G

,

k

) of the problem, in polynomial time, we can either solve (

G

,

k

) or produce an equivalent instance (

G

′,

k

′) such that

k

′ ≤ 

k

and |

V

(

G

′)| = 

O

(

k

3

). Our first result generalizes a result of Crowston, Jones and Mnich (ICALP 2012) on the corresponding parameterization of Max Cut (when every edge of

G

has sign −). Our second result generalizes and significantly improves the corresponding result of Crowston, Jones and Mnich for MaxCut: they showed that |

V

(

G

′)| = 

O

(

k

5

).

Group testing is the problem of identifying up to

d

defectives in a set of

n

elements by testing subsets for the presence of defectives. Let

t

(

n

,

d

,

s

) be the optimal number of tests needed by an

s

-stage strategy in the strict group testing model where the searcher must also verify that no more than

d

defectives are present. We develop combinatorial tools that are powerful enough to compute many exact

t

(

n

,

d

,

s

) values. This extends the work of Huang and Hwang (2001) for

s

 = 1 to multistage strategies. The latter are interesting since it is known that asymptotically nearly optimal group testing is possible already in

s

 = 2 stages. Besides other tools we generalize

d

-disjunct matrices to any candidate hypergraphs, which enables us to express optimal test numbers for

s

 = 2 as chromatic numbers of certain conflict graphs. As a proof of concept we determine almost all test numbers for

n

 ≤ 10, and

t

(

n

,2,2) for some larger

n

.

We consider a simple generalization of two-layer crossing minimization problem (TLCM) called leaf-edge-weighted TLCM (LEW-TLCM), where we allow positive weights on edges incident to leaves, and show that this problem admits a kernel with

O

(

k

) edges provided that the given graph is connected. As a straightforward consequence, LEW-TLCM (and hence TLCM) has a fixed parameter algorithm that runs in 2

O

(

k

log

k

)

 + 

n

O

(1)

time which improves on the previously best known algorithm with running time

$2^{O(k^3)}n$

.

In this paper, we design the first linear-time algorithm for computing the prime decomposition of a digraph

G

with regard to the cartesian product. A remarkable feature of our solution is that it computes the decomposition of

G

from the decomposition of its underlying undirected graph, for which there exists a linear-time algorithm. First, this allows our algorithm to remain conceptually very simple and in addition, it provides new insight into the connexions between the directed and undirected versions of cartesian product of graphs.

The problem of metrical service systems with multiple servers ((

k

,

l

)-MSSMS) proposed by Feuerstein [16] is to service requests, each of which is an

l

-point subset of a metric space, using

k

servers in an online manner, minimizing the distance traveled by the servers. We prove that Feuerstein’s deterministic algorithm actually achieves an improved competitive ratio of

$k\left({{k+l}\choose{l}}-1\right)$

on uniform metrics. In the randomized online setting on uniform metrics, we give an algorithm which achieves a competitive ratio

$\mathcal{O}(k^3\log l)$

, beating the deterministic lower bound of

${{k+l}\choose{l}}-1$

. We prove that any randomized algorithm for MSSMS on uniform metrics must be Ω(log

kl

)-competitive. On arbitrary metric spaces, we have deterministic lower bounds which are significantly larger than the bound for uniform metrics [8].

For the offline (

k

,

l

)-MSSMS, we give a factor

l

pseudo-approximation algorithm using

kl

servers on any metric space, and prove a matching hardness result, that a pseudo-approximation using less than

kl

servers is unlikely, even on uniform metrics.

The advice complexity of an online problem describes the additional information both necessary and sufficient for online algorithms to compute solutions of a certain quality. In this model, an oracle inspects the input before it is processed by an online algorithm. Depending on the input string, the oracle prepares an advice bit string that is accessed sequentially by the algorithm. The number of advice bits that are read to achieve some specific solution quality can then serve as a fine-grained complexity measure. The main contribution of this paper is to study a powerful method for proving lower bounds on the number of advice bits necessary. To this end, we consider the string guessing problem as a generic online problem and show a lower bound on the number of advice bits needed to obtain a good solution. We use special reductions from string guessing to improve the best known lower bound for the online set cover problem and to give a lower bound on the advice complexity of the online maximum clique problem.

In this paper, we study 1-space bounded 2-dimensional bin packing and square packing. A sequence of rectangular items (square items) arrive one by one, each item must be packed into a square bin of unit size on its arrival without any information about future items. When packing items, 90°-rotation is allowed. 1-space bounded means there is only one “active” bin. If the “active” bin cannot accommodate the coming item, it will be closed and a new bin will be opened. The objective is to minimize the total number of bins used for packing all items in the sequence.

Our contributions are as follows: For 1-space bounded 2-dimensional bin packing, we propose an online packing strategy with competitive ratio 5.06. A lower bound of 3.17 on the competitive ratio is proven. Moreover, we study 1-space bounded square packing, where each item is a square with side length no more than 1. A 4.3-competitive algorithm is achieved, and a lower bound of 2.94 on the competitive ratio is given. All these bounds surpass the previously best known results.

The bin packing problem has been extensively studied and numerous variants have been considered. The

k-item bin packing

problem is one of the variants introduced by Krause et al. in Journal of the ACM 22(4). In addition to the formulation of the classical bin packing problem, this problem imposes a

cardinality constraint

that the number of items packed into each bin must be at most

k

. For the

online

setting of this problem, i.e., the items are given one by one, Babel et al. provided lower bounds

$\sqrt{2} \approx 1.41421$

and 1.5 on the asymptotic competitive ratio for

k

 = 2 and 3, respectively, in Discrete Applied Mathematics 143(1-3). For

k

 ≥ 4, some lower bounds (e.g., by van Vliet in Information Processing Letters 43(5)) for the online bin packing problem, i.e., a problem without cardinality constraints, can be applied to this problem.

In this paper we consider the online

k

-item bin packing problem. First, we improve the previous lower bound 1.41421 to 1.42764 for

k

 = 2. Moreover, we propose a new method to derive lower bounds for general

k

and present improved bounds for various cases of

k

 ≥ 4. For example, we improve 1.33333 to 1.5 for

k

 = 4, and 1.33333 to 1.47058 for

k

 = 5.

This work presents new results on flood-filling games, Flood-It and Free-Flood-It, in which the player aims to make the board monochromatic with a minimum number of flooding moves. As for many colored graph problems, Flood-filling games have relevant interpretations in bioinformatics. The standard versions of Flood-It and Free-Flood-It are played on

n

×

m

grids. In this paper we analyze the complexity of these games when played on trees. We prove that Flood-It remains NP-hard on trees whose leaves are at distance at most

d

 = 2 from the pivot, and that Flood-It is in FPT when parameterized by the number of colors

c

in such trees (for any constant

d

). We also show that Flood-It on trees and Restricted Shortest Common Supersequence (RSCS) are analogous problems, in the sense that they can be translated from one to another, keeping complexity features; this implies that Flood-It on trees inherits several complexity results already proved for RSCS, such as some interesting FPT and W[1]-hard cases. We introduce a new variant of Flood-It, called Multi-Flood-It, where each move of the game is played on various pivots. We also present a general framework for reducibility from Flood-It to Free-Flood-It, by defining a special graph operator

ψ

such that Flood-It played on a graph class

$\mathcal{F}$

is reducible to Free-Flood-It played on the image of

$\mathcal{F}$

under

ψ

. An interesting particular case occurs when

$\mathcal{F}$

is closed under

ψ

. Some NP-hard cases for Free-Flood-It on trees can be derived using this approach. We conclude by showing some results on parameterized complexity for Free-Flood-It played on pc-trees (phylogenetic colored trees). We prove that some results valid for Flood-It on pc-trees can be inherited by Free-Flood-It on pc-trees, using another type of reducibility framework.

In this paper, we consider the problem of maximizing the spread of influence through a social network. Here, we are given a graph

G

 = (

V

,

E

), a positive integer

k

and a threshold value thr(

v

) attached to each vertex

v

 ∈ 

V

. The objective is then to find a subset of

k

vertices to “activate” such that the number of activated vertices at the end of a propagation process is maximum. A vertex

v

gets activated if at least thr(

v

) of its neighbors are. We show that this problem is strongly inapproximable in fpt-time with respect to (w.r.t.) parameter

k

even for very restrictive thresholds. For unanimity thresholds, we prove that the problem is inapproximable in polynomial time and the decision version is

W

[1]-hard w.r.t. parameter

k

. On the positive side, it becomes

r

(

n

)-approximable in fpt-time w.r.t. parameter

k

for any strictly increasing function

r

. Moreover, we give an fpt-time algorithm to solve the decision version for bounded degree graphs.

Branching on forbidden induced subgraphs is a genetic strategy to obtain parameterized algorithms for many edge modification problems. For such a problem in which the graph property is defined by multiple forbidden induced subgraphs, branching process is trivially performed on each subgraph. Thus, the size of the resulting search tree is dominated by the size of the largest forbidden subgraph. In this paper, we present a simple strategy for deriving significantly improved branching rules for dealing with multiple forbidden subgraphs by edge modifications. The basic idea hereby is that while constructing branching rules for the largest forbidden subgraph, we sufficiently take into account the structural relationship between it and other forbidden subgraphs. By applying this strategy, we obtain improved parameterized algorithms for edge modification problems for several graph properties such as proper interval, 3-leaf power, threshold and co-trivially perfect graphs.

The Maximun Agreement Forest problem (

maf

) asks for a largest common subforest of a collection of phylogenetic trees. The

maf

problem on two binary phylogenetic trees has been studied extensively in the literature. In this paper, we present the first group of fixed-parameter tractable algorithms for the

maf

problem on multiple (i.e., two or more) binary phylogenetic trees. Our techniques work fine for the problem for both rooted trees and unrooted trees. The computational complexity of our algorithms is comparable with that of the known algorithms for two trees, and is independent of the number of phylogenetic trees for which a maximum agreement forest is constructed.

An NP-complete coloring or homomorphism problem may become polynomial time solvable when restricted to graphs with degrees bounded by a small number, but remain NP-complete if the bound is higher. For instance, 3-colorability of graphs with degrees bounded by 3 can be decided by Brooks’ theorem, while for graphs with degrees bounded by 4, the 3-colorability problem is NP-complete. We investigate an analogous phenomenon for digraphs, focusing on the three smallest digraphs

H

with NP-complete

H

-colorability problems. It turns out that in all three cases the

H

-coloring problem is polynomial time solvable for digraphs with in-degrees at most 1, regardless of the out-degree bound (respectively with out-degrees at most 1, regardless of the in-degree bound). On the other hand, as soon as both in- and out-degrees are bounded by constants greater than or equal to 2, all three problems are again NP-complete. A conjecture proposed for graphs

H

by Feder, Hell and Huang states that any variant of the

H

-coloring problem which is NP-complete without degree constraints is also NP-complete with degree constraints, provided the degree bounds are high enough. Thus, our results verify the conjecture with very precise bounds on both in- and out-degrees that are needed for NP-completeness; in particular, the bounds underscore the fact that the sufficiently large bound must apply to both the in-degrees and the out-degrees.

This paper presents a bounded model checking approach for propositional projection temporal logic (PPTL). To this end, first PPTL is briefly introduced. Then, bounded semantics of PPTL is defined according to its semantics in logic theory. Further, a reduction method from BMC to SAT is given in detail. In addition, an example is presented to illustrate how the approach works. Our experience shows that BMC approach for PPTL proposed in the paper is useful and feasible.

While the problem of packing two-dimensional squares into a square, in which a set of squares is packed into a big square, has been proved to be NP-complete, the computational complexity of the

d

-dimensional (

d

 > 2) problems of packing hypercubes into a hypercube remains an open question [5,7]. In this paper, we show that the three-dimensional problem version of packing cubes into a cube is NP-hard in the strong sense.

Given a graph with an arbitrary vertex coloring, the Convex Recoloring Problem (CR) consists of recoloring the minimum number of vertices so that each color induces a connected subgraph. We focus on the complexity and inapproximabiliy of this problem on

k

-colored graphs, for fixed

k

 ≥ 2. We prove a very strong complexity result showing that CR is already NP-hard on

k

-colored grids, and therefore also on planar graphs with maximum degree 4. For each

k

 ≥ 2, we also prove that, for a positive constant

c

, there is no

c

ln

n

-approximation algorithm even for

k

-colored

n

-vertex bipartite graphs, unless P = NP. For 2-colored (

q

,

q

 − 4)-graphs, a class that includes cographs and

P

4

-sparse graphs, we present polynomial-time algorithms for fixed

q

. The same complexity results are obtained for a relaxation of CR, where only one fixed color is required to induce a connected subgraph.

Given a connected outerplanar graph

G

with pathwidth

p

, we give an algorithm to add edges to

G

to get a supergraph of

G

, which is 2-vertex-connected, outerplanar and of pathwidth

O

(

p

). As a consequence, we get a constant factor approximation algorithm to compute a straight line planar drawing of any outerplanar graph, with its vertices placed on a two dimensional grid of minimum height. This settles an open problem raised by Biedl [3].

Finding heavy-elements (heavy-hitters) in streaming data is one of the central, and well-understood tasks. Despite the importance of this problem, when considering the

sliding windows

model of streaming (where elements eventually expire) the problem of finding

L

2

-heavy elements has remained completely open despite multiple papers and considerable success in finding

L

1

-heavy elements.

Since the

L

2

-heavy element problem doesn’t satisfy certain conditions, existing methods for sliding windows algorithms, such as smooth histograms or exponential histograms are not directly applicable to it. In this paper, we develop the first polylogarithmic-memory algorithm for finding

L

2

-heavy elements in the sliding window model.

Our technique allows us not only to find

L

2

-heavy elements, but also heavy elements with respect to any

L

p

with 0 < 

p

 ≤ 2 on sliding windows. By this we completely “close the gap” and resolve the question of finding

L

p

-heavy elements in the sliding window model with polylogarithmic memory, since it is well known that for

p

 > 2 this task is impossible.

We demonstrate a broader applicability of our method on two additional examples: we show how to obtain a sliding window approximation of the similarity of two streams, and of the fraction of elements that appear exactly a specified number of times within the window (the

α

-rarity problem). In these two illustrative examples of our method, we replace the current

expected

memory bounds with

worst case

bounds.

In this paper, we study the security of the Micali-Schnorr pseudorandom number generator. The security of this cryptographic scheme is based on two computational problems which are variants of the RSA problem. The RSA problem essentially aims at recovering the plaintext from a random ciphertext. In the analysis of the Micali-Schnorr pseudorandom generator, we are interested in instances of this problem where the plaintext is small and where the ciphertext is not entirely known. We will describe time / memory tradeoff techniques to solve these hard problems which provides the first analysis of this pseudorandom generator 25 years after its publication.

Boundary extraction algorithm proposed by Capson can get the same or even better performance as the commercial software such as

VisionPro

and

Halcon

. Unfortunately, the algorithm cannot extract the inclusion relationship between boundaries, which greatly reduce its attractiveness. Two improvements is proposed to improve the original algorithm in this paper, one is to improve the precision of boundaries by splitting points and merging points, another one is to design new data-structure and rules to implement acquiring deep inclusion relationship between external and internal boundaries. Experimental results show that the improvements increase a little consuming time but make the original algorithm more attractive.

A monotone drawing of a graph

G

is a straight line drawing of

G

where a monotone path exists between every pair of vertices of

G

in some direction. Recently monotone drawings of graphs have been discovered as a new standard for visualizing graphs. In this paper we study monotone drawings of series-parallel graphs in a variable embedding setting. We show that a series-parallel graph of

n

vertices has a straight-line planar monotone drawing on a grid of size

O

(

n

)×

O

(

n

2

).

This paper studies a combinatorial optimization problem which is obtained by combining the two-machine flow shop scheduling problem and the shortest path problem. The objective of the obtained problem is to select a subset of jobs constitutes a feasible solution to the shortest path problem, and to execute the selected jobs on two-machine flow shop to minimize the makespan. We argue that this problem is NP-hard, and propose two approximation algorithms with constant factor guarantee.

In this paper, we consider the Program Download Problem (PDP) which is to download a set of desired programs from multiple channels. When the problem is to decide whether the download can be done by a given deadline

d

and each program appears in each of the

n

channels at most once, denoted as

PDP

(

n

,1,

d

), we prove that

PDP

(

n

,1,

d

) is NP-Complete by a reduction from 3-SAT(3). We can extend the NP-hardness proof to

PDP

(2,2,

d

) where there are only two channels but each program could appear in each channel at most twice. We show that the aligned version of the problem (APDP) is polynomially solvable by reducing it to a maximum flow problem. For a different version of the problem, MPDP, where the objective is to maximize the number of program downloaded before a given deadline

d

, we prove that it is fixed-parameter tractable.

Automated theorem finding is one of 33 basic research problems in automated reasoning which was originally proposed by Wos in 1988, and it is still an open problem. For the problem, Cheng has proposed a forward deduction approach based on strong relevant logic. To verify the effectiveness of the approach, we tried to rediscover already known theorems in NBG set theory by using the approach, and succeeded in rediscovery of several known theorems. However, the method of the rediscovery is ad hoc, but not systematic. This paper gives an analysis and discussion for our experiment method and results from the viewpoint of the systematic method. The paper also presents some issues and future research directions for a systematic method of automated theorem finding based on Cheng’s approach.

In this paper, we partially address a question raised by David Karger [5] regarding the structure of maximum-weighted bipartite matchings when the affinity data is of low rank. The affinity data of a weighted bipartite graph

G

over the vertex sets

U

 = 

V

 = {1,...,

n

} means the

n

×

n

matrix

W

whose entry

W

ij

is the weight of the edge (

i

,

j

) of

G

, 1 ≤ 

i

,

j

 ≤ 

n

.

W

has rank at most

r

if there are 2

r

vector

u

1

,...,

u

r

,

v

1

,...

v

r

 ∈ ℝ

n

such that

$$W = \sum_{i=1}^r \bf{u}_i \mathbf{v}^T_i.$$

In particular, we study the following locality property of the matchings: For an integer

k

 > 0, we say the

locality

of

G

is at most

k

if for every matching

π

of

G

, either

π

has the maximum weight, or its weight is smaller than that of another matching

σ

with |

π

 ∖ 

σ

| ≤ 

k

and |

σ

 ∖ 

π

| ≤ 

k

.

We prove the following theorem: For every

W

 ∈ [0,1]

n×n

of rank

r

and

ε

 ∈ [0,1], there exists

$\tilde{W} \in[0,1]^{n\times n}$

such that (i)

$\tilde{W}$

has rank at most

r

 + 1, (ii)

$\max_{i,j} \left| W_{i,j} - \tilde{W}_{i,j}\right| \leq \epsilon, $

and (iii) the weighted bipartite graph with affinity data

$\tilde{W}$

has locality at most ⌈

r

/

ε

⌉

r

.

We investigate the approximation for computing the sum

a

1

 + ⋯ + 

a

n

with an input of a list of nonnegative elements

a

1

, ⋯ ,

a

n

. If all elements are in the range [0,1], there is a randomized algorithm that can compute an (1 + 

ε

)-approximation for the sum problem in time

$O({n(\log\log n)\over\sum_{i=1}^n a_i})$

, where

ε

is a constant in (0,1). Our randomized algorithm is based on the uniform random sampling, which selects one element with equal probability from the input list each time. We also prove a lower bound

$\Omega({n\over \sum_{i=1}^n a_i})$

, which almost matches the upper bound, for this problem.

Finding a minimum connected dominating set (

connected domination

) is known

$\cal{NP}$

-complete for chordal bipartite graphs, but tractable for convex bipartite graphs. In this paper, connected domination is shown tractable for circular- and triad-convex bipartite graphs, by efficient reductions from these graphs to convex bipartite graphs.

Suppose that each arc in a digraph

D

 = (

V

,

A

) has two costs of non-negative integers, called a spine cost and a leaf cost. A caterpillar is a directed tree consisting of a single directed path (of spine arcs) and leaf vertices each of which is incident to the directed path by exactly one incoming arc (leaf arc). For a given terminal set

K

 ⊆ 

V

, we study the problem of finding a caterpillar in

D

such that it contains all terminals in

K

and its total cost is minimized, where the cost of each arc in the caterpillar depends on whether it is used as a spine arc or a leaf arc. In this paper, we first study the complexity status of the problem with respect to the number of terminals: the problem is solvable in polynomial time for any digraph with two terminals, while it is NP-hard for three terminals. We then give a linear-time algorithm to solve the problem for digraphs with bounded treewidth, where the treewidth for a digraph

D

is defined as the one for the underlying graph of

D

. Our algorithm runs in linear time even if |

K

| = 

O

(|

V

|).

Building upon the observation that individuals’ decisions to purchase a product are influenced by recommendations from their friends as well as their own preferences, in our work, we propose a new model that factors in people’s preferences for a product and the number of his/her neighbors that have adopted this product. In our model, as in related ones, beginning with an “active” seed set (adopters), an adoption action diffuses in a cascade fashion based on a stochastic rule. We demonstrate that under this model, maximizing individuals’ adoption of a product, called the product adoption maximization (PAM) problem, is NP-hard, and the objective function for product adoption is sub-modular for time T (T = 1, 2) when the function for estimating the influence coming from neighbors is sub-linear. Hence, a natural greedy algorithm guarantees an approximation. Furthermore, we show that it is hard to approximate the PAM problem when the function for estimating the influence coming from neighbors is not sub-linear.

Imprecision, incompleteness and dynamic exist in wide range of network applications. It is difficult to decide the uncertainty relationship among nodes since traditional models do not make sense on uncertain networks, and the inherent computational complexity of problems with uncertainty is always intractable. In this paper, we study how to capture the uncertainty in networks by modeling a series snapshots of networks to an uncertain graph. Since the large number of possible instantiations of an uncertain network, a novel sampling scheme is proposed which enables the development of efficient algorithm to measure in uncertain networks; considering the practical of neighborhood relationship in real networks, a framework is introduced to transform the uncertain networks into deterministic weight networks where the weights on edges can be measured as Jaccard-like index. The comprehensive experimental evaluation on real data demonstrates the effectiveness and efficiency of our algorithms.

Online social networks can be used as networks of human sensors to detect important events. It is important to detect important events as early as possible. Microblogs provide a new communication and information sharing platform for people to report daily-life events, and express their views on various issues. Because of the quickness of microblogs, microblog data can be used to predict popular topics. In this paper, we propose a short-term prediction model of topic popularity. With data from Sina Weibo, the most popular microblog service in China, we test our algorithm and our data shows that the proposed model could give a short-term prediction on topic popularity.

Online social network services have become indispensable in people’s daily life. The analysis of data in social network services often involves data mining techniques. However, the quick increase of users in such services posts challenges to develop effective data mining algorithms to deal with large social network data. In this paper, we propose a data-mining algorithm to get the shortest path between nodes in a social network. Based on HBase[1], this algorithm analyzes the social network model, and uses the intermediary degrees and degree central algorithm to optimize the output from cloud platform. With a simulated social network, we validate the efficiency of the algorithm.

Recently, the phenomenon of influence propagation becomes a hot topic in social networks. However, few existing influence models study the influence from communities, which has a large range of applications. In this paper, we use the charged system model to represent the social influence. This model provides a natural description about the behaviors of influence and explains why the influence makes communities expand. Based on this physical model, we propose two objective functions for choosing proper candidates to enlarge a community, considering of the cost and benefit issue. Then a linear programming approach is given to maximize those two objective functions. We validate our ideas and algorithm using two real-world networks. The results demonstrate that our model can choose excellent propagation candidates for a specific community, comparing to other two algorithms.

We explore the influence of the choice of attenuation factor on Katz centrality indices for evolving communication networks. For given snapshots of a network observed over a period of time, recently developed communicability indices aim to identify best broadcasters and listeners in the network. In this article, we looked into the sensitivity of communicability indices on the attenuation factor constraint, in relation to spectral radius (the largest eigenvalue) of the network at any point in time and its computation in the case of large networks. We proposed relaxed communicability measures where the spectral radius bound on attenuation factor is relaxed and the adjacency matrix is normalised in order to maintain the convergence of the measure. Using a vitality based measure of both standard and relaxed communicability indices we looked at the ways of establishing the most important individuals for broadcasting and receiving of messages related to community bridging roles. We illustrated our findings with two examples of real-life networks, MIT reality mining data set of daily communications between 106 individuals during one year and UK Twitter mentions network, direct messages on Twitter between 12.4k individuals during one week.

Finding communities in structural networks (online social networks included) with sufficient accuracy is an important issue. We present a new method to identify communities that are in the same order of time complexity as the existing algorithms. In particular, we present an efficient algorithm using random walkers which, on a given network, generates a new network to better reveal the structures of the original network. We then use existing hierarchical clustering algorithms on the new network to find communities. We carry out simulations on both computer-generated data and the widely-used karate club data [10], and show that our algorithm can identify communities with much improved accuracy.

The investigation of relationships between various social actors has been the main focus of social network analysis in explaining the structure of social relations, measuring the relationships between the actors and etc. Blogfa is among the popular web service providers for building Persian weblogs in Iran. To the best of our knowledge, there is no social network analysis for the Computer and Internet Category of Blogfa Persian weblogs. The current paper presents a social network analysis for the Computer and Internet category of Blogfa. Each weblog in the target category contains a list of friends to which, it establishes a connection called links or links of friends. These links lead to the formation of a relationship network between weblogs. The current study has particularly focused on the relationship analysis of the network of weblogs based on the friend links. We report on our analyses and measurements of different centrality parameters such as in-degree, out degree, clustering coefficient, modularity for the group of weblogs. Furthermore, the degree of collaborations between these weblogs are analyzed and some homophilies are detected among them. It was found through the analyses that the majority of the bloggers tend to link the weblogs which provide the contents with subjects of common interests among the bloggers, and that the common interests are merely general subjects rather than professional ones.

Dynamic complex social network is always mixed with noisy data. It is important to discover and model community structure for understanding real social network and predicting its evolution. In this paper, we propose a novel algorithm NDCD(Neighborhood-based Dynamic Community Detection with graph transform for 0-1 observed networks) to discover dynamic community structure in unweighted networks. It first calculates nodes’ shared neighborhood relationship in a snapshot network and deduces the weighted directed graph; then computes both historic information and current information and deduces updated weighted undirected graphs. A greedy algorithm is designed to find the community structure snapshot at each time step. One evaluation formula is proposed to measure the community similarity. Based on this evaluation, the latent communities can be found. Experiments on both synthetic and real datasets demonstrate that our algorithm not only discovers the real community structure but also eliminates the influence of noisy data for better understanding of real network structure and its evolution.

In social networks, the mechanism to suppress harmful rumors is of great importance. A rumor spreading model has been defined using the susceptible-infected-refractory (SIR) model to characterize rumor propagation in social networks. In this paper a new inoculation strategy based on structural centrality has been applied on rumor spreading model for heterogeneous networks. It is compared with the targeted and random inoculations. The structural centrality of each nodes has been ranked in the topology of social networks which is modeled as scale free network. The nodes with higher structural centrality are chosen for inoculation in the proposed strategy. The structural centrality based inoculation strategy is more efficient in comparison with the random and targeted inoculation strategies. One of the bottlenecks is the high complexity to calculate the structural centrality of the nodes for very large number of nodes in the complex networks. The proposed hypothesis has been verified using simulation results for email network data and the generated scale free networks.

Very recently, the study of social networks has received a huge attention since we can learn and understand many hidden properties of our society. This paper investigates the potential of social network analysis to select an effective leadership group of a society. Based on our real life observation, we establish three essential requirements for an effective leadership group, namely Influenceability, Partisanship, and Bipartisanship. Then, we formulate the problem of finding a minimum size leader group satisfying the three requirements as the minimum connected

k

-core dominating set problem (MC

k

CDSP), and show its NP-hardness. In addition, we introduce an extension of MC

k

CDSP, namely MC

k

CDSP-C, which assumes the society has a number of communities and requires at least one representative from each community should be in the leadership. At last, we propose an approximation algorithm for a subclass of MC

k

CDSP with

k

 = 2, and show an

α

-approximation algorithm of MC

k

CDSP can be used to obtain an

α

-approximation algorithm of MC

k

CDSP-C.

In the next few years, Brazil will host international events such as the 2014 FIFA World Cup and the 2016 Olympics Games. Given the worldwide appeal of these events, local authorities in Brazil expect the country will have around 1.6 million visitors arriving at its airports (1 million for the Olympics and 600 thousand for the World Cup). Therefore, these events will put to test the robustness of the Brazilian airline transportation system. As of today, Brazil concentrates most of its flights in and out a single hub city: São Paulo Airport in Guarulhos (GRU). Is this concentration a problem? Aiming to analyze the hub choices of this network we collected data from the five biggest companies that operate in Brazil with domestic and international flights; together these companies are responsible for more than 94% of the total flight traffic in Brazil. In this paper analyzed the impact of moving today’s main hub, Guarulhos Airport in São Paulo (GRU), to other airports around the country—the idea is to understand what is the best configuration for single-hub model in Brazil. We also investigated the robustness of the network having a single hub by analyzing the impact of the removal of this hub from the network. We believe this work may help us understand how the airport infrastructure in Brazil has to be developed in the near future.