Frontiers in Algorithmics

In this talk, we present a general survey on parallel computing. The main contents include parallel computer system which is the hardware platform of parallel computing, parallel algorithm which is the theoretical base of parallel computing, parallel programming which is the software support of parallel programming, parallel application which is the development impetus of parallel computing. Specially, we also introduce some enabling technologies of parallel application. We argue that the parallel computing research should form an integrated methodology of “architecture-algorithm-programming-application”. Only in this way, parallel computing research becomes continuous development and more realistic.

For any function f(x, y), its communication complexity is the minimum number of bits needed to be exchanged between two parties holding integers x and y respectively. Invented thirty years ago, communication complexity has been a central research area in theoretical computer science with rich applications to algorithmic problems. In this talk, we give an overview of computational complexity, high-lighting several notable recent results and the diverse mathematical techniques needed for deriving such results.

Power management has become an important issue in the design of information systems. Computer industry struggles to cope with the energy and cooling costs for servers. The wireless ad hoc network community has to invent clever schemes to conserve the limited power available to individual small radio devices. The algorithmic challenges in studying these problems involve both proper mathematical modeling and finding solutions to the resulted optimization problems. In this talk, we will look at some sample problems of power management in computers and wireless networks, discussing their mathematical modeling and efficient algorithms. It will be seen that graph theory and computational geometry can often play a role in providing effective solutions.

We introduce networks with additive losses and gains on the arcs. If a positive flow of

x

units enter an arc

a

, then

x

 + 

g

(

a

) units exit. Arcs may increase or consume flow, i.e., they are gainy or lossy. Such networks have various applications, e.g., in financial analysis, transportation, and data communication.

Problems in such networks are generally intractable. In particular, the shortest path problem is

NP

-hard. However, there is a pseudo-polynomial time algorithm for the problem with nonnegative costs and gains. The maximum flow problem is strongly

NP

-hard, even in unit-gain networks and in networks with integral capacities and loss at most three, and is hard to approximate. However, it is solvable in polynomial time in unit-loss networks using the Edmonds-Karp algorithm.

Our

NP

-hardness results contrast efficient polynomial time solutions of path and flow problems in standard and in so-called generalized networks with multiplicative losses and gains.

We give a linear-time algorithm for computing the edge search number of cographs, thereby proving that this problem can be solved in polynomial time on this graph class. With our result, the knowledge on graph searching of cographs is now complete: node, mixed, and edge search numbers of cographs can all be computed efficiently. Furthermore, we are one step closer to computing the edge search number of permutation graphs.

Recently high-trustworthy software has been proposed and advocated by many academic and engineering communities. High-trustworthy algorithm is core to high-trustworthy software. In this paper, using PAR method we derive formally a high-trustworthy generic algorithmic program for solving general single-source path problems. Common characteristics of these path problems can be abstracted into an algebra structure-dioid. Some typical graph algorithms, such as Bellman-Ford single-source shortest path algorithm, Reachability problem algorithm, and Bottleneck problem algorithm, etc. are all instances of the generic algorithmic program. Our approach mainly employs formal derivation technology and generic technology. Main contribution is combining the two techniques into a systemic approach, which aims to develop high-trustworthy generic algorithmic program for solving general problems. According to our approach, the correctness, reliability, safety and development efficiency of algorithmic programs are greatly improved. It is expected to be a promising approach to develop high-trustworthy generic algorithmic program.

In this paper, we explore the design of algorithms for the problem of checking whether an

undirected

graph contains a negative cost cycle (UNCCD). It is known that this problem is significantly harder than the corresponding problem in directed graphs. Current approaches for solving this problem involve reducing it to either the

b

-matching problem or the

T

-join problem. The latter approach is more efficient in that it runs in

O

(

n

3

) time on a graph with

n

vertices and

m

edges, while the former runs in

O

(

n

6

) time. This paper shows that instances of the UNCCD problem, in which edge weights are restricted to be in the range { − 

K

··

K

} can be solved in

O

(

n

2.75

·log

n

) time. Our algorithm is basically a variation of the

T

-join approach, which exploits the existence of extremely efficient shortest path algorithms in graphs with integral positive weights. We also provide an implementation profile of the algorithms discussed.

