Improved complexity results for several multifacility location problems on trees

In this paper we consider multifacility location problems on tree networks. On general networks, these problems are usually NP-hard. On tree networks, however, often polynomial time algorithms exist; e.g., for the median, center, centdian, or special cases of the ordered median problem. We present an enhanced dynamic programming approach for the ordered median problem that has a time complexity of just O(ps ² n ⁶) for the absolute and O(ps ² n ²) for the node restricted problem, improving on the previous results by a factor of O(n ³). (n and p being the number of nodes and new facilities, respectively, and s (≤n) a value specific for the ordered median problem.) The same reduction in complexity is achieved for the multifacility k-centrum problem leading to O(pk ² n ⁴) (absolute) and O(pk ² n ²) (node restricted) algorithms.     

Rank-two update algorithms for the minimum volume enclosing ellipsoid problem

We consider the problem of computing a (1+ε)-approximation to the minimum volume enclosing ellipsoid (MVEE) of a given set of m points in R ⁿ . Based on the idea of sequential minimal optimization (SMO) method, we develop a rank-two update algorithm. This algorithm computes an approximate solution to the dual optimization formulation of the MVEE problem, which updates only two weights of the dual variable at each iteration. We establish that this algorithm computes a (1+ε)-approximation to MVEE in O(mn ³/ε) operations and returns a core set of size O(n ²/ε) for ε∈(0,1). In addition, we give an extension of this rank-two update algorithm. Computational experiments show the proposed algorithms are very efficient for solving large-scale problem with a high accuracy.     

A trust region method for solving the decentralized static output feedback design problem

The shortest-paths problem is a fundamental problem in graph theory and finds diverse applications in various fields. This is why shortest path algorithms have been designed more thoroughly than any other algorithm in graph theory. A large number of optimization problems are mathematically equivalent to the problem of finding shortest paths in a graph. The shortest-path between a pair of vertices is defined as the path with shortest length between the pair of vertices. The shortest path from one vertex to another often gives the best way to route a message between the vertices. This paper presents anO(n ²) time sequential algorithm and anO(n ²/p+logn) time parallel algorithm on EREW PRAM model for solving all pairs shortest paths problem on circular-arc graphs, wherep andn represent respectively the number of processors and the number of vertices of the circular-arc graph.     

Polynomial algorithms for a class of minimum rank-two cost path problems

In this paper, we develop two algorithms for finding a directed path of minimum rank-two monotonic cost between two specified nodes in a network with n nodes and m arcs. Under the condition that one of the vectors characterizing the cost function f is binary, one yields an optimal solution in O(n³) or O(nm log n) time if f is quasiconcave; the other solves any problem in O(nm + n ² log n) time.     

Incremental algorithms for minimal length paths

We consider the problem of maintaining on-line a solution to the All Pairs Shortest Paths Problem in a directed graph G = (V,E) where edges may be dynamically inserted or have their cost decreased. For the case of integer edge costs in a given range [1…C], we introduce a new data structure which is able to answer queries concerning the length of the shortest path between any two vertices in constant time and to trace out the shortest path between any two vertices in time linear in the number of edges reported. The total time required to maintain the data structure under a sequence of at most O(n²) edge insertions and at most O(Cn²) edge cost decreases is O(Cn³ log(nC)) in the worst case, where n is the total number of vertices in G. For the case of unit edge costs, the total time required to maintain the data structure under a sequence of at most O(n²) insertions of edges becomes O(n³ logn) in the worst case. The same bounds can be achieved for the problem of maintaining on-line longest paths in directed acyclic graphs. All our algorithms improve previously known algorithms and are only a logarithmic factor away from the best possible bounds.     

An algorithm for outerplanar graphs with parameter

For n-vertex outerplanar graphs, it is proven that O(n^2.87) is an upper bound on the number of breakpoints of the function which gives the maximum weight of an independent set, where the vertex weights vary as linear functions of a parameter. An O(n^2.87) algorithm for finding the solution is proposed.     

Parallel algorithms for permutation graphs

In this paper, parallel algorithms are presented for solving some problems on permutation graphs. The coloring problem is solved inO(log² n) time usingO(n ³/logn) processors on the CREW PRAM, orO(logn) time usingO(n ³) processors on the CRCW PRAM. The weighted clique problem, the weighted independent set problem, the cliques cover problem, and the maximal layers problem are all solved with the same complexities. We can also show that the longest common subsequence problem belongs to the class NC.     

Scheduling jobs with release times preemptively on a single machine to minimize the number of late jobs

We give a direct combinatorial O(n³logn) algorithm for minimizing the number of late jobs on a single machine when jobs have release times and preemptions are allowed. Our algorithm improves the earlier O(n⁵) and O(n⁴) dynamic programming algorithms for this problem.     

