Given a rectangular boundary partitioned into rectangles, the Minimum-Length Corridor (MLC-R) problem consists of finding a corridor of least total length. A corridor is a set of connected line segments, each of which must lie along the line segments that form the rectangular boundary and/or the boundary of the rectangles, and must include at least one point from the boundary of every rectangle and from the rectangular boundary. The MLC-R problem is known to be NP-hard. We present the first polynomial-time constant ratio approximation algorithm for the MLC-R and MLC k problems. The MLC k problem is a generalization of the MLC-R problem where the rectangles are rectilinear c -gons, for c ≤ k and k is a constant. We also present the first polynomial-time constant ratio approximation algorithm for the Group Traveling Salesperson Problem (GTSP) for a rectangular boundary partitioned into rectilinear c -gons as in the MLC k problem. Our algorithms are based on the restriction and relaxation approximation techniques.

We consider the continuously delivery message dissemination (CDMD) problem over the n processor single-port complete (all links are present and are bi-directional) static network with the multicasting communication primitive. This problem has been shown to be NP-complete even when all messages have equal length. For the CDMD problem we present an efficient approximation algorithm to construct a message routing schedule with total communication time at most 3.5d, where d is the total length of the messages that each processor needs to send or receive. The algorithm takes O(qn) time, where n is the number of processors and q is the total number of messages that the processors receive.

We discuss algorithms, complexity issues, and applications for message dissemination problems under the multicasting communication mode. These problems arise while executing in a parallel or distributed computing environment iterative methods for solving scientific computation applications, dynamic programming procedures, sparse matrix multiplication, etc. Our message communication problems also arise when disseminating information over ad-hoc wireless networks. Given a communication environment and a set of messages that need to be exchanged, the message dissemination problem is to find a schedule to transmit all the messages in the least total number of communication rounds. Generating an optimal communication schedule (with the least total number of communication rounds) for message dissemination problems over a wide range of communication environments is an NP-hard problem. To cope with intractability efficient message dissemination approximation algorithms have been developed for different types of communication environments and message communication patterns (the communications that must take place). The communication environment consists of the communication network (the direct communications allowed for each processor), primitive operations (the basic communication operations allowed by the system), and the communication model (possible operations during each communication round or step). Our goal is to present scattered research results developed during the last decade to establish that the multicasting (one-to-many) communication environment is a powerful communication primitive that allows for solutions that are considerable better than those achievable under the telephone (or one-to-one) communication environment. The multicasting communication environment has been available for quite some time in parallel computing systems. We also establish that, within the multicasting communication mode, forwarding plays an important role by allowing solutions that are considerable better than when restricting to direct communications, even when the communication load is balanced and the network is complete (all possible bidirectional links are present). We show that off-line communication scheduling allows for considerably better solutions over on-line scheduling. However, on-line scheduling provides added flexibility and it is applicable to a larger set of scenarios.

Consider n independent jobs and m uniform machines in parallel. Each job has a processing requirement and a deadline. All jobs are available for processing at time t = 0. Job j must complete its processing before or at its deadline and preemptions are allowed. A set of jobs is said to be feasible if there exists a schedule that meets all the deadlines. We present a polynomial-time algorithm that given a feasible set of jobs, constructs a schedule that minimizes the total completion time Σ C j . In the classical α | β | γ scheduling notation, this problem is referred to as Qm | prmt , d¯ j | Σ C j . It is well known that a generalization of this problem with regard to its machine environment results in an NP-hard problem.

Performance profiling consists of monitoring a software system during execution and then analyzing the obtained data. There are two ways to collect profiling data: event tracing through code instrumentation and statistical sampling. These two approaches have different advantages and drawbacks. This paper proposes a hybrid approach to data collection that combines the completeness of event tracing with the low cost of statistical sampling. We propose to maximize the weighted amount of information obtained during data collection, show that such maximization can be performed in linear time or is NP-hard depending on the data collected and the collection implementation. We propose an approximation algorithm for NP-hard case. Our paper also presents an application of the formal approach to an example use case.

We present an algorithm for the gossiping problem defined over an n processor communication network, N, where message multicasting is allowed. The algorithm generates a communication schedule with a total communication time at most N+r, where r is the radius of the network. Our algorithm begins by constructing a spanning tree (or tree network T) with the least possible radius. Then, all the communications are carried out in the tree network as follows: each processor waits its turn to transmit "almost" consecutively to its parent and children all the messages in its subtree. During other times, each processor transmits to its children all the messages emanating elsewhere in the network.

The gossiping problem consists of an n processor communication network N, in which every processor has to broadcast a single message. We present an efficient algorithm to generate a communication schedule with total communication time at most n+r, where r is the radius of the network, when message multicasting is allowed. Our algorithm begins by constructing a spanning tree (or tree network T) with least possible radius. Then all the communications are carried out in the tree network as follows. Each processor waits its turn to transmit consecutively to its parent and children all the messages in its subtree. Before and after these communications, each processor must transmit to its children all the messages emanating elsewhere in the network.