The covering-based routing, which maintains a compact routing table and reduces the costs of communications and matching computations by removing redundant subscriptions, is a typical optimization method in content-based distributed publish/subscribe systems. Although it has been widely used as a fundamental part in acyclic systems, no research on covering-based routing for cyclic networks has been reported as we know. As the cyclic systems become a new focus of research for they have advantages over acyclic ones, developing covering-based protocols and algorithms for routing optimization on cyclic networks is significant to distribute publish/subscribe systems. Since current covering optimization methods of acyclic topologies can not be directly utilized on cyclic networks, this paper contributes the Cyclic Covering-Based Routing protocol with corresponding algorithms to support covering-based protocol in cyclic network, which enable efficiently path sharing among related subscriptions with covering relationships so as to reduce the costs of communications and matching computations in cyclic systems. Correctness proofs of the proposed algorithms are also presented in this paper.

Web search engines use link-based reputation systems (e.g. PageRank) to measure the importance of web pages, giving rise to the strategic manipulations of hyperlinks by spammers and others to boost their web pages’ reputation scores. Hopcroft and Sheldon [10] study this phenomenon by proposing a network formation game in which nodes strategically select their outgoing links in order to maximize their PageRank scores. They pose an open question in [10] asking whether all Nash equilibria in the PageRank game are insensitive to the restart probability

α

of the PageRank algorithm. They show that a positive answer to the question would imply that all Nash equilibria in the PageRank game must satisfy some strong algebraic symmetry, a property rarely satisfied by real web graphs. In this paper, we give a negative answer to this open question. We present a family of graphs that are Nash equilibria in the PageRank game only for certain choices of

α

.

A cop-robber guarding game is played by the robber-player and the cop-player on a graph

G

with a bipartition {

R

,

C

} of the vertex set. The robber-player starts the game by placing a robber (her pawn) on a vertex in

R

, followed by the cop-player who places a set of cops (her pawns) on some vertices in

C

. The two players take turns in moving their pawns to adjacent vertices in

G

. The cop-player moves the cops within

C

to prevent the robber-player from moving the robber to any vertex in

C

. The robber-player wins if it gets a turn to move the robber onto a vertex in

C

on which no cop situates, and the cop-player wins otherwise. The problem is to find the minimum number of cops that admit a winning strategy to the cop-player. It has been shown that the problem is polynomially solvable if

R

induces a path, whereas it is NP-complete if

R

induces a tree. It was open whether it is solvable or not when

R

induces a cycle. This paper answers the question affirmatively.

The non-existence of arbitrage in an efficient foreign exchange markets is widely believed. In this paper, we deploy a forecasting model to predict foreign exchange rates and apply the covered interest parity to evaluate the possibility of an arbitrage opportunity. Surprisingly, we substantiate the existence of covered interest arbitrage opportunities in the exchange rate forecasting market even with transaction costs. This also implies the inefficiency of the market and potential market threats of profit-seeking investors. In our experiments, a hybrid model GA-BPNN which combines adaptive genetic algorithm with back-propagation neural network is used for exchange rate forecasting.

In this article, we define a new variant of Cai-Fürer-Immerman construction. With this construction and some conditions of Dawar and Richerby, we are able to show that inflationary fixed point logic with counting (IFP+C) does not capture PTIME on the class of balanced graphs.

Matching geometric objects with respect to their Hausdorff distance is a well investigated problem in Computational Geometry with various application areas. The variant investigated in this paper is motivated by the problem of determining a matching (in this context also called

registration

) for neurosurgical operations. The task is, given a sequence

$\mathcal{P}$

of weighted point sets (anatomic landmarks measured from a patient), a second sequence

$\mathcal{Q}$

of corresponding point sets (defined in a 3D model of the patient) and a transformation class

$\mathcal{T}$

, compute the transformations

$t\in\mathcal{T}$

that minimize the

weighted

directed Hausdorff distance of

$t(\mathcal{P})$

to

$\mathcal{Q}$

. The weighted Hausdorff distance, as introduced in this paper, takes the weights of the point sets into account. For this application, a weight reflects the precision with which a landmark can be measured.

We present an exact solution for translations in the plane, a simple 2-approximation as well as a FPTAS for translations in arbitrary dimension and a constant factor approximation for rigid motions in the plane or in ℝ

3

.