The location of median paths on grid graphs

In this paper we consider the location of a path shaped facility on a grid graph. In the literature this problem was extensively studied on particular classes of graphs as trees or series-parallel graphs. We consider here the problem of finding a path which minimizes the sum of the (shortest) distances from it to the other vertices of the grid, where the path is also subject to an additional constraint that takes the form either of the length of the path or of the cardinality. We study the complexity of these problems and we find two polynomial time algorithms for two special cases, with time complexity of O(n) and O(nℓ) respectively, where n is the number of vertices of the grid and ℓ is the cardinality of the path to be located. The literature about locating dimensional facilities distinguishes between the location of extensive facilities in continuous spaces and network facility location. We will show that the problems presented here have a close connection with continuous dimensional facility problems, so that the procedures provided can also be useful for solving some open problems of dimensional facilities location in the continuous case.     

Optimally Computing the Shortest Weakly Visible Subedge of a Simple Polygon

Given ann-vertex simple polygonP, the problem of computing the shortest weakly visible subedge ofPis that of finding a shortest line segmentson the boundary ofPsuch thatPis weakly visible froms(ifsexists). In this paper, we present new geometric observations that are useful for solving this problem. Based on these geometric observations, we obtain optimal sequential and parallel algorithms for solving this problem. Our sequential algorithm runs inO(n) time, and our parallel algorithm runs inO(log n) time usingO(n/log n) processors in the CREW PRAM computational model. Using the previously best known sequential algorithms to solve this problem would takeO(n²) time. We also give geometric observations that lead to extremely simple and optimal algorithms for solving, both sequentially and in parallel, the case of this problem where the polygons are rectilinear.     

Streaming Algorithms for Line Simplification

We study the following variant of the well-known line-simplification problem: we are getting a (possibly infinite) sequence of points p ₀,p ₁,p ₂,… in the plane defining a polygonal path, and as we receive the points, we wish to maintain a simplification of the path seen so far. We study this problem in a streaming setting, where we only have a limited amount of storage, so that we cannot store all the points. We analyze the competitive ratio of our algorithms, allowing resource augmentation: we let our algorithm maintain a simplification with 2k (internal) points and compare the error of our simplification to the error of the optimal simplification with k points. We obtain the algorithms with O(1) competitive ratio for three cases: convex paths, where the error is measured using the Hausdorff distance (or Fréchet distance), xy-monotone paths, where the error is measured using the Hausdorff distance (or Fréchet distance), and general paths, where the error is measured using the Fréchet distance. In the first case the algorithm needs O(k) additional storage, and in the latter two cases the algorithm needs O(k ²) additional storage.     

Efficient parallel algorithms for shortest paths in planar digraphs

Efficient parallel algorithms are presented, on the CREW PRAM model, for generating a succinct encoding of all pairs shortest path information in a directed planar graphG with real-valued edge costs but no negative cycles. We assume that a planar embedding ofG is given, together with a set ofq faces that cover all the vertices. Then our algorithm runs inO(log² n) time and employsO(nq+M(q)) processors (whereM(t) is the number of processors required to multiply twot×t matrices inO(logt) time). Let us note here that wheneverq<n then our processor bound is better than the best previous one (M(n)).O(log² n) time,n-processor algorithms are presented for various subproblems, including that of generating all pairs shortest path information in a directedouterplanar graph. Our work is based on the fundamental hammock-decomposition technique of G. Frederickson. We achieve this decomposition inO(logn log*n) parallel time by usingO(n) processors. The hammock-decomposition seems to be a fundamental operation that may help in improving efficiency of many parallel (and sequential) graph algorithms.This work was partially supported by the EEC ESPRIT Basic Research Action No. 3075 (ALCOM) and by the Ministry of Industry, Energy and Technology of Greece.     

Graph algorithms on a tree-structured parallel computer

Parallel algorithms for some graph-theoretic problems on a tree-structured computer are presented. In particular, ifp denotes the number of processing elements, algorithms that run inO(n ²/p) time for finding connected components, transitive closure and the minimum spanning tree of an undirected graph withn vertices are obtained.     

A parallel search algorithm for directed acyclic graphs

A parallel algorithm for depth-first searching of a directed acyclic graph (DAG) on a shared memory model of a SIMD computer is proposed. The algorithm uses two parallel tree traversal algorithms, one for the preorder traversal and the other for therpostorder traversal of an ordered tree. Each of these traversal algorithms has a time complexity ofO(logn) whenO(n) processors are used,n being the number of vertices in the tree. The parallel depth-first search algorithm for a directed acyclic graphG withn vertices has a time complexity ofO((logn)²) whenO(n ^2.81/logn) processors are used.     

Parallel algorithms for analyzing activity networks

