Algorithmic Aspects in Information and Management

Can we optimally solve

Max

2

SAT

in (say) time (|

F

| log|

F

|) where |

F

| is the length of formula

F

. Of course, since

Max

2

SAT

is

NP

-complete, we can confidently rely on our strongly held belief that no

NP

-hard problem can be solved optimally in polynomial time. But obtaining

unconditional

complexity lower bounds (even linear or near linear bounds) remains the central challenge of complexity theory. In the complementary fields of complexity theory and that of algorithm design and analysis, we ask questions such as “what is the best polynomial time approximation ratio” that can be achieved for

Max

2

SAT

. The best negative results are derived from the beautiful development of PCP proofs. In terms of obtaining better approximation algorithms, we appeal to a variety of algorithmic techniques, including very basic techniques such as greedy algorithms, dynamic programming (with scaling), divide and conquer, local search and some more technically involved methods such as LP relaxation and randomized rounding, semi-definite programming (see [34] and [30] for an elegant presentation of these randomized methods and the concept of derandomization using conditional expectations). A more refined question might ask “what is the best approximation ratio (for a given problem such as

Max

2

SAT

) that can be obtained in (say) time

O

(

n

log

n

)” where

n

is the length of the input in some standard representation of the problem. What algorithmic techniques should we consider if we are constrained to time

O

(

n

log

n

)?

Self-assembly is the ubiquitous process by which objects autonomously assemble into complexes. This phenomenon is common in nature and yet is poorly understood from mathematical and programming perspectives. It is believed that self-assembly technology will ultimately permit the precise fabrication of complex nanostructures. Of particular interest is DNA self-assembly. Double and triple crossover DNA molecules have been designed that can act as four-sided building blocks for DNA self-assembly. Experimental work has been done to show the effectiveness of using these building blocks to assemble DNA crystals and perform DNA computation. With these building blocks (called

tiles

) in mind, researchers have considered the power of the

tile

self-assembly model.

The tile assembly model extends the theory of Wang tilings of the plane by adding a natural mechanism for growth. Informally, the model consists of a set of four sided Wang tiles whose sides are each associated with a type of glue. The bonding strength between any two glues is determined by a

glue function

. A special tile in the tile set is denoted as the

seed

tile. Assembly takes place by starting with the seed tile and attaching copies of tiles from the tile set one by one to the growing seed whenever the total strength of attraction from the glue function meets or exceeds a fixed parameter called the

temperature

.

Algorithmic DNA self-assembly is both a form of nanotechnology and a model of DNA computing. As a computational model, algorithmic DNA self-assembly encodes the input of a computational problem into DNA patterns and then manipulates these patterns to produce new DNA patterns that encode the desired output of the computational problem. As a nanotechnology, algorithmic DNA self-assembly aims to design tiles with carefully chosen glue types on their four sides. Two tiles are said to be of different types if their sides have different glue types. Useful tile types are nontrivial to design but relatively easy to duplicate in large quantity. A key design challenge for algorithmic DNA self-assembly is to use only a small number of different tile types to assemble a target nanostructure.

This talk will survey recent results in algorithmic DNA self-assembly and discuss future research directions.

This paper investigates the online scheduling problem on parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels. Hence each job and machine are labelled with the GoS levels, and each job can be processed by a particular machine only when the GoS level of the job is not less than that of the machine. The goal is to minimize the makespan. In this paper, we consider the problem with two GoS levels. It assumes that the GoS levels of the first

k

machines and the last

m

–

k

machines are 1 and 2, respectively, and every job has a GoS level of 1 alternatively or 2. We first prove the lower bound of the problem under consideration is at least 2. Then we discuss the performance of algorithm

AW

presented in [2] for the problem and show it has a tight bound of 4 – 1/

m

. Finally, We present an approximation algorithm with a competitive ratio of

$\frac{12+4\sqrt{2}}{7}\approx 2.522$

.