Computing the visibility polygon, VP, of a point in a polygonal scene, is a classical problem that has been studied extensively. In this paper, we consider the problem of computing VP for any query point efficiently, with some additional preprocessing phase. The scene consists of a set of obstacles, of total complexity

O

(

n

). We show for a query point

q

,

VP

(

q

) can be computed in logarithmic time using

O

(

n

4

) space and

O

(

n

4

log

n

) preprocessing time. Furthermore to decrease space usage and preprocessing time, we make a tradeoff between space usage and query time; so by spending

O

(

m

) space, we can achieve

$O(n^2 \log (\sqrt{m}/n) / \sqrt{m})$

query time, where

n

2

 ≤ 

m

 ≤ 

n

4

. These results are also applied to angular sorting of a set of points around a query point.

For a set of

n

points in the plane, we consider the axis–aligned (

p

,

k

)

-Box Covering

problem: Find

p

axis-aligned, pairwise disjoint boxes that together contain exactly

n

 − 

k

points. Here, our boxes are either squares or rectangles, and we want to minimize the area of the largest box. For squares, we present algorithms that find the solution in

O

(

n

 + 

k

log

k

) time for

p

 = 1, and in

O

(

n

log

n

 + 

k

p

log

p

k

) time for

p

 = 2,3. For rectangles we have running times of

O

(

n

 + 

k

3

) for

p

 = 1 and

O

(

n

log

n

 + 

k

2 + 

p

log

p

 − 1

k

) time for

p

 = 2,3. In all cases, our algorithms use

O

(

n

) space.

In this paper, we present techniques and algorithms for processing an offline sequence of insertion and query operations and for related problems. Most problems we consider are solved optimally in linear time by our algorithms, which are based on a new geometric modeling and interesting techniques. We also discuss some applications to which our algorithms and techniques can be applied to yield efficient solutions.

Data access time becomes the main bottleneck in applications dealing with large-scale graphs. Cache-oblivious layouts, constructed to minimize the geometric mean of arc lengths of graphs, have been adapted to reduce data access time during random walks on graphs. In this paper, we present a constant factor approximation algorithm for the Minimum Geometric Mean Layout (MGML) problem for bounded-degree planar graphs. We also derive an upper bound for any layout of the MGML problem. To the best of our knowledge, these are the first results for the MGML problem with bounded-degree planar graphs.

Plane graphs are often represented within two-dimensional rectangular grids in the plane. In this paper, we consider the problem of minimizing one of its two dimensions for some two-dimensional geometric representations of plane graphs. We first prove that the one dimension tight bound for a rectangular dual of any plane graphs with

n

vertices is

$\frac{n+1}{2}$

. Then we present a linear time algorithm for constructing a rectangular dual for a randomly generated plane graph with

n

vertices, one of its dimensions has the expected value

$\frac{11n}{27}+O(\sqrt{n})$

.

In the second part of our paper, we consider

vertex-face contact representation

(VFCR for short) for 2-connected plane multigraphs [9] and

vertex-vertex contact representation

(VVCR for short) for 2-connected bipartite plane graphs [1,2].

We prove that: (1) Given a 2-connected plane multigraph

G

with

n

vertices and a positive integer

k

, the decision problem on whether

G

admits a VFCR with its height (width, respectively) ≤ 

k

is NP-Complete. (2) Given a 2-connected bipartite plane graph

G

with

n

vertices and a positive integer

k

, the decision problem on whether

G

admits a VVCR with one of its dimensions ≤ 

k

is NP-Complete.

A graph

G

is

k

-

linked

if

G

has at least 2

k

vertices, and for every sequence

x

1

,

x

2

,...,

x

k

,

y

1

,

y

2

,...,

y

k

of distinct vertices,

G

contains

k

pairwise vertex-disjoint paths

P

1

,

P

2

,...,

P

k

such that

P

i

joins

x

i

and

y

i

for

i

 = 1,2,...,

k

. We say that

G

is

modulo

(

m

1

,

m

2

,...,

m

k

)

-linked

if

G

is

k

-linked and, in addition, for any

k

-tuple (

d

1

,

d

2

,...,

d

k

) of natural numbers, the paths

P

1

,

P

2

,...,

P

k

can be chosen such that

P

i

has length

d

i

modulo

m

i

for

i

 = 1,2,...,

k

. Thomassen [15] showed that if each

m

i

