Combinatorial Optimization and Applications

The max-min allocation problem under a grade of service provision is defined in the following model: given a set

${\cal M}$

of

m

parallel machines and a set

${\cal J}$

of

n

jobs, where machines and jobs are all entitled to different levels of grade of service (GoS), each job

$J_j\in {\cal J}$

has its processing time

p

j

and it is only allocated to a machine

M

i

whose GoS level is no more than the GoS level the job

J

j

has. The goal is to allocate all jobs to

m

machines to maximize the

minimum machine load

, where the machine load of machine

M

i

is the sum of the precessing times of jobs executed on

M

i

. The best approximation algorithm [4] to solve this problem produces an allocation in which the minimum machine completion time is at least

Ω

(

logloglogm

/

loglogm

) of the optimal value.

In this paper, we respectively present four approximation schemes to solve this problem and its two special versions: (1) a polynomial time approximation scheme (PTAS) with running time

$O(mn^{O(1/\epsilon^2)})$

for the general version, where

ε

> 0; (2) a PTAS and an fully polynomial time approximation scheme (FPTAS) with running time

O

(

n

) for the version where the number

m

of machines is fixed; (3) a PTAS with running time

O

(

n

) for the version where the number of GoS levels is bounded by

k

.

Given an unreliable communication network, we seek for determining a vertex from the network, the expected number of vertices which connects to is maximum. Such vertex is named the most reliable source (MRS) on the network. The communication failures may occur to links or vertices of the network. The case was generally studied, where no failure happens to each vertex and each link has an independent operational probability. Practically, failures frequently happen to the vertices, including the transmitting fault and receiving fault. Recently, another case is proposed, where each link is steady and each vertex has an independent transmitting probability and receiving probability, and an

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

time algorithm is presented for computing the MRS on such tree networks with

n

vertices. In this paper, we propose a faster algorithm for this case, whose time complexity is

$\mathcal{O}(n)$

.

The objective of the classical Joint Replenishment Problem (JRP) is to minimize ordering costs by combining orders in two stages, first at some retailers, and then at a warehouse. These orders are needed to satisfy demands that appear over time at the retailers. We investigate the natural special case that each demand has a deadline until when it needs to be satisfied. For this case, we present a randomized 5/3 -approximation algorithm, which significantly improves the best known approximation ratio of 1.8 obtained by Levi and Sviridenko (APPROX’06). We moreover prove that JRP with deadlines is APX-hard, which is the first such inapproximability result for a variant of JRP. Finally, we extend the known hardness results by showing that JRP with linear delay cost functions is NP-hard, even if each retailer has to satisfy only three demands.

The node-weighted Steiner tree problem is a variation of classical Steiner minimum tree problem. Given a graph

G

 = (

V

,

E

) with node weight function

C

:

V

→

R

 + 

and a subset

X

of

V

, the node-weighted Steiner tree problem is to find a Steiner tree for the set

X

such that its total weight is minimum. In this paper, we study this problem in unit disk graphs and present a (1+

ε

)-approximation algorithm for any

ε

> 0, when the given set of vertices is

c

-local. As an application, we use node-weighted Steiner tree to solve the node-weighted connected dominating set problem in unit disk graphs and obtain a (5 + 

ε

)-approximation algorithm.

Pooling design is an important research topic in bio- informatics due to its wide applications in molecular biology, especially DNA library screening. In this paper, with unitary spaces over finite fields, we present two new constructions whose efficiency ratio, i.e., the ratio between the number of tests and the number of items, is smaller than some of existing construction.

A

gene team

is a set of genes that appear in two or more species, possibly in a different order yet with the distance between adjacent genes in the team for each chromosome always no more than a certain threshold. The focus of this paper is the problem of finding gene teams of two chromosomes. Béal

et al

. [1] had an

O

(

n

log

2

n

)-time algorithm for this problem. In this paper, two

O

(

n

log

d

)-time algorithms are proposed, where

d

 ≤ 

n

is the number of gene teams. The proposed algorithms are obtained by modifying Béal

et al

.’s algorithm, using two different approaches. Béal

et al

.’s algorithm can be extended to find the gene teams of

k

chromosomes in

O

(

kn

log

2

n

) time. Our improved algorithms can be extended to find the gene teams of

k

chromosomes in

O

(

kn

log

d

) time.