In online dial-a-ride problem with time-windows, requests for rides consist of two points in a metric space, a source and a destination. One server with some finite capacity is required to transports a specified amount of goods for requests from the sources to the destinations. Calls for rides come in while the server is travelling. Each request also specifies a deadline. If a request is not be served by its deadline, it will be called off. The server travels at unit speed in the metric space and the goal is to plan the motion of the server in an online way so that the maximum number of requests (or the maximum quantity of goods) is met by the deadlines of the requests. Usually it is assumed that the server knows the complete information on the ride when the requests are presented. We study this problem under a restricted information model. At the release time of one request, only the information on the source is presented. The server does not have the information on the destination until it reaches the source of the request. This models, e.g. the taxi problem, or elevator problem. We study the problem in the

uniform

metric space and

K-constrained

metric space. We perform competitive analysis of two deterministic strategies in the two types of metric spaces. The competitive ratios of the strategies are obtained. We also prove a lower bound on the competitive ratio of any deterministic algorithm of

Z

for the

uniform

metric space and of

KZ

for the

K-constrained

metric space, where

Z

denotes the capacity of the server and

K

denotes the diameter of the metric space.

In this paper, motivated by on-line admission control in the hard deadline model, we deal with the following scheduling problem. We are given

m

identical machines (multi-streams). All jobs (requests) have identical processing time. Each job is associated with a release time and a deadline, neither of which is known until the job arrives. As soon as a job is available, we must immediately decide if the job is accepted or rejected. If a job is accepted, then it must be completed no later than its deadline. The goal is to maximize the total number of jobs accepted. The one-machine case has been extensively studied while little is known for multiple machines. Our main result is deriving a nontrivial optimal online algorithm with competitive ratio

$\frac{3}{2}$

for the two-machine case by carefully investigating various strategies. Deterministic lower bounds for the general case are also given.

We study the nonpreemptive online scheduling of jobs with deadlines and weights. The goal of the scheduling algorithm is to maximize the total weight of jobs completed by their deadlines. As a special case, the weights may be given as the processing times of jobs, where the job instance is said to have

uniform value density

.

Most previous work of nonpreemptively scheduling jobs online concentrates on a single machine and uniform value density. For the single machine, Goldwasser [6] shows a matching upper bound and lower bound of

$(2 + \frac{1}{\kappa})$

on the best competitive ratio, where every job can be delayed for at least

κ

times its processing time before meeting its deadline. This paper is concerned with multiple machines. We provide a

$(7 + 3\sqrt{\frac{1}{\kappa}})$

-competitive algorithm defined on multiple machines. Also we consider arbitrary value density, where jobs have arbitrary weights. We derive online scheduling algorithms on a single machine as well as on multiple machines.

consider the relationship of two fixed point theorems for direction-preserving discrete correspondences. We show that, for any space of no more than three dimensions, the fixed point theorem [4] of Iimura, Murota and Tamura, on integrally convex sets can be derived from Chen and Deng’s fixed point theorem [2] on lattices by extending every direction-preserving discrete correspondence over an integrally convex set to one over a lattice. We present a counter example for the four dimensional space. Related algorithmic results are also presented for finding a fixed point of direction-preserving correspondences on integrally convex sets, for spaces of all dimensions.

We investigate LP-polytopes generated by mean payoff games and their properties, including the existence of tight feasible solutions of bounded size. We suggest a new associated algorithm solving a linear program and transforming its solution into a solution of the game.

We study atomic routing games on networks in which players choose a path with the objective of minimizing the

maximum congestion

along the edges of their path. The social cost is the global maximum congestion over all edges in the network. We show that the

price of stability

is 1. The

price of anarchy

,

PoA

, is determined by topological properties of the network. In particular,

PoA

=

O

(ℓ+ log

n

), where ℓ is the length of the longest path in the player strategy sets, and

n

is the size of the network. Further,

κ

– 1 ≤

PoA

≤

c

(

κ

2

+ log

2

n

), where

κ

is the length of the longest cycle in the network, and

c

is a constant.

This paper formulates a model of advertising prices in which a homogeneous product is not intended for sales at conventional stores. The product is sold by means of advertising instead. Applications of this model can be found on numerous sales activities include, for example, insurance companies, television shopping channels and Internet e-tailers who advertise their products and prices by sending e-mails to potential buyers or by means of popup windows. This paper makes endogenous both firm advertising and price strategies in the model.

