Combinatorial Optimization and Applications

An intense activity is nowadays devoted to the definition of models capturing the properties of complex networks. Among the most promising approaches, it has been proposed to model these graphs via their clique incidence bipartite graphs. However, this approach has, until now, severe limitations resulting from its incapacity to reproduce a key property of this object: the overlapping nature of cliques in complex networks. In order to get rid of these limitations we propose to encode the structure of clique overlaps in a network thanks to a process consisting in iteratively

factorising

the maximal bicliques between the upper level and the other levels of a multipartite graph. We show that the most natural definition of this factorising process leads to infinite series for some instances. Our main result is to design a restriction of this process that terminates for any arbitrary graph. Moreover, we show that the resulting multipartite graph has remarkable combinatorial properties and is closely related to another fundamental combinatorial object. Finally, we show that, in practice, this multipartite graph is computationally tractable and has a size that makes it suitable for complex network modelling.

We consider the problem of bisecting a graph, i.e. cutting it into two equally sized parts while minimising the number of cut edges. In its most general form the problem is known to be NP-hard. Several papers study the complexity of the problem when restricting the set of considered graphs. We attempt to study the effects of restricting the allowed cuts. We present an algorithm that bisects a solid grid, i.e. a connected subgraph of the infinite two-dimensional grid without holes, using only cuts that correspond to a straight line or a right angled corner. It was shown in [13] that an optimal bisection for solid grids with

n

vertices can be computed in

${\mathcal{O}}(n^5)$

time. Restricting the cuts in the proposed way we are able to improve the running time to

${\mathcal{O}}(n^4)$

. We prove that these restricted cuts still yield good solutions to the original problem: The best restricted cut is a bicriteria approximation to an optimal bisection w.r.t. both the differences in the sizes of the partitions and the number of edges that are cut.

We investigate the problem of creating fast evacuation plans for buildings that are modeled as grid polygons, possibly containing exponentially many cells. We study this problem in two contexts: the “confluent” context in which the routes to exits remain fixed over time, and the “non-confluent” context in which routes may change. Confluent evacuation plans are simpler to carry out, as they allocate contiguous regions to exits; non-confluent allocation can possibly create faster evacuation plans. We give results on the hardness of creating the evacuation plans and strongly polynomial algorithms for finding confluent evacuation plans when the building has two exits. We also give a pseudo-polynomial time algorithm for non-confluent evacuation plans. Finally, we show that the worst-case bound between confluent and non-confluent plans is

$2-O(\frac{1}{k})$

.

Given a graph

G

 = (

V

,

E

) with a positive weight function

w

on the vertices of

G

, a global powerful alliance of

G

is a subset

S

of

V

such that for every vertex

v

at least half of the total weight in the closed neighborhood of

v

is contributed by the vertices of

S

. Finding the smallest such set in general graphs is NP-complete, even when the weights are all the same. In this paper, we give a linear time algorithm that finds the smallest global powerful alliance of any weighted tree

T

 = (

V

,

E

).

There are

n

points in the plane and each point is painted by one of

m

colors where

m

 ≤ 

n

. We want to select

m

different color points such that (1) the total edge length of resulting minimal spanning tree is as small as possible; or (2) the total edge length of resulting minimal spanning tree is as large as possible; or (3) the perimeter of the convex hull of

m

different color points is as small as possible. We prove NP-completeness for those three problems and give approximations algorithms for the third problem.

The development of a new system involves extensive tests on the software functionality in order to identify possible failures. Also, a system already built requires a fine tuning of its configurable options to give the best performance in the environment it is going to work. Both cases require a finite set of tests that avoids testing all the possible combinations (which is time consuming); to this situation Mixed Covering Arrays (MCAs) are a feasible alternative. MCAs are combinatorial structures represented as matrices having a test case per row. MCAs are small, in comparison with brute force, and guarantees a level of interaction among the parameters involved (a difference with random testing). We present a Tabu Search (TS) algorithm to construct MCAs; the novelty in the algorithm is a mixture of three neighborhood functions. We also present a new benchmark for the MCAs problem. The experimental evidence showed that the TS algorithm improves the results obtained by other approaches reported in the literature, finding the optimal solution in some the solved cases.