Discovering groups of genes that share common expression profiles is an important problem in DNA microarray analysis. Unfortunately, standard bi-clustering algorithms often fail to retrieve common expression groups because (1) genes only exhibit similar behaviors over a subset of conditions, and (2) genes may participate in more than one functional process and therefore belong to multiple groups. Many algorithms have been proposed to address these problems in the past decade; however, in addition to the above challenges most such algorithms are unable to discover linear coherent bi-clusters—a strict generalization of additive and multiplicative bi-clustering models. In this paper, we propose a novel bi-clustering algorithm that discovers linear coherent bi-clusters, based on first detecting linear correlations between pairs of gene expression profiles, then identifying groups by sample majority voting. Our experimental results on both synthetic and two real datasets,

Saccharomyces cerevisiae

and

Arabidopsis thaliana

, show significant performance improvements over previous methods. One intriguing aspect of our approach is that it can easily be extended to identify bi-clusters of more complex gene-gene correlations.

This paper investigates Russian Cards problem for the purpose of unconditional secured communication. First, a picking rule and deleting rule as well as safe communication condition are given to deal with the problem with 3 players and 7 cards. Further, the problem is generalized to tackle

n

players and

n

(

n

 − 1) + 1 cards. A new picking rule for constructing the announcement is presented, and a new deleting rule for players to determine each other’s cards is formalized. In addition, the safe communication condition is also proved.

This paper proposes a method to compute the transitive closure of a union of affine relations on integer tuples. Within Presburger arithmetics, complete algorithms to compute the transitive closure exist for convex polyhedra only. In presence of non-convex relations, there exist little but special cases and incomplete heuristics. We introduce a novel sufficient and necessary condition defining a class of relations for which an exact computation is possible. Our method is immediately applicable to a wide area of symbolic computation problems. It is illustrated on representative examples and compared with state-of-the-art approaches.

Combinatorial optimization problems have recently emerged in the design of controllers for OLED displays. The objective is to decompose an image into subframes minimizing the addressing time and thereby also the amplitude of the electrical current through the diodes, which has a direct impact on the lifetime of such a display. To this end, we model this problem as an integer linear program. Subsequently, we refine this formulation by exploiting the combinatorial structure of the problem. We propose a fully combinatorial separation routine for the LP-relaxation based on matching techniques. It can be used as an oracle in various frameworks to derive approximation algorithms or heuristics. We establish NP-hardness and hardness of approximation. Nevertheless, we are able to work around this issue by only focusing on a subsets of the variables and provide experimental evidence that they are sufficient to come up with near optimal solutions in practice. On this basis, one can derive custom-tailored solutions adapting to technical constraints such as memory requirements. By allowing the addressing of distributed doublelines, we improve the addressing time in cases where previous approaches fall short due to their restriction to consecutive doublelines.

We investigate open rectangle-of-influence drawings for irreducible triangulations, which are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. An open rectangle-of-influence drawing of a plane graph

G

is a type of straight-line grid drawing where there is no vertices drawn in the proper inside of the axis-parallel rectangle defined by the two end vertices of any edge. The algorithm presented by Miura and Nishizeki [8] uses a grid of size

${\cal W} + {\cal H} \leq$

(n-1)

, where

${\cal W}$

is the width of the grid,

${\cal H}$

is the height of the grid and

n

is the number of vertices in

G

. Thus the area of the grid is at most ⌈(n-1)/2⌉ ×

$\lfloor$

(n-1)/2

$\rfloor$

[8].

In this paper, we prove that the two straight-line grid drawing algorithms for irreducible triangulations from [4] and quadrangulations from [3,5] actually produce open rectangle-of-influence drawings for them respectively. Therefore, the straight-line grid drawing size bounds from [3,4,5] also hold for the open rectangle-of-influence drawings. For irreducible triangulations, the new asymptotical grid size bound is

$\emph{11n/27}$

×

$\emph{11n/27}$

. For quadrangulations, our asymptotical grid size bound

$\emph{13n/27}$

×

$\emph{13n/27}$

is the first known such bound.

Given a fixed set of equal or unequal circular objects, the problem we deal with consists in finding the smallest container within which the objects can be packed without overlap. Circular containers are considered. Moreover, 2D and 3D problems are treated. Lacking powerful optimization method is the key obstacle to solve this kind of problems. The energy landscape paving (ELP) method is a class of heuristic global optimization algorithm. By combining the improved ELP method with the gradient descent (GD) procedure based on adaptive step length, a hybrid algorithm ELPGD for the circles and spheres packing problems is put forward. The experimental results on a series of representative circular packing instances taken from the literature show the effectiveness of the proposed algorithm for the circles packing problem, and the results on a set of unitary spherical packing instances are also presented for the spheres packing problem for future comparison with other methods.