It is well known that faithful (i.e. dependency preserving) decompositions of relational database schemas into Boyce-Codd Normal Form (BCNF) do not always exist, depending on the set of functional dependencies given, and that the corresponding decision problem is NP-hard. The only algorithm to guarantee both faithfulness and BCNF (if possible) proposed so far in [Os79] is a brute-force approach which always requires exponential time. To be useful in practice, e.g. in automated design tools, we require more efficient means.

In this paper we present an algorithm which always finds a faithful BCNF decomposition if one exists, and which is usually efficient, and exponential only in notorious cases.

Many of scheduling algorithms that provide a predefined bandwidth to a traffic flow fall into a category of Latency-rate (

$\mathcal{LR}$

) server. A series of

$\mathcal{LR}$

servers can be viewed as a virtual node with an

$\mathcal{LR}$

server of the

latency

which is simply the summation of individual latencies of actual

$\mathcal{LR}$

servers. Deficit Round Robin (DRR) is such an

$\mathcal{LR}$

server and the simplest one to implement, so that it is adopted in many real systems. In this research we suggest a novel policy of Instant Service, which is applicable to any round-robin schedulers. We then apply this policy to DRR, make a variation called DRR with Instant Service (DRR-IS), and analyze it. We prove that the DRR-IS is still an

$\mathcal{LR}$

server. We calculate its latency and investigate its fairness characteristics. We demonstrate the DRR-IS, compared with DRR, provides about 30% better latency while have the same complexity and the same fairness.

We introduce a novel invertible transform for two- dimensional data which has the objective of reordering the matrix so it will improve its (lossless) compression at later stages. The transform requires to solve a computationally hard problem for which a randomized algorithm is used. The inverse transform is fast and can be implemented in linear time in the size of the matrix. Preliminary experimental results show that the reordering improves the compressibility of digital images.

We give logarithmic approximation algorithms for the non-metric uncapacitated multicommodity and multilevel facility location problems. The former algorithms are optimal up to a constant factor, the latter algorithm is far away from the lower bound, but it is the first algorithm to solve the general multilevel problem. To solve the multicommodity problem, we also define a new problem, the friendly tour operator problem, which we approximate by a greedy algorithm.

Given

d

> 2 and a set of

n

grid points

Q

in

$\Re^d$

, we design a randomized algorithm that finds a

w

-wide separator, which is determined by a hyper-plane, in

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

sublinear time such that

Q

has at most

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

points one either side of the hyper-plane, and at most

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

points within

$\frac{w}{2}$

distance to the hyper-plane, where

c

d

is a constant for fixed

d

. In particular,

c

3

= 1.209. To our best knowledge, this is the first sublinear time algorithm for finding geometric separators. Our 3D separator is applied to derive an algorithm for the protein side-chain packing problem, which improves and simplifies the previous algorithm of Xu [26].

For a given

x

-monotone polygonal curve each of whose edge lengths is between

$\underline{l}$

and

$2\underline{l}$

, we consider the problem of approximating it by another

x

-monotone polygonal curve using points of a square grid so that there exists a small number of different edge lengths and every edge length is between

$\underline{l}$

and

$\beta \underline{l}$

, where

β

is a given parameter satisfying 1≤

β

≤2. Our first algorithm computes an approximate polygonal curve using fixed square grid points in

O

((

n

/

α

4

)log(

n

/

α

)) time. Based on this, our second algorithm finds an approximate polygonal curve as well as an optimal grid placement simultaneously in

O

((

n

3

/

α

12

)log

2

(

n

/

α

)) time, where

α

is a parameter that controls the closeness of approximation. Based on the approximate polygonal curve, we shall give an algorithm for finding a uniform triangular mesh for an

x

-monotone polygon with a constant number of different edge lengths.

We consider a variant of Heilbronn’s triangle problem by asking for fixed integers

d

,

k

≥2 and any integer

n

≥

k

for a distribution of

n

points in the

d

