Parallel batch scheduling of equal-length jobs with release and due dates

In this paper we study parallel batch scheduling problems with bounded batch capacity and equal-length jobs in a single and parallel machine environment. It is shown that the feasibility problem 1|p-batch,b<n,r _j ,p _j =p,C _j ≤d _j |− can be solved in O(n ²) time and that the problem of minimizing the maximum lateness can be solved in O(n ²log n) time. For the parallel machine problem P|p-batch,b<n,r _j ,p _j =p,C _j ≤d _j |− an O(n ³log n)-time algorithm is provided, which can also be used to solve the problem of minimizing the maximum lateness in O(n ³log ² n) time.     

Scheduling on Unrelated Machines under Tree-Like Precedence Constraints

We present polylogarithmic approximations for the R|prec|C _max and R|prec|∑ _j w _j C _j problems, when the precedence constraints are “treelike”—i.e., when the undirected graph underlying the precedences is a forest. These are the first non-trivial generalizations of the job shop scheduling problem to scheduling with precedence constraints that are not just chains. These are also the first non-trivial results for the weighted completion time objective on unrelated machines with precedence constraints of any kind. We obtain improved bounds for the weighted completion time and flow time for the case of chains with restricted assignment—this generalizes the job shop problem to these objective functions. We use the same lower bound of “congestion + dilation”, as in other job shop scheduling approaches (e.g. Shmoys, Stein and Wein, SIAM J. Comput. 23, 617–632, 1994). The first step in our algorithm for the R|prec|C _max problem with treelike precedences involves using the algorithm of Lenstra, Shmoys and Tardos to obtain a processor assignment with the congestion + dilation value within a constant factor of the optimal. We then show how to generalize the random-delays technique of Leighton, Maggs and Rao to the case of trees. For the special case of chains, we show a dependent rounding technique which leads to a bicriteria approximation algorithm for minimizing the flow time, a notoriously hard objective function. A preliminary version of this paper appeared in the Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 146–157, 2005. V.S. Anil Kumar supported in part by NSF Award CNS-0626964. Part of this work was done while at the Los Alamos National Laboratory, and supported in part by the Department of Energy under Contract W-7405-ENG-36. M.V. Marathe supported in part by NSF Award CNS-0626964. Part of this work was done while at the Los Alamos National Laboratory, and supported in part by the Department of Energy under Contract W-7405-ENG-36. Part of this work by S. Parthasarathy was done while at the Department of Computer Science, University of Maryland, College Park, MD 20742, and in part while visiting the Los Alamos National Laboratory. Research supported in part by NSF Award CCR-0208005 and NSF ITR Award CNS-0426683. Research of A. Srinivasan supported in part by NSF Award CCR-0208005, NSF ITR Award CNS-0426683, and NSF Award CNS-0626636.     

Deterministic Broadcast and Gossiping Algorithms for Ad hoc Networks

We present in this paper three deterministic broadcast and a gossiping algorithm suitable for ad hoc networks where topology changes range from infrequent to very frequent. The proposed algorithms are designed to work in networks where the mobile nodes possessing collision detection capabilities. Our first broadcast algorithm accomplishes broadcast in O(nlog n) for networks where topology changes are infrequent. We also present an O(nlog n) worst case time broadcast algorithms that is resilient to mobility. For networks where topology changes are frequent, we present a third algorithm that accomplishes broadcast in O(Δ·nlog n + n·|M|) in the worst case scenario, where |M| is the length of the message to be broadcasted and Δ the maximum node degree. We then extend one of our broadcast algorithms to develop an O(Dn log n + D²) algorithm for gossiping in the same network model.     

A Neural Algorithm for the Maximum Clique Problem: Analysis,Experiments, and Circuit Implementation