In wireless communication networks, optimal use of the directional antenna is very important. The

directional antenna coverage (DAC) problem

is to cover all clients with the smallest number of directional antennas. In this paper, we consider the

variable-size rectangle covering (VSRC) problem

, which is a transformation of the DAC problem. There are

n

points above the base line

y

 = 0 of the two-dimensional plane. The target is to cover all these points by minimum number of rectangles, such that the dimension of each rectangle is not fixed but the area is at most 1, and the bottom edge of each rectangle is on the base line

y

 = 0. In some applications, the number of rectangles covering any position in the two-dimensional plane is bounded, so we also consider the variation when each position in the plane is covered by no more than two rectangles. We give two polynomial time algorithms for finding the optimal covering. Further, we propose two 2-approximation algorithms that use less running time (

O

(

n

log

n

) and

O

(

n

)).

We study the multiple-strip packing problem, in which the goal is to pack all the rectangles into

m

vertical strips of unit widths such that the maximum height among strips used is minimized. A number of on-line algorithms for this problem are proposed, in which the decision of delivering the rectangles to strips as well as packing the rectangles in strips must be done on-line. Both randomized and deterministic on-line algorithms are investigated, and all of them are guaranteed to have constant competitive ratios.

We present a cross-monotonic competitive cost-sharing method with provable cost-recovery ratio for the soft-capacitated economic lot-sizing game, an extension of the basic economic lot-sizing game, under the weak triangle inequality assumption.

We study Facility Location games played by

n

agents situated on the nodes of a graph. Each agent orders installation of a facility at a node of the graph and pays connection cost to the chosen node, and shares fairly facility installation cost with other agents having chosen the same location. This game has pure strategy Nash equilibria, that can be found by simple improvements performed by the agents iteratively. We show that this algorithm may need super-polynomial

$\Omega(2^{n^{\frac{1}{2}}})$

steps to converge. For metric graphs we show that approximate pure equilibria can be found in polynomial time. On metric graphs we consider additionally

strong

equilibria; previous work had shown that they do not always exist. We upper bound the overall (social) cost of

α

-approximate strong equilibria within a factor

O

(

α

ln

α

) of the optimum, for every

α

 ≥ 1.

The Single Source Shortest Paths problem with positive edge weights (SSSPP) is one of the more widely studied problems in Operations Research and Theoretical Computer Science [1,2] on account of its wide applicability to practical situations. This problem was first solved in polynomial time by Dijkstra [3], who showed that by extracting vertices with the smallest distance from the source and relaxing its outgoing edges, the shortest path to each vertex is obtained. Variations of this general theme have led to a number of algorithms, which work well in practice [4,5,6]. At the heart of a Dijkstra implementation is the technique used to implement a priority queue. It is well known that using Dijkstra’s approach requires

Ω

(

n

log

n

) steps on a graph having

n

vertices, since it essentially sorts vertices based on their distances from the source. Accordingly, the fastest implementation of Dijkstra’s algorithm on a graph with

n

vertices and

m

edges should take

Ω

(

m

 + 

n

·log

n

) time and consequently the Dijkstra procedure for SSSPP using Fibonacci Heaps is optimal, in the comparison-based model. In this paper, we introduce a new data structure to implement priority queues called Two-Level Heap (TLH) and a new variant of Dijkstra’s algorithm called

Phased Dijkstra

. We contrast the performance of Dijkstra’s algorithm (both the simple and the phased variants) using a number of data structures to implement the priority queue and empirically establish that Two-Level heaps are far superior to Fibonacci heaps on every graph family considered.

Reingold et al. introduced the notion zig-zag product on two different graphs, and presented a fully explicit construction of

d

-regular expanders with the second largest eigenvalue

O

(

d

− 1/3

). In the same paper, they ask whether or not the similar technique can be used to construct expanders with the second largest eigenvalue

O

(

d

− 1/2

). Such graphs are called Ramanujan graphs. Recently, zig-zag product has been generalized by Ben-Aroya and Ta-Shma. Using this technique, they present a family of expanders with the second largest eigenvalue

d

− 1/2 + 

o

(1)

, what they call almost-Ramanujan graphs. However, their construction relies on local invertible functions and the dependence between the big graph and several small graphs, which makes the construction more complicated.