-dimensional unit cube [0,1]

d

such that the minimum volume of the convex hull of

k

points among these

n

points is as large as possible. We show that there exists a configuration of

n

points in [0,1]

d

, such that, simultaneously for

j

= 2, ...,

k

, the volume of the convex hull of any

j

points among these

n

points is Ω( 1/

n

(j − − 1)/(1 + |d − − j + 1|)

). Moreover, for fixed

k

≥

d

+1 we provide a deterministic polynomial time algorithm, which finds for any integer

n

≥

k

a configuration of

n

points in [0,1]

d

, which achieves, simultaneously for

j

=

d

+1, ...,

k

, the lower bound Ω( 1/

n

(j − − 1)/(1 + |d − − j + 1|)

) on the minimum volume of the convex hull of any

j

among the

n

points.

Given two sets

A

and

B

of

m

non-intersecting line segments in the plane, we show how to compute in

O

(

m

log

m

) time a data structure that uses

O

(

m

) space and allows to answer the following query in

O

(log

m

) time: Given a parabola

γ

:

y

=

ax

2

+

bx

+

c

, does

γ

separate

A

and

B

? This structure can be used to build a data structure that stores a simple polygon and allows ray-shooting queries along parabolic trajectories with vertical main axis. For a polygon with complexity

n

, we can answer such “stone throwing” queries in

O

(log

2

n

) time, using

O

(

n

log

n

) space and

O

(

n

log

2

n

) preprocessing time. This matches the best known bound for circular ray shooting in simple polygons.

In this paper we deal with sensitivity analysis of combinatorial optimization problems and its fundamental term, the tolerance. For three classes of objective functions (

$\Sigma, \Pi, {\mbox{MAX}}$

) we give some basic properties on upper and lower tolerances. We show that the upper tolerance of an element is well defined, how to compute the upper tolerance of an element, and give equivalent formulations when the upper tolerance is +∞ or > 0. Analogous results are given for the lower tolerance and some results on the relationship between lower and upper tolerances are given.

In this note we discuss a class of exponential penalty function policies recently proposed by Iyengar and Sigman for controlling a stochastic knapsack. These policies are based on the optimal solution of some related deterministic linear programs. By finding explicitly their optimal solution, we reinterpret the exponential penalty function policies and show that they belong to the class of threshold policies. This explains their good practical behavior, facilitates the comparison with the thinning policy, simplifies considerably their analysis and improves the bounds previously proposed.

The bottleneck optimization problem is to find a feasible solution that minimizes the bottleneck cost. In this paper, we consider the inverse bottleneck optimization problems with bound constraints on modification under weighted

l

1

norm, weighted sum-Hamming distance and weighted bottleneck-Hamming distance. That is, given a feasible solution

F

*

, we aim to modify the cost function under some measure such that

F

*

becomes an optimal solution to the bottleneck optimization problem. We show that the inverse problem under weighted

l

1

norm and weighted sum-Hamming distance can be reduced to

O

(

m

) minimum cut problems, while the inverse problem under weighted bottleneck-Hamming distance can be reduced to

O

(log

m

) cut feasibility problems, where

m

= |

E

|.

In this paper, we consider the quickest flow problem in a network which consists of a directed graph with capacities and transit times on its arcs. We present an

O

(

n

log

n

) time algorithm for the quickest flow problem in a network of grid structure with uniform arc capacity which has a single sink where

n

is the number of vertices in the network.

We study an extension of the set cover problem, the connected set cover problem, the problem is to find a set cover of minimal size that satisfies some connectivity constraint. We first propose two algorithms that find optimal solutions for two cases, respectively, and then we propose one approximation algorithm for a special case that has the best possible performance ratio. At last we consider how to apply the obtained result to solve a wavelength assignment problem in all optical networks.

In this paper, a branch and bound algorithm for computing the treewidth of a graph is presented. The method incorporates extensions of existing results, and uses new pruning and reduction rules, based upon properties of the adopted branching strategy. We discuss how the algorithm can not only be used to obtain exact bounds for the treewidth, but also to obtain upper and/or lower bounds. Computational results of the algorithm are presented.