is odd and

G

has sufficiently high connectivity then

G

is

modulo

(

m

1

,

m

2

,...,

m

k

)

-linked

. In this paper, we will prove that when

G

is

$(92\sum_{i=1}^k m_i-44k)$

-connected, where

m

i

is a prime or

m

i

 = 1, either

G

is modulo (2

m

1

,2

m

2

,..., 2

m

k

)-linked or

G

has a vertex set

X

of order at most 4

k

 − 3 such that

G

 − 

X

is bipartite.

The pathwidth of a graph

G

is the minimum clique number of

H

minus one, over all interval supergraphs

H

of

G

. We prove in this paper that the

pathwidth

problem is NP-hard for particular subclasses of chordal graphs, and we deduce that the problem remains hard for weighted trees. We also discuss subclasses of chordal graphs for which the problem is polynomial.

This paper investigates the problem of learning classifiers from samples which have additional features and some of these additional features are absent due to noise or corruption of measurement. The common approach for handling missing features in discriminative models is to complete their unknown values with some methods firstly, and then use a standard classification procedure on the completed data. In this paper, an incremental Max-Margin Learning Algorithm is proposed to tackle with data which have additional features and some of these features are missing. We show how to use a max-margin learning framework to classify the incomplete data directly without any completing of the missing features. Based on the geometric interpretation of the margin, we formulate an objective function which aims to maximize the margin of each sample in its own relevant subspace. In this formulation, we make use of the structural parameters trained from existing features and optimize the structural parameters trained from additional features only. A two-step iterative procedure for solving the objective function is proposed. By avoiding the pre-processing phase in which the data is completed, our algorithm could offer considerable computational saving. Moreover, by using structural parameters trained from existing features and training the additional absent features only, our algorithm can save much training time. We demonstrate our results on a large number of standard benchmarks from UCI and the results show that our algorithm can achieve better or comparable classification accuracy.

Distributed denial of service (DDoS) attack is one of the major threats to the current Internet. After analyzing the characteristics of DDoS attacks and the existing Algorithms to detect DDoS attacks, this paper proposes a novel detecting algorithm for DDoS attacks based on IP address features value (IAFV). IAFV is designed to reflect the essential DDoS attacks characteristics, such as the abrupt traffic change, flow dissymmetry, distributed source IP addresses and concentrated target IP addresses. IAFV time series can be used to characterize the essential change features of network flows. Furthermore, a trained support vector machine (SVM) classifier is applied to identify the DDoS attacks. The experimental results on the MIT data set show that our algorithm can detect DDoS attacks accurately and reduce the false alarm rate drastically.

While transductive support vector machine (TSVM) utilizes the information carried by the unlabeled samples for classification and acquires better classification performance than support vector machine (SVM), the number of positive samples must be appointed before training and it is not changed during the training phase. In this paper, a sequential minimal transductive support vector machine (SMTSVM) is discussed to overcome the deficiency in TSVM. It solves the problem of estimation the penalty value after changing a temporary label by introducing the sequential minimal way. The experimental results show that SMTSVM is very promising.

As MMDPs are difficult to represent structural relations among Agents and MAIDs can not model dynamic environment, we present Multi-Agent dynamic influences (MADIDs). MADIDs have stronger knowledge representation ability and MADIDs may efficiently model dynamic environment and structural relations among Agents. Based on the hierarchical decomposition of MADIDs, a junction tree factored particle filter (JFP) algorithm is presented by combing the advantages of the junction trees and particle filter. JFP algorithm converts the distribution of MADIDs into the local factorial form, and the inference is performed by factor particle of propagation on the junction tree. Finally, and the results of algorithm comparison show that the error of JFP algorithm is obviously less than BK algorithm and PF algorithm without the loss of time performance.

Edge Dominating Set problem is an important NP-hard problem. In this paper, we give more detailed structure analysis for the problem, and adopt the enumerate-and-expand technique to construct a fixed-parameter enumeration algorithm. Based on the relationship between Edge Dominating Set and Minimal Vertex Cover, we first find all minimal vertex covers up to 2

k

size for the instance of problem and then expand these vertex covers with matching property and dynamic programming to get the

z

smallest

k

-edge dominating sets. At last, we present an efficient fixed-parameter enumeration algorithm of time complexity

O