In this paper, we shall give a generalized theorem of zig-zag product. Specifically, the zig-zag product of one “big” graph and several “small” graphs with the same size will be formalized. By choosing the big graph and several small graphs individually, we shall present a family of fully explicitly almost-Ramanujan graphs with locally invertible function waived.

Given a directed graph

G

with non-negative cost on the arcs, a directed tour cover

T

of

G

is a cycle (not necessary simple) in

G

such that either head or tail (or both of them) of every arc in

G

is touched by

T

. The minimum directed tour cover problem (DToCP) which is to find a directed tour cover of minimum cost, is

NP

-hard. It is thus interesting to design approximation algorithms with performance guarantee to solve this problem. Although its undirected counterpart (ToCP) has been studied in recent years [1,6], in our knowledge, the DTCP remains widely open. In this paper, we give a 2log

2

(

n

)-approximation algorithm for the DTCP.

We present an approximation algorithm for the Max 3-section problem which divides a weighted graph into 3 parts of equal size so as to maximize the weight of the edges connecting different parts. The algorithm is based on a complex semidefinite programming and can in some sense be viewed as a generalization of the approximation algorithm proposed by Ye [17] for the Max Bisection problem. Our algorithm can hit the 2/3 bound and has approximate ratio 0.6733 for Max 3-section that sightly improves the 2/3 bound obtained by Andersson [1] and Gaur [8], respectively.

Cayley graphs arise naturally in interconnection networks design in study of Akers and Krishnamurthy in 1989 [1]. Lakshmivarahan, Jwo and Dhall studied a number of interconnection networks as graphs in 1993 [12]. In this paper, we propose some conjectures related to complete-transposition graph, alternating-group graph, folded hypercube and binary orthogonal graph, respectively. The conjectures claim that each of these graphs is Hamiltonian decomposable. In addition, we prove that above conjectures are true for smaller order of the networks.

In 1970, Dirac conjectured that for each integer

k

 ≥ 4, there exists a vertex

k

-critical graph without any critical edge. In this paper, we introduce strict-vertex critically (

k

 − 1)-de-chromatic pair, strict 2-vertex decomposition graph and so on. By studying their relevant properties, we obtain that any vertex

k

-critical graph without any critical edge generates an infinite family of vertex

k

-critical graphs without critical edges.

Let

H

be the graph obtained from a 6-cycle

C

6

by adding an edge which joins a pair of two vertices with distance two. We show that if a planar graph does not contain

H

, then

G

is edge-

t

-choosable, where

t

 = 7 if

Δ

(

G

) = 5, and

t

 = 

Δ

(

G

) + 1, otherwise. This extends the known results that a planar graph is edge-(

Δ

(

G

) + 1)-choosable when

Δ

(

G

) ≠ 7 and

G

does not contain a

k

-cycle for some

k

 ∈ {3, 5, 6}. It is well-known that {3, 5, 6} are only integers for which the lack of a cycle of length in {3, 5, 6} for a planar graph

G

implies 3-degeneracy of

G

. As a by-product, we prove that if a planar graph

G

contains at most seven 3-cycles,

G

is 3-degenerate. We also answer a problem of Raspaud and Wang (European J. Combin. 29(2008) 1064-1075) in negative.

Riddle [15] showed that the forcing number of a bipartite graph is bounded blow by the minimum number of trailing vertices of the ordering of a color set. In the present work, we improve the trailing-vertex method by Riddle and obtain a necessary condition for the matching forcing number of a bipartite graph being equal to a given natural number

k

; furthermore, we give a sufficient and necessary condition for the minimum forcing number of bipartite graph being equal to the minimum number of trailing vertices of all standard orderings of a color set.

The integrity of a graph

G

 = (

V

,

E

) is defined as

I

(

G

) = 

min

{|

S

| + 

m

(

G

 − 

S

):

S

 ⊆ 

V

(

G

)}, where

m

(

G

 − 

X

) denotes the order of the largest component in the graph

G

 − 

X

. This is a better parameter to measure the stability of a network

G

, as it takes into account both the amount of work done to damage the network and how badly the network is damaged. In this paper, we give the exact values or bounds for the integrity of Harary graphs.

In matching theory,

n

-critical graphs play an important role in the decomposition of graphs with respect to perfect matchings. Since bipartite graphs cannot be

n

-critical when

n

 > 0, we amend the classical definition of

n

-critical graphs and propose the concept of

n

-critical bipartite graphs. Let

G

 = (

B

,

W

;

E

) be a bipartite graph with

n

 = |