The search tree size of the spatial Branch-and-Bound algorithm for Mixed-Integer Nonlinear Programming depends on many factors, one of which is the width of the variable ranges at every tree node. A range reduction technique often employed is called Feasibility Based Bounds Tightening, which is known to be practically fast, and is thus deployed at every node of the search tree. From time to time, however, this technique fails to converge to its limit point in finite time, thereby slowing the whole Branch-and-Bound search considerably. In this paper we propose a polynomial time method, based on solving a linear program, for computing the limit point of the Feasibility Based Bounds Tightening algorithm applied to linear equality and inequality constraints.

This article characterises stable sets in an abstract game. We show that every stable subset of the pure strategies for the game is characterised as a fixed point of the mapping assigning to each upper boundedly preordered subset of the strategies the set of all its maximal elements.

We propose a new bi-clustering algorithm, LinCoh, for finding

linear coherent

bi-clusters in gene expression microarray data. Our method exploits a robust technique for identifying conditionally correlated genes, combined with an efficient density based search for clustering sample sets. Experimental results on both synthetic and real datasets demonstrated that LinCoh consistently finds more accurate and higher quality bi-clusters than existing bi-clustering algorithms.

A novel iterative algorithm of calculating the exact transitive closure of a parameterized graph being represented by a union of simple affine integer tuple relations is presented. When it is not possible to calculate exact transitive closure, the algorithm produces its upper bound. To calculate the transitive closure of the union of all simple relations, the algorithm recognizes the class of each simple relations, calculates its exact transitive closure, forms the union of calculated transitive closures, and applies this union in an iterative procedure. Results of experiments aimed at the comparison of the effectiveness of the presented algorithm with those of related ones are outlined and discussed.

For a square primitive nonpowerful sign pattern

A

, the base of

A

, denoted by

l

(

A

), is the least positive integer

l

such that every entry of

A

l

is #. In this paper, we consider the base set of the primitive nonpowerful sign pattern matrices. Some bounds on the bases for the sign pattern matrices with base at least

$\displaystyle \frac{3}{2}n^{2}-2n+4$

is given. Some sign pattern matrices with given bases is characterized and some “

gaps

” in the base set are shown.

We present techniques for maintaining subgraph frequencies in a dynamic graph, using data structures that are parameterized in terms of

h

, the

h-index

of the graph. Our methods extend previous results of Eppstein and Spiro for maintaining statistics for undirected subgraphs of size three to directed subgraphs and to subgraphs of size four. For the directed case, we provide a data structure to maintain counts for all 3-vertex induced subgraphs in

O

(

h

) amortized time per update. For the undirected case, we maintain the counts of size-four subgraphs in

O

(

h

2

) amortized time per update. These extensions enable a number of new applications in Bioinformatics and Social Networking research.

The paper describes an optimization procedure for a class of discrete optimization problems which is defined by certain properties of the boundary of the feasible region and level sets of the objective function. It is shown that these properties are possessed, for example, by various scheduling problems, including a number of well-known NP-hard problems which play an important role in scheduling theory. For an important particular case the presented optimization procedure is compared with a version of the branch-and-bound algorithm by means of computational experiments.

Given a directed graph

G

, an edge is a strong bridge if its removal increases the number of strongly connected components of

G

. Similarly, we say that a vertex is a strong articulation point if its removal increases the number of strongly connected components of

G

. In this paper, we present linear-time algorithms for computing all the strong bridges and all the strong articulation points of directed graphs, solving an open problem posed in [2].