Given a class of graphs

${\cal G}$

, a graph G is a

probe graph of

${\cal G}$

if its vertices can be partitioned into two sets ℙ (the probes) and ℕ (nonprobes), where ℕ is an independent set, such that G can be embedded into a graph of

${\cal G}$

by adding edges between certain vertices of ℕ. If the partition of the vertices into probes and nonprobes is part of the input, then we call the graph a

partitioned probe graph of

${\cal G}$

. We give the first polynomial-time algorithm for recognizing partitioned probe distance-hereditary graphs. By using a novel data structure for storing a multiset of sets of numbers, the running time of this algorithm is

${O}(\mathfrak\it{n}^2)$

, where

$\mathfrak\it{n}$

is the number of vertices of the input graph. We also show that the recognition of both partitioned and unpartitioned probe cographs can be done in

${O}(\mathfrak\it{n}^2)$

time.

We describe an improved algorithm for solving the

Maximum Clique

problem in a graph using a novel sampling technique combined with a parameterized

k

-vertex cover algorithm. Experimental research shows that this approach greatly improves the execution time of the search, and in addition, provides intermediate results during computation. We also examine a very effective heuristic for finding a large clique that combines our sampling approach with fast independent set approximation. In experiments using the DIMACS benchmark, the heuristical approach established new lower bounds for four instances and provides the first optimal solution for an instance unsolved until now. The heuristic competitively matched the accuracy of the current best exact algorithm in terms of correct solutions, while requiring a fraction of the run time. Ideally such an approach could be beneficial as a preprocessing step to any exact algorithm, providing an accurate lower bound on the maximum clique, in very short time.

In this paper we present the first set of approximation and inapproximability results for the Exemplar Breakpoint Distance Problem. Our inapproximability results hold for the simplest case between only two genomes

${\cal G}$

and

${\cal H}$

, each containing only one sequence of genes (possibly with repetitions).

– For the general Exemplar Breakpoint Distance Problem, we prove that the problem does not admit any approximation unless P=NP; in fact, this result holds even when a gene appears in

${\cal G}$

(

${\cal H}$

) at most three times.

– Even on a weaker definition of approximation (which we call weak approximation), we show that the problem does not admit a weak approximation with a factor

m

1 − − ε

, where

m

is the maximum length of

${\cal G}$

and

${\cal H}$

.

– We present a factor-2(1 + log

n

) approximation for an interesting special case, namely, one of the two genomes is a

k-span

genome (i.e., all genes in the same gene family are within a distance

k

=

O

(log

n

)), where

n

is the number of gene families in

${\cal G}$

and

${\cal H}$

.

We study the

λ

-seed problem of a string in this paper. Given a string

x

of length

n

and an integer

λ

, the

λ

-seed problem is to find all the sets of

λ

substrings of

x

that cover a superstring of

x

, assuming that each element of the set is of equal length. We present an efficient algorithm that can compute all the

λ

-seeds of

x

in

O

(

n

2

) time.

We study the subsequence packing problem: given a string

T

and a collection of strings {

S

i

}, find disjoint subsequences {

T

i

} of

T

with maximum total length such that each

T

i

is a subsequence of

S

i

. We prove the NP-completeness of the decision problem, present the first non-trivial deterministic approximation, and show its applications to DNA sequencing verification and preemptive job shop scheduling with two machines.

In this paper, I present a frequency reassignment problem (FRP) arising from the installation of new base stations for capacity expansion in mobile telecommunication systems, and develop an integer programming (IP) formulation along with some valid inequalities. Also, I develop a novel decomposition based heuristic algorithm. Computational results show that the developed valid inequalities are quite strong, and that the developed heuristic algorithm finds a feasible solution of good quality within reasonable time bound.

We propose polynomial time approximation algorithms for minimum span channel (frequency) assignment problems, which is known to be NP-hard. Let

α

be the approximation ratio of our algorithm and

W

≥2 be the maximum of numbers of channels required in vertices. If an instance is defined on a perfect graph

G

, then