W

| − |

B

|, where

B

and

W

are the bipartitions of vertex set,

E

is the edge set. Then,

G

is

n

-critical if when deleting any

n

distinct vertices of

W

, the remaining subgraph of

G

has a perfect matching. Furthermore, an algorithm for determining

n

-critical bipartite graphs is given which runs in

O

(|

W

||

E

|) time, in the worst case. Our work helps to design a job assignment circuit which has high robustness.

We consider a new kind of

n

-vehicle exploration problem. Given

n

vehicles, respectively denoted by

v

1

,

v

2

, ⋯ ,

v

n

, the oil capacity of

v

i

is

a

i

, and the oil consumption amount of

v

i

is

b

i

. The

n

vehicles depart from the same place, and steer straight to the same direction. Without oil supply in the middle, but some vehicles can stop wherever and give its oil to any others. The question is how to arrange the order of

n

vehicles to make one of the vehicles go the farthest. In this paper, we propose a couple of heuristic algorithms and construct the real-time algorithm scheme. We can find a solution in a reasonable time complexity and approximation ratio under the real-time scheme. We simulate the proposed algorithms, and the results show that the approximate ratio of heuristic algorithm is as well as be above 98%.

We consider updates to an

n

-dimensional frequency vector of a data stream, that is, the vector

f

is updated coordinate-wise by means of insertions or deletions in any arbitrary order. A fundamental problem in this model is to recall the vector approximately, that is to return an estimate

$\hat{f}$

of

f

such that

where

ε

is an accuracy parameter and

p

is the index of the ℓ

p

norm used to calculate the norm

. This problem, denoted by

, is fundamental in data stream processing and is used to solve a number of other problems, such as heavy hitters, approximating range queries and quantiles, approximate histograms, etc..

Suppressing poly-logarithmic factors in

n

and

, for

p

 = 1 the problem is known to have

${\it \tilde{\Theta}}(1/\epsilon)$

randomized space complexity [2,4] and

${\it \tilde{\Theta}}(1/\epsilon^2)$

deterministic space complexity [6,7]. However, the deterministic space complexity of this problem for any value of

p

 > 1 is not known. In this paper, we show that the deterministic space complexity of the problem

is

${\it \tilde{ \Theta}}(n^{2-2/p}/\epsilon^2)$

for 1 < 

p

 < 2, and

$\it \Theta(n)$

for

p

 ≥ 2.

Online social network has developed significantly in recent years as a medium of communicating, sharing and disseminating information and spreading influence. Most of current research has been on understanding the property of online social network and utilizing it to spread information and ideas. In this paper, we explored the problem of how to utilize online social networks to help alleviate social problems in the physical world, for example, the drinking, smoking, and drug related problems. We proposed a

Positive Influence Dominating Set (PIDS)

selection algorithm and analyzed its effect on a real online social network data set through simulations. By comparing the size and the average positive degree of PIDS with those of a 1-dominating set, we found that by strategically choosing 26% more people into the PIDS to participate in the intervention program, the average positive degree increases by approximately 3.3 times. In terms of the application, this result implies that by moderately increasing the participation related cost, the probability of positive influencing the whole community through the intervention program is significantly higher. We also discovered that a power law graph has empirically larger dominating sets (both the PIDS and 1-dominating set) than a random graph does.

In the problem of online time series search introduced by El-Yaniv et al. [4], a player observes prices one by one over time and shall select exactly one of the prices on its arrival without the knowledge of future prices, aiming to maximize the selected price. In this paper, we extend the problem by introducing profit function. Considering two cases where the search duration is either known or unknown beforehand, we propose two optimal deterministic algorithms respectively. The models and results in the paper generalize those of El-Yaniv et al. [4].

Recently, the single-period, single-item newsboy problem with limited distributional information (e.g., range, mean, mode, variance, symmetry) has been widely studied. However, the existing newsboy models with partial information are only fit to risk-neutral inventory managers. This paper considers the newsboy problem with range information. Based on the competitive ratio analysis, which guarantees a certain performance level under all possible input sequences, we construct a framework to manage risk and reward of newsboy problems under different forecasts (i.e. certain forecasts; probability forecasts; probability distributions). Comparing the existing studies, this approach helps the newsboy flexibly choose the optimal reward strategies, according to his own risk tolerance levels and different forecasts.

We consider two semi-online scheduling problems on a single batch (processing) machine with jobs’ nondecreasing processing times and jobs’ nonincreasing processing times, respectively. Our objective is to minimize the makespan. A batch processing machine can handle up to