The graph partitioning problem (GPP) consists of partitioning the vertex set of a graph into several disjoint subsets so that the sum of weights of the edges between the disjoint subsets is minimized. The critical node problem (CNP) is to detect a set of vertices in a graph whose deletion results in the graph having the minimum pairwise connectivity between the remaining vertices. Both GPP and CNP find many applications in identification of community structures or influential individuals in social networks, telecommunication networks, and supply chain networks. In this paper, we use integer programming to formulate GPP and CNP. In several practice cases, we have networks with uncertain weights of links. Some times, these uncertainties have no information of probability distribution. We use robust optimization models of GPP and CNP to formulate the community structures or influential individuals in such networks.

Sequence assembly from short reads is an important problem in biology. It is known that solving the sequence assembly problem exactly on a bi-directed de Bruijn graph or a string graph is intractable. However finding a Shortest Double stranded DNA string (SDDNA) containing all the

k

-long words in the reads seems to be a good heuristic to get close to the original genome. This problem is equivalent to finding a cyclic Chinese Postman (CP) walk on the underlying un-weighted bi-directed de Bruijn graph built from the reads. The Chinese Postman walk Problem (CPP) is solved by reducing it to a general bi-directed flow on this graph which runs in

O

(|

E

|

2

log

2

(|

V

|)) time.

In this paper we show that the cyclic CPP on bi-directed graphs can be solved without reducing it to bi-directed flow. We present a

$\Theta(p(|V|+|E|)\log(|V|) + (d_{max}p)^3 )$

time algorithm to solve the cyclic CPP on a weighted bi-directed de Bruijn graph, where

p

 =  max {|{

v

|

d

in

(

v

) − 

d

out

(

v

) > 0}|, |{

v

|

d

in

(

v

) − 

d

out

(

v

) < 0}|} and

d

max

 =  max { |

d

in

(

v

) − 

d

out

(

v

)}. Our algorithm performs asymptotically better than the bi-directed flow algorithm when the number of

imbalanced

nodes

p

is much less than the nodes in the bi-directed graph. From our experimental results on various datasets, we have noticed that the value of

p

/|

V

| lies between 0.08% and 0.13% with 95% probability.

Many practical bi-directed de Bruijn graphs do not have cyclic CP walks. In such cases it is not clear how the bi-directed flow can be useful in identifying contigs. Our algorithm can handle such situations and identify maximal bi-directed sub-graphs that have CP walks. We also present a Θ((|

V

| + |

E

|)log(

V

)) time algorithm for the single source shortest path problem on bi-directed de Bruijn graphs, which may be of independent interest.

The discovery of power law distribution in degree sequence (i.e. the number of vertices with degree

i

is proportional to

i

 − 

β

for some constant

β

) of many large-scale real networks creates a belief that it may be easier to solve many optimization problems in such networks. Our works focus on the hardness and inapproximability of optimization problems on power law graphs (PLG). In this paper, we show that the

Minimum Dominating Set

,

Minimum Vertex Cover

and

Maximum Independent Set

are still

APX

-hard on power law graphs. We further show the inapproximability factors of these optimization problems and a more general problem (

ρ

-

Minimum Dominating Set

), which proved that a belief of (1 + 

o

(1))-approximation algorithm for these problems on power law graphs is not always true. In order to show the above theoretical results, we propose a general cycle-based embedding technique to embed any

d

-bounded graphs into a power law graph. In addition, we present a brief description of the relationship between the exponential factor

β

and constant greedy approximation algorithms.

For a connected graph

G

, a vertex subset

F

 ⊂ 

V

(

G

) is a cyclic vertex-cut of

G

if

G

 − 

F

is disconnected and at least two of its components contain cycles. The cardinality of a minimum cyclic vertex-cut of

G

, denoted by

κ

c

(

G

), is the cyclic vertex-connectivity of

G

. In this paper, we show that for any integer

n

 ≥ 4, the

n

-dimensional star graph

SG

n

has

κ

c

(

SG

n

) = 6(

n

 − 3).

We enumerate all of the shortest paths between any vertex

v