(5.6

2

k

k

4

z

2

 + 4

2

k

nk

3

z

) for the Weighted Edge Dominating Set problem, which is the first result for the enumeration of the Weighted Edge Dominating Set problem.

The network lifetime and application requirement are two fundamental, yet conflicting, design objectives in wireless sensor networks for tracking mobile objects. The application requirement is often correlated to the delay time within which the application can send its sensing data back to the users in tracking networks. In this paper we study the network lifetime maximization problem and the delay time minimization problem together. To make both problems tractable, we have the assumption that each sensor node keeps working since it turns on. And we formulate the network lifetime maximization problem as maximizing the number of sensor nodes who don’t turn on, and the delay time minimization problem as minimizing the routing path length, after achieving the required tracking tasks. Since we prove the problems are

NP-complete

and

APX-complete

, we propose three heuristic algorithms to solve them. And we present several experiments to show the advantages and disadvantages referring to the network lifetime and the delay time among these three algorithms on three models, random graphs, grids and hypercubes.

In the paper, we study three related problems, the closest string problem, the farthest string problem and the distinguishing string selection problem. These problems have applications in motif detection, binding sites locating, genetic drug target identification, genetic probes design, universal PCR primer design, etc. They have been extensively studied in recent years.

The problems are defined as follows:

The closest string problem:

given a group of strings

${\cal B}=\{s_1, s_2, \ldots,$

s

n

}, each of length

L

, and an integer

d

, the problem is to compute a center string

s

of length

L

such that the Hamming distance

d

(

s

,

s

i

) ≤ 

d

for all

$s_y\in {\cal B}$

.

The farthest string problem:

given a group of strings

${\cal G}=\{g_1,g_2,...,$

$g_{n_2}\}$

, with all strings of the same length

L

, and an integer

d

b

, the

farthest string

problem is to compute a center string

s

of length

L

such that the Hamming distance

d

(

s

,

g

j

) ≥ 

L

 − 

d

b

for all

$ g_j\in {\cal G}$

.

The distinguishing string selection problem:

given two groups of strings

${\cal B}$

(bad genes) and

${\cal G}$

(good genes),

${\cal B}=\{s_1,s_2,...,s_{n_1}\}$

and

${\cal G}=\{g_{n_1+1},g_{n_1+2},...,g_{n_2}\}$

, with all strings of the same length

L

, and two integers

d

b

and

d

g

with

d

g

 ≥ 

L

 − 

d

b

, the Distinguishing String Selection problem is to compute a center string

s

of length

L

such that the Hamming distance

$d(s,s_i)\leq d_b, \forall s_i\in{\cal B}$

and the Hamming distance

d

(

s

,

g

j

) ≥ 

d

g

for all

$g_j\in {\cal G}$

.

Our results:

We design an

O

(

Ln

 + 

nd

(|

Σ

 − 1|)

d

2

3.25

d

) time fixed parameter algorithm for the closest string problem which improves upon the best known

O

(

Ln

 + 

nd

2

4

d

×(|

Σ

| − 1)

d

) algorithm in [14], where |

Σ

| is the size of the alphabet. We also design fixed parameter algorithms for both the farthest string problem and the distinguishing string selection problem. Both algorithms run in time

$O(Ln+nd2^{3.25d_b})$

when the input strings are binary strings over

Σ

 = {0, 1}.

Finding optimal path through a graph efficiently is central to many problems, including route planning for a mobile robot. BDD-based incremental heuristic search method uses heuristics to focus their search and reuses BDD-based information from previous searches to find solutions to series of similar search problems much faster than solving each search problem from scratch. In this paper, we apply BDD-based incremental heuristic search to robot navigation in unknown terrain, including goal-directed navigation in unknown terrain and mapping of unknown terrain. The resulting BDD-based dynamic A* (BDDD*) algorithm is capable of planning paths in unknown, partially known and changing environments in an efficient, optimal, and complete manner. We present properties about BDDD* and demonstrate experimentally the advantages of combining BDD-based incremental and heuristic search for the applications studied. We believe that our experimental results will make BDD-based D* like replanning algorithms more popular and enable robotics researchers to adapt them to additional applications.

In the Scheduling Machines with Capacity Constraints problem, we are given

k

identical machines, each of which can process at most

m

i

jobs.

$M \leq \sum_{i = 1}^{k}{m_i}$