B

jobs simultaneously. We study an unbounded model where

B

 = ∞. The jobs that are processed together construct a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time of any job in the batch. Jobs arrive over time. Let

p

j

denote the processing time of job

J

j

. Given job

J

j

and its following job

J

j

 + 1

, we assume that

p

j

 + 1

 ≥ 

αp

j

, where

α

 ≥ 1 is a constant number, for the first problem with jobs’ nondecreasing processing times. For the second problem, we assume that

p

j

 + 1

 ≤ 

αp

j

, where 0 < 

α

< 1 is a constant number. We propose an optimal algorithm for both problems with a competitive ratio

$\frac{\sqrt{\alpha^2+4}-\alpha}{2}+1$

for the first problem and

$\frac{\sqrt{4\alpha+1}+1}{2}$

for the second problem.

We investigate the problem of on-line scheduling for jobs with arbitrary release times on

m

identical parallel machines. The goal is to minimize the makespan. We derive a best possible online algorithm with competitive ratio of 2 for

m

 = 2. For a special case that all the jobs have unit processing times, we prove that Algorithm LS has a tight bound of 3/2 for general

m

machines.

In the Multicast

k

-Tree Routing Problem, a data copy is sent from the source node to at most

k

destination nodes in every transmission. The goal is to minimize the total cost of sending data to all destination nodes, which is measured as the sum of the costs of all routing trees. This problem was formulated out of optical networking and has applications in general multicasting. Several approximation algorithms, with increasing performance, have been proposed in the last several years; The most recent ones are heavily relied on a

tree partitioning

technique. In this paper, we present a further improved approximation algorithm along the line. The algorithm has a worst case performance ratio of

$\frac 54\rho + \frac 32$

, where

ρ

denotes the best approximation ratio for the Steiner Minimum Tree problem. The proofs of the technical routing lemmas also provide some insights on why such a performance ratio could be the best possible that one can get using this tree partitioning technique.

We present a routing algorithm that finds

n

disjoint shortest paths from the source node to

n

target nodes in the

n

-dimensional hypercube in

O

(

n

3

) =

O

(log

3

N

) time, where

N

 = 2

n

, provided that such disjoint shortest paths exist which can be verified in

O

(

n

5/2

) time, improving the previous

O

(

n

3

log

n

) routing algorithm. In addition, the development of this algorithm also shows strong relationship between the problems of the disjoint shortest paths routing and matching.

In this paper we propose a new design for rearrangeable multicast switching networks, which uses the minimum number of intermediate nodes and a comparable number of switches. The newly designed 3-stage

N

×

N

switching network has the minimum 2

N

intermediate nodes and

O

(

N

5/3

) switches and an efficient routing algorithm, while the best known wide-sense nonblocking (and hence rearrangeable) multicast 3-stage network uses

O

(

N

log

N

/loglog

N

) intermediate nodes and

O

(

N

3/2

log

N

/loglog

N

) switches. The new design is constructed by adding switches to a rearrangeable unicast Clos network. The design and analysis of the design is done by a combinatorial approach, which represents a switching network as a multistage bipartite graph, and the middle stage as bipartite switch box, and routing requirements as hypergraph. The new routing algorithm is done by the edge ordering of regular hypergraphs, a technique originated from job scheduling.

In this paper, we consider the single machine scheduling problem with inventory operations. The objective is to minimize makespan subject to the constraint that the total number of tardy jobs is minimum. We show the problem is strongly NP-hard. A polynomial (1 + 1/(

m

 − 1))-approximation scheme for the problem is presented, where

m

is defined as the total job’s processing times ∑ 

p

j

divided by the capacity

c

of the storage, and an optimal algorithm for a special case of the problem, in which each job is one unit in size, is provided.

We consider the problem of minimizing the weighted number of tardy jobs (

$\sum_{j=1}^{n}w_jU_j$

) on an unbounded batch processing machine. The batch processing machine can process up to

B

(

B

 ≥ 

n

) jobs simultaneously. The jobs that are processed together form a batch, and all jobs in a batch start and complete at the same time. For a batch of jobs, the processing time of the batch is equal to the largest processing time among the jobs in this batch. In this paper, we design a fully polynomial time approximation scheme (FPTAS) to solve the unbounded batch scheduling problem

$1|B\geq n|\sum_{j=1}^{n}w_jU_j.$

This is the strongest possible polynomial time approximation result that we can derive for an NP-hard problem (unless

P

 = 

NP

holds).