and the identity vertex in an (

n

,

k

)-star graph by enumerating the minimum factorizations of

v

in terms of the transpositions corresponding to edges in that graph. This result generalizes a previous one for the star graph, and can be applied to obtain the number of the shortest paths between a pair of vertices in some of the other similar structures. It also implies an algorithm to enumerate all such paths.

We consider the

k

most vital edges (nodes) and min edge (node) blocker versions of the 1-median and 1-center location problems. Given a weighted connected graph with distances on edges and weights on nodes, the

k

most vital edges (nodes) 1-median (respectively 1-center) problem consists of finding a subset of

k

edges (nodes) whose removal from the graph leads to an optimal solution for the 1-median (respectively 1-center) problem with the largest total weighted distance (respectively maximum weighted distance). The complementary problem, min edge (node) blocker 1-median (respectively 1-center), consists of removing a subset of edges (nodes) of minimum cardinality such that an optimal solution for the 1-median (respectively 1-center) problem has a total weighted distance (respectively a maximum weighted distance) at least as large as a specified threshold. We show that

k

most vital edges 1-median and

k

most vital edges 1-center are

NP

-hard to approximate within a factor

$\frac{7}{5}-\epsilon$

and

$\frac{4}{3}-\epsilon$

respectively, for any

ε

> 0, while

k

most vital nodes 1-median and

k

most vital nodes 1-center are

NP

-hard to approximate within a factor

$\frac{3}{2}-\epsilon$

, for any

ε

> 0. We also show that the complementary versions of these four problems are

NP

-hard to approximate within a factor 1.36.

To reduce routing cost and to improve road load balance, we study a problem of minimizing size of connected dominating set

D

under constraint that for any two nodes

u

and

v

, the routing cost through

D

is within a factor of

α

from the minimum, the cost of the shortest path between

u

and

v

. We show that for

α

 ≥ 5, this problem in unit disk graphs has a polynomial-time approximation scheme, that is, for any

ε

> 0, there is a polynomial-time (1 + 

ε

)-approximation.

We present a primal-dual ⌈log(

n

) ⌉-approximation algorithm for the version of the asymmetric prize collecting traveling salesman problem, where the objective is to find a directed tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. The previous work on the problem [9] is based on the Held-Karp relaxation and heuristic methods such as the Frieze et al.’s heuristic [6] or the recent Asadpour et al.’s heuristic for the ATSP [2]. Depending on which of the two heuristics is used, it gives respectively 1 + ⌈log(

n

) ⌉ and

$3+ 8\frac{\log(n)}{\log(\log(n))}$

as an approximation ratio. Our approximation ratio ⌈log(

n

) ⌉ outperforms the first in theory and the second in practice. Moreover, unlike the method in [9], our algorithm is combinatorial.

We present several algorithms for computing a

feasible toolpath

with desired features for sculpting a given surface using a 5-axis numerically controlled (NC) machine in computer-aided manufacturing. A toolpath specifies the orientation of a cutting tool at each point of a path taken by the tool. Previous algorithms are all heuristics with no quality guarantee of solutions and with no analysis of the running time. We present optimal quality solutions and provide time analysis for our algorithms. We model the problems using a directed, layered graph

G

such that a feasible toolpath corresponds to a certain path in

G

, and give efficient methods for solving several path problems in such graphs.

We determine the complexity of approximate counting of the total weight of assignments for complex-weighted Boolean constraint satisfaction problems (or CSPs), particularly, when degrees of instances are bounded from above by a given constant, provided that all arity-1 (or unary) constraints are freely available. All degree-1 counting CSPs are solvable in polynomial time. When the degree is more than 2, we present a trichotomy theorem that classifies all bounded-degree counting CSPs into only three categories. This classification extends to complex-weighted problems an earlier result on the complexity of the approximate counting of bounded-degree unweighted Boolean CSPs. The framework of the proof of our trichotomy theorem is based on Cai’s theory of signatures used for holographic algorithms. For the degree-2 problems, we show that they are as hard to approximate as complex Holant problems.