{In this paper we design and analyze a neural approximation algorithm for the Maximum Clique problem. This algorithm, having as input an arbitrary undirected graph G = \langle V, E\rangle , constructs a finite sequence of Hopfield networks such that the attractor of the last network in the sequence represents a maximal clique of G . We prove that D(G) ⋅ |E ^{\rm c} | , where D(G) = max _{{i,j}\notin E} \min{d _i , d _j } , d _i is the degree of the vertex i of G , and |E ^{\rm c} | denotes the cardinality of the set of edges in the complement graph, is an upper bound to the number of the networks in the sequence. Some experiments made on the second DIMACS benchmark and on random graphs show that: 1. The quality of the solutions found by the algorithm is satisfactory. 2. The theoretical upper bound D(G) ⋅ |E ^{\rm c} | is quite pessimistic. For random graphs we propose an empirical formula that gives a better estimate of the number of networks in the sequence. Moreover, thanks to the simplicity of the algorithm, we are able to design a uniform family of circuits of small size (\approx 10n ² log ₂ n ) that implements it. The circuit, which solves the problems for graphs of at most 32 vertices, has then been programmed on FPGAs (Field Programmable Gate Arrays). An analysis in terms of size and time complexity is given. Received November 10, 1998; revised December 2000.     

Output-Sensitive Algorithm for Computing β-Skeletons

The β-skeleton is a measure of the internal shape of a planar set of points. We get an entire spectrum of shapes by varying the parameter β. For a fixed value of β, a β-skeleton is a geometric graph obtained by joining each pair of points whose β-neighborhood is empty. For β≥1, this neighborhood of a pair of points p _i ,p _j is the interior of the intersection of two circles of radius , centered at the points (1−β/2)p _i +(β/2)p _j and (β/2)p _i +(1−β/2)p _j , respectively. For β∈(0,1], it is the interior of the intersection of two circles of radius , passing through p _i and p _j . In this paper we present an output-sensitive algorithm for computing a β-skeleton in the metrics l ₁ and l _∞ for any β≥2. This algorithm is in O(nlogn+k), where k is size of the output graph. The complexity of the previous best known algorithm is in O(n ^5/2logn) [7]. Received April 26, 2000     

Improved Algorithms for Uniform Partitions of Points

Abstract. We consider the following one- and two-dimensional bucketing problems: Given a set S of n points in \reals ¹ or \reals ² and a positive integer b , distribute the points of S into b equal-size buckets so that the maximum number of points in a bucket is minimized. Suppose at most (n/b) + Δ points lie in each bucket in an optimal solution. We present algorithms whose time complexities depend on b and Δ . No prior knowledge of Δ is necessary for our algorithms. For the one-dimensional problem, we give a deterministic algorithm that achieves a running time of O(b ⁴ (Δ ² +log n) + n) . For the two-dimensional problem, we present a Monte Carlo algorithm that runs in subquadratic time for small values of b and Δ . The previous algorithms, by Asano and Tokuyama [1], searched the entire parameterized space and required Ω ( n ² ) time in the worst case even for constant values of b and Δ . We also present a subquadratic algorithm for the special case of the two-dimensional problem when b=2 .     

Approximation Algorithms for Connected Dominating Sets

The dominating set problem in graphs asks for a minimum size subset of vertices with the following property: each vertex is required to be either in the dominating set, or adjacent to some vertex in the dominating set. We focus on the related question of finding a connected dominating set of minimum size, where the graph induced by vertices in the dominating set is required to be connected as well. This problem arises in network testing, as well as in wireless communication. Two polynomial time algorithms that achieve approximation factors of 2H(Δ)+2 and H(Δ)+2 are presented, where Δ is the maximum degree and H is the harmonic function. This question also arises in relation to the traveling tourist problem, where one is looking for the shortest tour such that each vertex is either visited or has at least one of its neighbors visited. We also consider a generalization of the problem to the weighted case, and give an algorithm with an approximation factor of (c _n +1) \ln n where c _n ln k is the approximation factor for the node weighted Steiner tree problem (currently c _n = 1.6103 ). We also consider the more general problem of finding a connected dominating set of a specified subset of vertices and provide a polynomial time algorithm with a (c+1) H(Δ) +c-1 approximation factor, where c is the Steiner approximation ratio for graphs (currently c = 1.644 ). Received June 22, 1996; revised February 28, 1997.     

Minimizing total weighted tardiness on a single machine with release dates and equal-length jobs

In this paper we study the problem of scheduling n jobs with release dates, due dates, weights, and equal processing times on a single machine. The objective is to minimize total weighted tardiness. We formulate the problem as a time-indexed ILP after which we solve the LP-relaxation. We show that for certain special cases (namely when either all due dates, all weights, or all release dates are equal, or when all due dates and release dates are equally ordered), the solution for the LP-relaxation is either integral or can be adjusted in polynomial time into an integral one. For the general case we present a branching rule that performs well. Furthermore we show that the same approach holds for the m identical, parallel machines variant of the problem. Finally we show that with a minor modification the same approach also holds for the single-machine problems of minimizing the sum of weighted late jobs (1|r _j ,p _j =p|∑w _j U _j ) and the sum of weighted late work (1|r _j ,p _j =p|∑w _j V _j ) as well as their respective variants with m identical, parallel machines. We further show how we can solve these problems by applying column generation when there is not sufficient memory available to apply the direct ILP-approach.     

A special case of the single-machine total tardiness problem is NP-hard

In this paper, it is shown that the special case B-1 of the single-machine total tardiness problem 1 ∥ ΣT _j is NP-hard in the ordinary sense. For this case, there exists a pseudo-polynomial algorithm with run time O(n σp _j). Published in Russian in Izvestiya Akademii Nauk. Teoriya i Sistemy Upravleniya, 2006, No. 3, pp. 120–128. Article was translated by the authors.     

When Does Eddy Viscosity Damp Subfilter Scales Sufficiently?

Large eddy simulation (LES) seeks to predict the dynamics of spatially filtered turbulent flows. The very essence is that the LES-solution contains only scales of size ≥Δ, where Δ denotes some user-chosen length scale. This property enables us to perform a LES when it is not feasible to compute the full, turbulent solution of the Navier-Stokes equations. Therefore, in case the large eddy simulation is based on an eddy viscosity model we determine the eddy viscosity such that any scales of size <Δ are dynamically insignificant. In this paper, we address the following two questions: how much eddy diffusion is needed to (a) balance the production of scales of size smaller than Δ; and (b) damp any disturbances having a scale of size smaller than Δ initially. From this we deduce that the eddy viscosity ν _e has to depend on the invariants q = \frac12tr(S²)q = \frac{1}{2}\mathrm{tr}(S^{2}) and r = -\frac13tr(S³)r= -\frac{1}{3}\mathrm{tr}(S^{3}) of the (filtered) strain rate tensor S. The simplest model is then given by n_e = \frac32(D/p)² |r|/q\nu_{e} = \frac{3}{2}(\Delta/\pi)^{2} |r|/q. This model is successfully tested for a turbulent channel flow (Re  _τ =590).     

Online Dynamic Programming Speedups

Consider the dynamic program h(n)=min _1≤j≤n a(n,j), where a(n,j) is some formula that may (online) or may not (offline) depend on the previously computed h(i), for i<n. The goal is to compute all h(n), for 1≤n≤N. It is well known that, if a(n,j) satisfy the Monge property, then the SMAWK algorithm (Aggarwal et al., Algorithmica 2(1):195–208, 1987) can solve the offline problem in O(N) time; a Θ(N) speedup over the naive algorithm. In this paper we extend this speedup to the online case, that is, to compute h(n) in the order n=1,2,…,N when (i) we do not know the values of a(n′,j) for n′>n before h(n) has been computed and (ii) do not know the problem size N in advance. We show that if a(n,j) satisfy a stronger, but sometimes still natural, property than the Monge one, then each h(n) can be computed in online fashion in O(1) amortized time. This maintains the speedup online, in the sense that the total time to compute all h(n) is O(N). We also show how to compute each h(n) in the worst case O(log N) time, while maintaining the amortized time bound. For a(n,j) satisfying our stronger property, our algorithm is also simpler than the standard SMAWK algorithm for solving the offline case. We illustrate our technique on two examples from the literature; the first is the D-median problem on a line, and the second comes from mobile wireless paging. The research of the first author was partially supported by the NSF program award CNS-0626606; the research of the second and third authors was partially supported by Hong Kong RGC CERG grant HKUST6312/04E.     

Erratum: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems

Abstract. There is an error in our paper ``An Approximation Algorithm for Minimum-Cost Vertex- Connectivity Problems' (Algorithmica (1997), 18:21—43). In that paper we considered the following problem: given an undirected graph and values r _ij for each pair of vertices i and j , find a minimum-cost set of edges such that there are r _ij vertex-disjoint paths between vertices i and j . We gave approximation algorithms for two special cases of this problem. Our algorithms rely on a primal—dual approach which has led to approximation algorithms for many edge-connectivity problems. The algorithms work in a series of stages; in each stage an augmentation subroutine augments the connectivity of the current solution. The error is in a lemma for the proof of the performance guarantee of the augmentation subroutine. In the case r _ij = k for all i,j , we described a polynomial-time algorithm that claimed to output a solution of cost no more than 2 H (k) times optimal, where H = 1 + 1/2 + · · · + 1/n . This result is erroneous. We describe an example where our primal—dual augmentation subroutine, when augmenting a k -vertex connected graph to a (k+1) -vertex connected graph, gives solutions that are a factor Ω(k) away from the minimum. In the case r _ij ∈ {0,1,2} for all i,j , we gave a polynomial-time algorithm which outputs a solution of cost no more than three times the optimal. In this case we prove that the statement in the lemma that was erroneous for the k -vertex connected case does hold, and that the algorithm performs as claimed.     

Resource scheduling with variable requirements over time

The problem of scheduling resources for tasks with variable requirements over time can be stated as follows. We are given two sequences of vectors A=A ₁,…,A _n and R=R ₁,…,R _m . Sequence A represents resource availability during n time intervals, where each vector A _i has q elements. Sequence R represents resource requirements of a task during m intervals, where each vector R _i has q elements. We wish to find the earliest time interval i, termed latency, such that for 1≤k≤m, 1≤j≤q: A _i+k−1 ^j ≥R _k ^j , where A _i+k−1 ^j and R _k ^j are the jth elements of vectors A _i+k−1 and R _k , respectively. One application of this problem is I/O scheduling for multimedia presentations. The fastest known algorithm to compute the optimal solution of this problem has computation time (Amir and Farach, in Proceedings of the ACM-SIAM symposium on discrete algorithms (SODA), San Francisco, CA, pp. 212–223, 1991; Inf. Comput. 118(1):1–11, 1995). We propose a technique that approximates the optimal solution in linear time: . We evaluated the performance of our algorithm when used for multimedia I/O scheduling. Our results show that 95% of the time, our solution is within 5% of the optimal.     

Solving Some Discrepancy Problems in NC

We show that several discrepancy-like problems can be solved in NC nearly achieving the discrepancies guaranteed by a probabilistic analysis and achievable sequentially. For example, we describe an NC algorithm that given a set system (X, S) , where X is a ground set and S⊆2 ^X , computes a set R⊆X so that for each S∈ S the discrepancy ||R S|-|R^-∩S|| is . Whereas previous NC algorithms could only achieve discrepancies with ɛ>0 , ours matches the probabilistic bound within a multiplicative factor 1+o(1) . Other problems whose NC solution we improve are lattice approximation, ɛ -approximations of range spaces with constant VC-exponent, sampling in geometric configuration spaces, approximation of integer linear programs, and edge coloring of graphs. Received June 26, 1998; revised February 18, 1999.     

A Property Tester for Tree-Likeness of Quartet Topologies

Property testing is a rapid growing field in theoretical computer science. It considers the following task: given a function f over a domain D, a property ℘ and a parameter 0<ε<1, by examining function values of f over o(|D|) elements in D, determine whether f satisfies ℘ or differs from any one which satisfies ℘ in at least ε|D| elements. An algorithm that fulfills this task is called a property tester. We focus on tree-likeness of quartet topologies, which is a combinatorial property originating from evolutionary tree construction. The input function is f _Q , which assigns one of the three possible topologies for every quartet over an n-taxon set S. We say that f _Q satisfies tree-likeness if there exists an evolutionary tree T whose induced quartet topologies coincide with f _Q . In this paper, we prove the existence of a set of quartet topologies of error number at least c((n) || 4)c{n\choose 4} for some constant c>0, and present the first property tester for tree-likeness of quartet topologies. Our property tester makes at most O(n ³/ε) queries, and is of one-sided error and non-adaptive.     

Fault-Tolerant Real-Time Scheduling

We use competitive analysis to study how best to use redundancy to achieve fault-tolerance in online real-time scheduling. We show that the optimal way to use spatial redundancy depends on a complex interaction of the benefits, execution times, release times, and latest start times of the jobs. We give a randomized online algorithm whose competitive ratio is O( logΦ log Delta ( log ² n log m/ log log m)) for transient faults. Here n is the number of jobs, m is the number of processors, Φ is the ratio of the maximum value density of a job to the minimum value density of a job, and Δ is the ratio of the longest possible execution time to the shortest possible execution time. We show that this bound is close to optimal by giving an Ω(( log ΔΦ/ log log m) ( log m log log m) ² ) lower bound on the competitive ratio of any randomized algorithm. In the case of permanent faults, there is a randomized online algorithm that has a competitive ratio of O( log Phi log Δ (log m/log log m)). We also show a lower bound of Ω((log ΔΦ/ log log m) ( log m/log log m)) on the competitive ratio for interval scheduling with permanent faults. Received October 1997; revised January 1999.     

On Metric Clustering to Minimize the Sum of Radii

Given an n-point metric (P,d) and an integer k>0, we consider the problem of covering P by k balls so as to minimize the sum of the radii of the balls. We present a randomized algorithm that runs in n ^{O(log n⋅log Δ)} time and returns with high probability the optimal solution. Here, Δ is the ratio between the maximum and minimum interpoint distances in the metric space. We also show that the problem is NP-hard, even in metrics induced by weighted planar graphs and in metrics of constant doubling dimension.     

Fast algorithms for minimum matrix norm with application in computer graphics

In this paper we consider the following problem. Given (r ₁,r ₂, ...,r _n) R ⁿ, for anyI= (I ₁,I ₂,...,I _n) Z ⁿ, letE ₁=(e _ij), wheree _ij=(r _i–r_j)–(I _i–I_j), findI Z ⁿ such that |E _I| is minimized, where |·| is a matrix norm. This problem arises from optimal curve rasterization in computer graphics, where minimum distortion of curve dynamic context is sought. Until now, there has been no polynomial-time solution to this computer graphics problem. We present a very simpleO(n lgn)-time algorithm to solve this problem under various matrix norms.This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant OGP0046373.     

Newton Iterative Parallel Finite Element Algorithm for the Steady Navier-Stokes Equations

A combination method of the Newton iteration and parallel finite element algorithm is applied for solving the steady Navier-Stokes equations under the strong uniqueness condition. This algorithm is motivated by applying the Newton iterations of m times for a nonlinear problem on a coarse grid in domain Ω and computing a linear problem on a fine grid in some subdomains Ω _j ⊂Ω with j=1,…,M in a parallel environment. Then, the error estimation of the Newton iterative parallel finite element solution to the solution of the steady Navier-Stokes equations is analyzed for the large m and small H and h≪H. Finally, some numerical tests are made to demonstrate the the effectiveness of this algorithm.     

Extension of <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis> log <Emphasis Type="Italic">n</Emphasis>) Filtering Algorithms for the Unary Resource Constraint to Optional Activities

Scheduling is one of the most successful application areas of constraint programming mainly thanks to special global constraints designed to model resource restrictions. Among these global constraints, edge-finding and not-first/not-last are the most popular filtering algorithms for unary resources. In this paper we introduce new O(n log n) versions of these two filtering algorithms and one more O(n log n) filtering algorithm called detectable precedences. These algorithms use a special data structures Θ-tree and Θ-Λ-tree. These data structures are especially designed for “what-if” reasoning about a set of activities so we also propose to use them for handling so called optional activities, i.e. activities which may or may not appear on the resource. In particular, we propose new O(n log n) variants of filtering algorithms which are able to handle optional activities: overload checking, detectable precedences and not-first/not-last.