Investigates the pin redistribution problem (PRP) for multi-chip modules. A novel transformation to the max-flow problem is introduced. This approach provides an efficient algorithm for finding a 2-layer solution, whenever one exists. A greedy heuristic to find a k-layer solution is described. The approach can find a minimum layer solution for two variants of the PRP; when each net can be routed on more than one layer, and when source and target terminals are drilled through all layers. Except for the heuristic procedure which takes O(km/sup 4/ log/sup 2/ m) time, the algorithms take O(/spl verbar/S/spl verbar/km/sup 2/) time, where S is the set of source terminals, m is the number of rows and columns in the grid, and k is the number of layers required. One can show that generalizations of the k-layer PRP are NP-complete problems.>

The authors define a class of languages (called rectilinear) to describe coloured digitized maps and classify them on the basis of their level of succinct representation. The map compression problem is defined as the problem of finding for any given map a shortest description within a given language. For one dimensional maps, that a shortest description can be generated quickly for some languages, but for other languages the problem is NP-hard. A large number of linear time algorithms generate map descriptions whose length is at most twice the minimum.>

The generalized channel definition problem has been modeled as the following partition problem. Let RP be a boundary defined by a rectilinear polygon in E/sup 2/ and let H be a set of holes defined by disjoint rectilinear polygons inside RP. For IP=(RP,H), p(IP) is used to denote the length of the line segments that define RP plus the sum of the length of the line segments that define the holes in H. The authors consider the RP-RP problem in which RP is partitioned into rectangles by introducing a set of orthogonal line segments with least total length. Then m(IP) is used to denote the total length of the partitioning segments in an optimal solution to IP. The problem of finding m(IP) given IP is NP-hard. In this paper an O(n log n) approximation algorithm is presented for the RP-RP problem that generates solutions with length at most 2.5p(IP)+6m(IP), where n is the total number of segments in RP and H.>

Let R be a rectangle uniformly partitioned by w-1 vertical line segments and h-1 horizontal line segments. The problem of routing through the rectangle, called the RRP problem (also referred to as the switch-box routing problem), is considered. It is denoted by I=(R, N), and consists of finding a layout under the knock-knee wiring model for the set N of nets inside R. The authors present a set of transformations different from the ones given by K. Mehlhorn et al. (Journal of ACM, vol.33, no.1, p.60-85, 1986) that provide smaller approximation bounds for the unrestricted RRP and the three-terminal-net RRP problems.>

The problem of constructing makespan-optimal preemptive schedules for n independent jobs on m unrelated parallel processors is discussed. For the case of two processors, we present a linear time algorithm to construct optimal schedules. The schedules generated by our algorithm have at most two preemptions. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

The authors consider the via placement problem that arises in multilayer printed circuit board (MPCB) layout systems. It is shown that this problem can be formulated as an integer linear max-flow problem. Since the integer linear max-flow problem is an NP-complete problem, it is unlikely that one can find an efficient algorithm for its solution. However, a solution to this via placement problem can be obtained by relaxing the integer constraints in the integer linear max-flow problem. A solution to the relaxed linear max-flow problem can be obtained by solving a linear programming problem. The procedure generates in time bounded by a low order polynomial a placement with no more than 2*d/sub OPT/ density, where D/sub OPT/ is the density in an optimal placement.>

The problem of connecting a set of terminals that lie on the sides of a rectangle to minimize the total area is discussed. An O ( n ) algorithm is presented to solve this problem when the set of n terminals is initially sorted. The strategy in this paper is to reduce the problem to several problems such that no matter what instance is started with, at least one of these problems can be solved optimally by a greedy method.

A set of three algorithms is presented for solving single-row routine problems with a fixed street capacity using the least number of layers. The main difference among these algorithms is in the strategy used to search for an optimal solution, which greatly affects the performance. At the extreme points of the strategy are algorithms Q and S. The worst-case time complexity is linear for algorithm Q and exponential for algorithm S. The best-case time complexity of all the algorithms is linear. The main disadvantage of algorithm Q is that the constant associated with its time complexity bounds is large. On the other hand, the constant associated with the best-case time complexity bound for algorithm S is small. An experimental evaluation of the performance of the algorithms is presented.>

The problem of connecting a set of n terminals belonging to m (signal) nets that lie on the sides of a rectangle to minimize the total area is discussed. We present an $O(n(m + \log n))$approximation algorithm to solve this problem. Our algorithm generates a solution with area $ \leqq 1.6 * {\operatorname{OPT}}$, where ${\operatorname{OPT}}$ is the area of an optimal solution. The nets are routed according to the following greedy strategy: the wire connecting all points from a net is one whose path crosses the least number of corners of the rectangle. For some nets there are several routes that cross the least number of corners. A subset of these nets is connected by wires whose paths blend with the paths for other nets. The remaining nets are routed using several strategies and $2^6 $ layouts are obtained. The best of these layouts is the solution generated by our algorithm.