The problem considered in this paper is: given an integer

k

 > 0 and a set

P

of

n

points in the plane each with a corresponding non-negative weight, find a step function

f

with

k

steps that minimize the maximum weighted vertical distance between

f

and all the points in

P

. We present a randomized algorithm to solve the problem in

O

(

n

log

n

) expected running time. The bound is obviously optimal for the unsorted input. The previously best known algorithm runs in

O

(

n

log

2

n

) worst-case time. Another merit of the algorithm is its simplicity. The algorithm is just a randomized implementation of Frederickson and Johnson’s matrix searching technique, and it only exploits a simple data structure.

This paper is our third step towards developing a theory of testing monomials in multivariate polynomials and concentrates on two problems: (1) How to compute the coefficients of multilinear monomials; and (2) how to find a maximum multilinear monomial when the input is a ΠΣΠ polynomial. We first prove that the first problem is #P-hard and then devise a

O

*

(3

n

s

(

n

)) upper bound for this problem for any polynomial represented by an arithmetic circuit of size

s

(

n

). Later, this upper bound is improved to

O

*

(2

n

) for ΠΣΠ polynomials. We then design fully polynomial-time randomized approximation schemes for this problem for ΠΣ polynomials. On the negative side, we prove that, even for ΠΣΠ polynomials with terms of degree ≤ 2, the first problem cannot be approximated at all for any approximation factor ≥ 1, nor

”weakly approximated”

in a much relaxed setting, unless P=NP. For the second problem, we first give a polynomial time

λ

-approximation algorithm for ΠΣΠ polynomials with terms of degrees no more a constant

λ

 ≥ 2. On the inapproximability side, we give a

n

(1 − 

ε

)/2

lower bound, for any

ε

> 0, on the approximation factor for ΠΣΠ polynomials. When the degrees of the terms in these polynomials are constrained as ≤ 2, we prove a 1.0476 lower bound, assuming

$P\not=NP$

; and a higher 1.0604 lower bound, assuming the Unique Games Conjecture.

A simplex spanned by a colored point set in Euclidean

d

-space is

colorful

if all vertices have distinct colors. The union of all full-dimensional colorful simplices spanned by a colored point set is called the

colorful union

. We show that for every

d

 ∈ ℕ, the maximum combinatorial complexity of the colorful union of

n

colored points in ℝ

d

is between

$\Omega(n^{(d-1)^2})$

and

$O(n^{(d-1)^2}\log n)$

. For

d

 = 2, the upper bound is known to be

O

(

n

), and for

d

 = 3 we present an upper bound of

O

(

n

4

α

(

n

)), where

α

(·) is the extremely slowly growing inverse Ackermann function. We also prove several structural properties of the colorful union. In particular, we show that the boundary of the colorful union is covered by

O

(

n

d

 − 1

) hyperplanes, and the colorful union is the union of

d

 + 1 star-shaped polyhedra. These properties lead to efficient data structures for point inclusion queries in the colorful union.

The

visibility representation

(VR for short) is a classical representation of plane graphs. The VR has various applications and has been extensively studied. A main focus of the study is to minimize the size of the VR. It is known that there exists a plane graph

G

with

n

vertices where any VR of

G

requires a size at least

$\lfloor \frac{2n}{3} \rfloor \times (\lfloor \frac{4n}{3} \rfloor -3)$

. For upper bounds, it is known that every plane graph has a VR with size at most

$\lfloor \frac{2}{3}n \rfloor \times (2n-5)$

, and a VR with size at most

$(n-1) \times \lfloor \frac{4}{3}n \rfloor$

.

It has been an open problem to find a VR with both height and width simultaneously bounded away from the trivial upper bounds (namely of size

c

h

n

×

c

w

n

with

c

h

< 1 and

c

w

< 2). In this paper, we provide the first VR construction for a non-trivial graph class that simultaneously bounds both the height and the width. We prove that every 4-connected plane graph has a VR with height