In this paper, we consider the scheduling with rejection. The objective functions are to minimize the maximum completion time of the processed ones when the total compression cost is given. Firstly, we prove that the problem 1|

rej

|

C

max

/

TCP

is NP-hard, which implying that

P

m

|

rej

|

C

max

/

TCP

, 1 |

rej

,

r

j

|

C

max

/

TCP

, 1 |

rej

,

on

 − 

line

|

C

max

/

TCP

are all NP-hard. Secondly, for problem

P

m

|

rej

|

C

max

/

TCP

, we design a pseudopolynomial time dynamic programming algorithm that solves it exactly and an

FPTAS

(full polynomial time approximation scheme) when

m

is a constant. We also design a pseudopolynomial time dynamic programming algorithm and an

FPTAS

for the case of non-identical job arrival problem 1 |

rej

,

r

j

|

C

max

/

TCP

. In the end, we consider the on-line problem 1 |

rej

,

on

 − 

line

|

C

max

/

TCP

and prove that there doesn’t exist any on-line algorithm with a constant competitive ratio for it, even if the jobs only have two different release times.

In this paper we study a cross-docking problem minimizing the total flow time of inbound and outbound jobs. Using the theories and methodologies of scheduling, we formulate the problem into a two-stage scheduling problem and propose heuristics with worst-case performance analysis under parallel, uniform and open-shop machines, respectively. For each of problems studied, some polynomially solvable special cases are also introduced.

We investigate the problems of scheduling

n

jobs to

m

 = 

m

1

 + 

m

2

identical machines where

m

1

machines are always available,

m

2

machines have some specified unavailable intervals. The objective is to minimize the makespan. We assume that if a job is interrupted by the unavailable interval, it can be resumed after the machine becomes available.

We show that if at least one machine is always available, i.e.

m

1

 > 0, then the PTAS for Multiple Subset Sum problem given by Kellerer [3] can be applied to get a PTAS; otherwise,

m

 = 

m

2

, every machine has some unavailable intervals, we show that if (

m

 − 1) machines each of which has unavailable intervals with total length bounded by

α

(

n

) ·

P

sum

/

m

where

P

sum

is the total processing time of all jobs and

α

(

n

) can be any non-negative function, we can develop a (1 + 

α

(

n

) + 

ε

) −approximation algorithm for any constant 0 < 

ε

< 1; finally we show that there does not exist any polynomial time (1 + 

α

(

n

) − 

o

(1)) −approximation unless P=NP.

This paper considers an online hierarchical scheduling problem on parallel identical machines. We are given a set of

m

machines and a sequence of jobs. Each machine has a different hierarchy, and each job also has a hierarchy associated with it. A job can be assigned to a machine only if its hierarchy is no less than that of the machine. The objective is to minimize makespan. Two models are studied in the paper. For the fractional model, we present an improved algorithm and lower bounds. Both algorithm and lower bounds are based on solutions of mathematical programming. For any given

m

, our algorithm is optimal by numerical calculation. For the integral model, we present both a general algorithm for any

m

, and an improved algorithm with better competitive ratios of 2.333 and 2.610 for

m

 = 4 and 5, respectively.

In the context of scheduling and timetabling, we study a challenging combinatorial problem which is very interesting for both practical and theoretical points of view. The motivation behind it is to cope with scheduled activities which might be subject to unavoidable disruptions, such as delays, occurring during the operational phase. The idea is to preventively plan some extra time for the scheduled activities in order to be “prepared” if a delay occurs, and absorb it without the necessity of re-scheduling all the activities from scratch. This realizes the concept of designing

robust timetables

. During the planning phase, one should also consider recovery features that might be applied at runtime if disruptions occur. This leads to the concept of

recoverable robust timetables

. In this new concept, it is assumed that recovery capabilities are given as input along with the possible disruptions that must be considered. The main objective is the minimization of the overall needed time. We show that finding an optimal solution for this problem is NP-hard even though the topology of the network, which models dependencies among activities, is restricted to trees. However, we manage to design a pseudo-polynomial time algorithm based on dynamic programming.