Parallel algorithms for analyzing activity networks are proposed which include feasibility test, topological ordering of the events, and computing the earliest and latest start times for all activities and hence identification of the critical activities of the activity network. The first two algorithms haveO(logn) time complexity and the remaining one achievesO(logd log logn) time bound, whered is the diameter of the digraph representing the activity network withn nodes. All these algorithms work on a CRCW PRAM and requireO(n ³) processors.     

Long time error analysis of the fourth‐order compact finite difference methods for the nonlinear Klein–Gordon equation with weak nonlinearity

We present the fourth‐order compact finite difference (4cFD) discretizations for the long time dynamics of the nonlinear Klein–Gordon equation (NKGE), while the nonlinearity strength is characterized by ?^p with a constant p ∈ ?⁺ and a dimensionless parameter ? ∈ (0, 1] . Based on analytical results of the life‐span of the solution, rigorous error bounds of the 4cFD methods are carried out up to the time at O(?^?p) . We pay particular attention to how error bounds depend explicitly on the mesh size h and time step τ as well as the small parameter ? ∈ (0, 1] , which indicate that, in order to obtain ‘correct’ numerical solutions up to the time at O(?^?p) , the ? ‐scalability (or meshing strategy requirement) of the 4cFD methods should be taken as: h = O(?^p/4) and τ = O(?^p/2) . It has better spatial resolution capacity than the classical second order central difference methods. By a rescaling in time, it is equivalent to an oscillatory NKGE whose solution propagates waves with wavelength at O(1) in space and O(?^p) in time. It is straightforward to get the error bounds of the oscillatory NKGE in the fixed time. Finally, numerical results are provided to confirm our theoretical analysis.     

On the evaluation of the Eigenvalues of a banded toeplitz block matrix

Let A = (a_ij) be an n × n Toeplitz matrix with bandwidth k + 1, K = r + s, that is, a_ij = a_j−i, i, J = 1,… ,n, a_i = 0 if i > s and if i < -r. We compute p(λ)= det(A - λI), as well as p(λ)/p′(λ), where p′(λ) is the first derivative of p(λ), by using O(k log k log n) arithmetic operations. Moreover, if a_i are m × m matrices, so that A is a banded Toeplitz block matrix, then we compute p(λ), as well as p(λ)/p′(λ), by using O(m³k(log² k + log n) + m²k log k log n) arithmetic operations. The algorithms can be extended to the computation of det(A − λB) and of its first derivative, where both A and B are banded Toeplitz matrices. The algorithms may be used as a basis for iterative solution of the eigenvalue problem for the matrix A and of the generalized eigenvalue problem for A and B.     

Numerical solution of Volterra integral and integro-differential equations with rapidly vanishing convolution kernels

Variable stepsize algorithms for the numerical solution of nonlinear Volterra integral and integro-differential equations of convolution type are described. These algorithms are based on an embedded pair of Runge–Kutta methods of order p=5 and p=4 proposed by Dormand and Prince with interpolation of uniform order p=4. They require O(N) number of kernel evaluations, where N is the number of steps. The cost of the algorithms can be further reduced for equations that have rapidly vanishing convolution kernels, by using waveform relaxation iterations after computing the numerical approximation by variable stepsize algorithm on some initial interval. AMS subject classification (2000)  65R20, 45L10, 93C22     

Optimal parallel quicksort on EREW PRAM

In this paper, we present parallel quicksort algorithms running inO((n/p+logp) logn) expected time andO((n/p+logp+log logn) logn) deterministic time respectively, and both withO(n) space by usingp processors on EREW PRAM. Whenp=O(n/logn), the cost is optimal, in terms of the product of time and number of processors. These algorithms can be used to obtain parallel algorithms for constructing balanced binary search trees without using sorting algorithms. One of our quicksort algorithms leads to a parallel quickhull algorithm on EREW PRAM.The work of this author was partially supported by a fellowship from the College of Science, Old Dominion University, Norfolk, VA 23529, USA.     

Fly Cheaply: On the Minimum Fuel Consumption Problem

In planning a flight, stops at intermediate airports are sometimes necessary to minimize fuel consumption, even if a direct flight is available. We investigate the problem of finding the cheapest path from one airport to another, given a set of n airports in ² and a function l: ² × ² → ⁺ representing the cost of a direct flight between any pair. Given a source airport s, the cheapest-path map is a subdivision of ² where two points lie in the same region iff their cheapest paths from s use the same sequence of intermediate airports. We show a quadratic lower bound on the combinatorial complexity of this map for a class of cost functions. Nevertheless, we are able to obtain subquadratic algorithms to find the cheapest path from s to all other airports for any well-behaved cost function l: our general algorithm runs in O(n^{4/3 +} ) time, and a simpler, more practical variant runs in O(n^{3/2 +} ) time, while a special class of cost functions requires just O(n log n) time.