$\leq \frac{3n}{4}+2\lceil\sqrt{n}\rceil +4$

and width

$\leq \lceil \frac{3n}{2}\rceil$

. Our VR algorithm is based on an

st

-orientation of 4-connected plane graphs with special properties. Since the

st

-orientation is a very useful concept in other applications, this result may be of independent interests.

Given a set

P

of

n

points and a straight line

L

, we study three important variations of minimum enclosing circle problem. The first problem is on computing

k

circles of minimum (common) radius with centers on

L

which can cover the members in

P

. We propose three algorithms for this problem. The first one runs in

O

(

nk

log

n

) time and

O

(

n

) space. The second one runs in

O

(

nk

 + 

k

2

log

3

n

) time and

O

(

n

log

n

) space assuming that the points are sorted along

L

, and is efficient where

k

 < < 

n

. The third one is based on parametric search and it runs in

O

(

n

log

n

 + 

k

log

4

n

) time. The next one is on computing the minimum radius circle centered on

L

that can enclose at least

k

points. The time and space complexities of the proposed algorithm are

O

(

nk

) and

O

(

n

) respectively. Finally, we study the situation where the points are associated with

k

colors, and the objective is to find a minimum radius circle with center on

L

such that at least one point of each color lies inside it. We propose an

O

(

n

log

n

) time algorithm for this problem.

We are searching for an unknown horizontal or vertical line in the plane under the competitive framework. We design a framework for lower bounds on all

cyclic

and

monotone

strategies that result in two-sequence functionals. For optimizing such functionals we apply a method that combines two main paradigms. The given solution shows that the combination method is of general interest. Finally, we obtain the current best strategy and can prove that this is the best strategy among all cyclic and monotone strategies which is a main step toward a lower bound construction.

Algorithms for the construction of spanning planar subgraphs of Unit Disk Graphs (UDGs) do not ensure connectivity of the resulting graph under single edge deletion. To overcome this deficiency, in this paper we address the problem of augmenting the edge set of planar geometric graphs with straight line edges of bounded length so that the resulting graph is planar and 2-edge connected. We give bounds on the number of newly added straight-line edges and show that such edges can be of length at most 3 times the max length of the edges of the original graph; also 3 is shown to be optimal. It is shown to be NP-hard to augment a geometric planar graph to a 2-edge connected geometric planar with the minimum number of new edges of a given bounded length. Further, we prove that there is no local algorithm for augmenting a planar UDG into a 2-edge connected planar graph with straight line edges.

Motivated by providing quality-of-service differentiated services in the Internet, we consider buffer management algorithms for network switches. We study a

multi-buffer model

. A network switch consists of multiple size-bounded buffers such that at any time, the number of packets residing in each individual buffer cannot exceed its capacity. Packets arrive at the network switch over time; they have values, deadlines, and designated buffers. In each time step, at most one pending packet is allowed to be sent and this packet can be from any buffer. The objective is to maximize the total value of the packets sent by their respective deadlines. A 9.82-competitive online algorithm (Azar and Levy. SWAT 2006) and a 4.73-competitive online algorithm (Li. AAIM 2009) have been provided for this model, but no offline algorithms have yet been described. In this paper, we study the offline setting of the multi-buffer model. Our contributions include a few optimal offline algorithms for some variants of the model. Each variant has its unique and interesting algorithmic feature.

In this paper, we consider a processing system that consists of two identical parallel machines such that the jobs are delivered to the system by a single transporter and moved between the machines by the same transporter. The objective is to minimize the length of a schedule, i.e., the time by which the completed jobs are collected together on board the transporter. The jobs can be processed with preemption, provided that the portions of jobs are properly transported to the corresponding machines. We establish properties of feasible schedule, define lower bounds on the optimal length and describe an algorithm that behaves like a fully polynomial-time approximation scheme (FPTAS).