$\alpha \leq 1+(1+\frac{1}{W-1})\text{H}_{\omega(G)}$

, where

$\text{H}_i$

denotes the

i

-th harmonic number. For any instance defined on a unit disk graph

G

,

α

is less than or equal to

$(1+\frac{1}{W-1})(3\text{H}_{\omega(G)}-1)$

. If a given graph is 4 or 3 colorable,

α

is bounded by

$(2.5+\frac{1.5}{W-1})$

and

$(2+\frac{1}{W-1})$

, respectively. We also discuss well-known practical instances called Philadelphia instances and propose an algorithm with

α

≤12/5.

The non-homogeneous version of the range assignment problem in Ad-Hoc wireless network is studied in the context of information

broadcast

and

accumulation

. Efficient algorithms are presented for the unbounded and bounded-hop

broadcast

problems for a set of radio-stations when they are placed on a straight line. This improves time complexity of the existing results for the same two problems by a factor of

n

, where

n

is the number of radio-stations [2]. An easy to implement algorithm for the unbounded version of

accumulation

problem is also presented for the non-homogeneous version of the range assignment problem. Its worst case running time complexity is

O

(

n

2

). The same algorithm works when the radio-stations are placed in

R

d

.

Due to the increasing security threats in the Internet, new overlay network architectures have been proposed to secure privileged services. In these architectures, the application servers are protected by a defense perimeter where only traffic from entities called servelets are allowed to pass. End users must be authorized and can only communicate with entities called access points (APs). APs relay authorized users’ requests to servelets, which in turn pass them to the servers. The identity of APs are publicly known while the servelets are typically secret. All communications are done through the public Internet. Thus all the entities involved forms an overlay network. The main component of this distributed system consists of

n

APs. and

m

servelets. A design for a network is a bipartite graph with APs on one side, and the servelets on the other side. If an AP is compromised by an attacker, all the servelets that are connected to it are subject to attack. An AP is

blocked

, if all servelets connected to it are subject to attack. We consider two models for the failures: In the

average case model

, we assume that each AP

i

fails with a given probability

p

i

. In the

worst case model

, we assume that there is an adversary that knowing the topology of the network, chooses at most

k

APs to compromise. In both models, our objective is to design the connections between APs and servelets to minimize the (expected/worst-case) number of blocked APs. In this paper, we give a polynomial-time algorithm for this problem in the average-case model when the number of servelets is a constant. We also show that if the probability of failure of each AP is at least 1/2, then in the optimal design each AP is connected to only one servelet (we call such designs

star-shaped

), and give a polynomial-time algorithm to find the best star-shaped design. We observe that this statement is not true if the failure probabilities are small. In the worst-case model, we show that the problem is related to a problem in combinatorial set theory, and use this connection to give bounds on the maximum number of APs that a perfectly failure-resistant design with a given number of servelets can support. Our results provide the

first

rigorous theoretical foundation for practical secure overlay network design.

This paper discusses the portfolio selection problem based on the possibilistic theory. The possibilistic portfolio model with general constraints to investment is proposed by means of possibilistic mean value and possibilistic variance. The conventional probabilistic mean-variance model can be simplified under the assumption that the returns of assets are triangular fuzzy numbers. Finally, a numerical example of the portfolio selection problem is given to illustrate our proposed effective means and approaches.

Discount auction is a market mechanism for buying heterogeneous items in a single auction. The suppliers submit discount bids, which consist of two parts: the individual cost for each of the items and discounts based on the number of items procured. The winner determination problem faced by the buyer is to determine the winning suppliers and their corresponding winning items, such that the total cost of procurement is minimized. This problem is

${\cal NP}$

-hard and in this paper we propose a novel branch and bound algorithm called as

branch on price

, which uses a tight integer programming formulation with valid inequalities. Computational experiments show that the proposed algorithm is many folds faster than the existing algorithm.

We derive a polynomial time algorithm to compute a stable solution in a mixed matching market from an auction procedure as presented by Eriksson and Karlander [5]. As a special case we derive an

$\mathcal{O}(nm)$

algorithm for bipartite matching that does not seem to have appeared in the literature yet.