The problem of connecting a set of terminals that lie on the sides of a rectangle to minimize the total area is discussed. We present an O(nm) approximation algorithm to solve this problem where n is the number of terminals and m is the number of signal nets. Our algorithm generates a solution with an area ≤1.69* OPT where OPT is the area of an optimal solution. Our algorithm routes some of the nets by a simple greedy strategy. The remaining nets are routed using several strategies and four layouts are obtained. The best of these layouts is the solution generated by our algorithm.

We study the problem of partitioning a rectilinear polygon with interior points into rectangles by introducing a set of line segments. All points must be included in at least one of the line segments introduced and the objective function is to introduce a set of line segments such that the sum of their lengths is minimal. Since this problem is computationally intractable, we present efficient approximation algorithms for its solution. The solutions generated by our algorithms are guaranteed to be within a fixed constant of the optimal solution value. Even though the constant approximation bound is not so small, we conjecture that in general the solutions our algorithms generate are close to optimal.

We consider the multi-via assignment problem for multilayered printed circuit board routing. An efficient approximation algorithm for this problem is presented. The algorithm is of (low) polynomial time complexity and guarantees solutions with no more than 3 * OPT via columns, where OPT is the number of via columns in an optimal solution. Several issues relating to the computational complexity of via and multi-via assignment problems are also discussed.

We consider the problem of evaluating arithmetic expressions under a set of algebraic laws including the distributive law. An arithmetic expression can be represented by a dag and our problem is to find an equivalent dag with the fewest number of interior nodes. We attack the case when it is possible to eliminate common subexpressions and transform the dag into a tree; efficient algorithms to handle different cases of this problem are developed. These algorithms are based on the following strategy: we first transform the dag into a tree, assuming that such a transformation is possible, and we later check to see whether the tree and the given dag are indeed equivalent.

An algorithm which schedules forests of n tasks on m identical processors in O ( n log m ) time, offline, is given. The schedules are optimal with respect to finish time and contain at most n - 2 preemptions, a bound which is realized for all n . Also given is a simpler algorithm which runs in O ( nm ) time on the same problem and can be adapted to give optimal finish time schedules on-line for independent tasks with release times.

The problem of preemptively scheduling a set of n independent jobs on an m processor open shop is discussed. An algorithm to construct preemptive schedules with minimum-maximum finishing time is presented. The worst case time complexity is 0(r + min {m4, n4, r2}), where r is the number of nonzero tasks. The maximum number of preemptions introduced is 0(min {rn, rm, n3, m3}). The algorithm is best possible for open shops with a fixed number of processors or jobs. In this case the maximum number of preemptions introduced is bounded by some fixed constant.

Umverstty of Mmnesota, Mtnneapohs, MmnesotaAaSTRACT An O(n) t~me algorithm is presented to obtain an opt,mal fimsh time preemptive schedule for n independent tasks on m uniform processors This algorithm assumes that the tasks are lnmally ordered by task length and that the umform processors are ordered by processor speed KEY WORDS AND PHRASES.

We study the performance of LPT (largest processing time) schedules with respect to optimal schedules in a nonpreemptive multiprocessor environment. The processors are assumed to have different speeds and the tasks being scheduled are independent.

article Free Access Share on An Efficient Algorithm for the Kolmogorov-Smirnov and Lilliefors Tests Authors: Teofilo Gonzalez Department of Computer, Information and Control Sciences, 114 Main Engineering Building, Minneapolis, MN Department of Computer, Information and Control Sciences, 114 Main Engineering Building, Minneapolis, MNView Profile , Sartaj Sahni Department of Computer, Information and Control Sciences, 114 Main Engineering Building, Minneapolis, MN Department of Computer, Information and Control Sciences, 114 Main Engineering Building, Minneapolis, MNView Profile , W. R. Franta Department of Computer, Information and Control Sciences, 114 Main Engineering Building, Minneapolis, MN Department of Computer, Information and Control Sciences, 114 Main Engineering Building, Minneapolis, MNView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 3Issue 1March 1977 pp 60–64https://doi.org/10.1145/355719.355724Published:01 March 1977Publication History 23citation2,096DownloadsMetricsTotal Citations23Total Downloads2,096Last 12 Months621Last 6 weeks49 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A linear time algorithm to obtain a minimum finish time schedule for the two-processor open shop together with a polynomial time algorithm to obtain a minimum finish time preemptive schedule for open shops with more than two processors are obtained. It is also shown that the problem of obtaining minimum finish time nonpreemptive schedules when the open shop has more than two processors is NP-complete.

For P-complete problems such as traveling salesperson, cycle covers, 0-1 integer programming, multicommodity network flows, quadratic assignment, etc., it is shown that the approximation problem is also P-complete. In contrast with these results, a linear time approximation algorithm for the clustering problem is presented.