jobs are also given, job

j

has a non-negative processing time length

t

j

 ≥ 0. The task is to find a schedule such that the makespan is minimized and the capacity constraints are met. In this paper, we present a 3-approximation algorithm using an extension of

Iterative Rounding Method

introduced by Jain [4]. To the best of the authors’ knowledge, this is the first attempt to apply

Iterative Rounding Method

to scheduling problem with capacity constraints.

As a generalization of the spanning star forest problem, the spanning

k

-tree forest problem is to find a maximum-edge-weight spanning forest in which each tree has a central node and other nodes in the tree are at most

k

-distance away from the central node. In this paper, we show that it can be approximated with ratio

$\frac{k}{k+1}$

in polynomial time for both undirected and directed graphs. In the weighted distance model, a 0.5-approximation algorithm is presented.

The greedy approach is widely used for combinatorial optimization problems, but its implementation varies from problem to problem. In this paper we propose a mechanical approach for implementing greedy algorithmic programs. Using PAR method, a problem can be continually partitioned into subproblems in smaller size based on the problem singleton and the maximum selector, and the greedy algorithm can be mechanically generated by combining the problem-solving sequences. Our structural model supports logical transformation from specifications to algorithmic programs by deductive inference, and thus significantly promotes the automation and reusability of algorithm design.

Admission control is the problem of deciding for a given set of requests which of them to accept and which to reject, with the goal of maximizing the profit obtained from the accepted requests. The problem is considered in a scenario with advance reservations where multiple resources exist and users can specify several resource request alternatives. Each alternative is associated with a resource capacity requirement for a time interval on one of the multiple resources and a utility. We give a novel (1 + 

α

)-approximation admission control algorithm with respect to the maximal utility and derive the approximation ratio for different request scenarios. We also design non-guaranteed greedy heuristics. We compare the performance of our approximation algorithm and greedy heuristics in aspect of utility optimality and timing in finding solutions. Simulation results show that on average our approximation algorithm appears to offer the best trade-off between quality of solution and computation cost. And our (1 + 

α

)-approximation algorithm shows its intrinsic stability in performance for different utility functions.

DAWG is a key data structure for string matching and it is widely used in bioinformatics and data compression. But DAWGs are memory greedy. Weighted directed word graph (WDWG) is a space-economical variation of DAWG which is as powerful as DAWG. The underlay concept of WDWGs is a new equivalent relation of the substrings of a word, namely the minimal consistent linear partition. However, the structure of the consistent linear partition is not extensively explored. In this paper, we present a theorem that gives insight into the structure of consistent partitions. Through this theorem, one can enumerate all the consistent linear partitions and verify whether a linear partition is consistent. It also demonstrates how to merge the DAWG into a consistent partition. In the end, we give a simple and easy-to-construct class of consistent partitions based on lexicographic order.

This paper concentrates on the problem of finding all the occurrences of a pattern in a text. A novel bit-parallel exact string matching algorithm for small alphabet (SABP) is proposed based on a position related character matching table, which is deduced according to the matching matrix of the pattern and the text. A 2-base logarithm table consisting of 2

16

items is employed to locate the leftmost “1” bit of an unsigned integer flag, which indicates a latest probable occurrence of the pattern in the text. Safe shifts are obtained through combining the 2-base logarithm table value of current flag and the bad character shift which is adopted in Boyer-Moore algorithm. Our algorithm suits to the situation that the pattern length is more than the word size of a computer. Experimental results on random generated texts show that it is the fastest in many cases, particularly, on long patterns with a small alphabet.

Database classification is a data preprocessing technique for multi-database mining. To reduce search costs in the data from all databases, we need to identify those databases which are most likely relevant to a data mining application. Based on the related research, the algorithm

GreedyClass

and

BestClassification

[7]are improved in order to optimize the time complexity of algorithm and to obtainthe best classification from

m

given databases. Theoretical analysis and experimental results show the efficiency of the proposed algorithm.

There have existed several “card-based protocols” for secure computations of a Boolean function such as AND and XOR. The best result currently known is that AND and XOR can be securely computed using 8 cards and 10 cards, respectively. In this paper, we improve the result: we design a 6-card AND protocol and a 4-card XOR protocol. Thus, this paper succeeds in reducing the number of required cards for secure computations.