This work presents a simple graph based heuristic that employs a roulette wheel selection mechanism for solving exam timetabling problems. We arrange exams in non-increasing order of the number of conflicts (degree) that they have with other exams. The difficulty of each exam to be scheduled is estimated based on the degree of exams in conflict. The degree determines the size of a segment in a roulette wheel, with a larger degree giving a larger segment. The roulette wheel selection mechanism selects an exam if the generated random number falls within the exam’s segment. This overcomes the problem of repeatedly choosing and scheduling the same sequence of exams. We utilise the proposed Roulette Wheel Graph Colouring heuristic on the un-capacitated Carter’s benchmark datasets. Results showed that this simple heuristic is capable of producing feasible solutions for all 13 instances.

Consider a company that manufactures perishable goods. The company relies on a third party to deliver goods, which picks up delivery products at regular times. At each delivery time, there is a time window that products can be produced to be delivered at that delivery time. Suppose we have a set of jobs with each job specifying its delivery time, processing time and profit. The company can earn the profit of the job if the job is produced and delivered at its specified delivery time. From the company point of view, we are interested in picking a subset of jobs to produce and deliver so as to maximize the total profit. The jobs that are not picked will be discarded without penalty. We consider both the single machine case and the parallel and identical machines case.

In this article we consider two kinds of profits: (1) arbitrary profit, (2) profit proportional to its processing time. In the first case, we give a fully polynomial time approximation scheme (FPTAS) for a single machine with running time

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

. In the second case, we give a faster FPTAS for a single machine with running time

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

. All of our algorithms can be extended to parallel and identical machines with a degradation of performance ratios.

This paper addresses the problem of fault-tolerant many-to-one routing in static wireless networks with asymmetric links, which is important in both theoretical and practical aspects. The problem is to find a minimum energy subgraph for a given subset and a destination node such that there are

k

node-disjoint paths from each node in the subset to the destination node in the subgraph. We prove that the problem is NP-hard, and propose two efficient heuristic approaches, namely, the minimum weight

k

node-disjoint paths based (MWkNDPB) approach and the minimum energy

k

node-disjoint paths based (MEkNDPB) approach. Extensive simulations have been conducted to show that proposed algorithms are efficient.

In this paper, we study the minimum energy symmetric connectivity problem in wireless sensor networks. This problem is to assign transmission power to each sensor node in a wireless sensor network such that all the sensor nodes are connected by bidirectional links and the overall power consumption is minimized. The determined transmission powers must support the communication session between each pair of nodes along a single-hop path or a multi-hop path. We view this feature as strong symmetric connectivity defined on a digraph. We present two mixed integer programming formulations involving an exponential number of constraints. By introducing some logical constraints, we give the first formulation. Based on this formulation, we further produce some strong cuts which result in the second stronger formulation. Using these formulations, we then devise a branch-and-cut algorithm. Computational results demonstrate that our algorithm is an efficient algorithm for the instances with up to 100 nodes.

In this paper we discuss minimum energy broadcast routing with directional antennas in ad hoc and sensor networks. We assume that the network consists of sensor nodes whose antennas are

Switched beam

directional antennas. The problem of our concern is: given a set

V

with

n

nodes and each node

v

i

has

l

(

i

) transmission

directions

(i.e. the antenna sectors) and a broadcast request sourced at

s

, how to find a broadcast tree rooted at

s

and spanning all nodes in

V

such that the total energy is minimized. This problem involves with the choice of transmitting nodes and their transmission

directions

, which is NP-hard. We propose a |

V

|-approximation algorithm and one heuristic for the problem. Extensive simulations have demonstrated the efficiency of our algorithms.

As an important technique, traffic grooming aggregates the traffic of multiple connections into a single wavelength channel, and significantly increases the utilization of bandwidth of wavelength channels. In this paper, for the problem of grooming multicast traffics in unidirectional SONET/WDM rings, an efficient approximation algorithms with approximation factor of 2

lng

 + 

lnM

 + 

o

(

ln

(

M

·

g

)) for any given number of multicast requests

M

and grooming factor

g

is proposed.

The goal for the problem of efficient grooming of given non-uniform multicast traffic demands on a unidirectional SONET/WDM ring is to try to minimize the network cost as given by (i) the number of wavelengths required per fiber and (ii) the number of electronic Add- Drop Multiplexers (ADMs) required in the ring. The problem with cost function (i) can be reduced to a corresponding traffic grooming problem for unicast traffic which can then be modeled as a standard circular-arc graph coloring problem.The function (ii) is a main research topic in recent studies.The problem is NP hard for both the cost functions. For the problem with fuction (ii), we present a algorithm with better approximation ratio,

$ \frac{3}{2}(\frac{N}{{N - 1}} + 1)$

. Additionally, we give a lower bound and upper bound for the number of ADMs.