We present OptCCL, a technique to synthesize collective communication algorithms that are optimal for a given host and network hardware and topology. OptCCL is general: it enables synthesizing optimal algorithms for all existing collectives, for all existing hardware, and even for multiple concurrent collectives sharing host and network resources. And yet, OptCCL is scalable: it synthesizes optimal algorithms for hundreds of GPUs within tens of minutes.

The Joint Replenishment Problem (JRP) is a classical inventory management problem, that aims to model the trade-off between coordinating orders for multiple commodities (and their cost) with holding costs incurred by meeting demand in advance. Recently, Moseley, Niaparast and Ravi introduced a natural online generalization of the JRP in which inventory corresponding to demands may be replenished late, for a delay cost, or early, in which case there is a holding cost associated with storing it until the desired service time. They established that when the holding and delay costs are monotone and uniform across demands, there is a 30-competitive algorithm that employs a greedy strategy and a dual-fitting based analysis; notably, they left relaxing the uniformity assumption as an open problem. This assumption is a significant limitation, and in fact, remarkable from the perspective that most online problems with only delay costs do not require uniformity, only monotonicity.

The joint replenishment problem (JRP) is a classical inventory management problem. We consider a natural generalization with outliers, where we are allowed to reject (that is, not service) a subset of demand points. In this paper, we are motivated by issues of fairness - if we do not serve all of the demands, we wish to “spread out the pain” in a balanced way among customers, communities, or any specified market segmentation. One approach is to constrain the rejections allowed, and to have separate bounds for each given customer. In our most general setting, we consider a set of C features, where each demand point has an associated rejection cost for each feature, and we have a given bound on the allowed rejection cost incurred in total for each feature. This generalizes an extensively studied model of fairness introduced in earlier work on the Colorful k—Center problem in which (analogously) each demand point has a given color, and we bound the number of rejections of each color class. In the JRP, we seek to balance the cost incurred by a fixed ordering overhead with the cost of maintaining on-hand inventory over a longer period in advance of when it is needed. More precisely, there is a given set of item types, for which there is specified demand over a finite, discrete-time horizon, and placing any order at a given time incurs a general ordering cost and item-specific ordering costs (independent of the total demand serviced); in addition, for each unit of demand held in inventory for an interval of time, there is a corresponding item-specific holding cost incurred; the aim is to minimize the total cost.

The Simplex algorithm for solving linear programs---one of Computing in Science & Engineering's top 10 most influential algorithms of the 20th century---is an important topic in many algorithms courses. While the algorithm relies on intuitive geometric ideas, the computationally-involved mechanics of the algorithm can obfuscate a geometric understanding. In this paper, we present gilp, an easy-to-use Simplex algorithm visualization tool designed to connect the mechanical steps of the algorithm with their geometric interpretation. We provide an extensive library of example visualizations, and our tool allows instructors to quickly produce custom interactive HTML files for students to experiment with the algorithm (without requiring students to install anything!). The tool can also be used for interactive assignments in Jupyter notebooks, and has been incorporated into a forthcoming Data Science and Decision Making interactive textbook. In this paper, we first describe how the tool fits into the existing algorithm visualization literature: how it was designed to facilitate student engagement and instructor adoption, and how it substantially extends existing algorithm visualization tools for Simplex. We then describe the development and usage of the tool, and report feedback from its use in a course with roughly 100 students. Student feedback was overwhelmingly positive, with students finding the tool easy to use: it effectively helped them link the algebraic and geometrical views of the Simplex algorithm and understand its nuances. Finally, gilp is open-source, includes an extension to visualizing linear programming-based branch and bound, and is readily amenable to further extensions.

Packet scheduling over a switch (interconnect) fabric is a wellstudied problem in distributed computing, with known near-optimal distributed bipartite matching based protocols.

The Fair Representation Act, first introduced in 2017 and reintroduced in 2019 and 2021, would mandate the use of multi-member districts (MMDs) to elect members to the United States House of Representatives, i.e., having fewer, larger districts each with multiple representatives. The bill is supported by good governance organizations such as FairVote; the American Academy of Arts and Sciences in 2020 released a report advocating states to use multi-member districts - however, "on the condition that they adopt a non-winner-take-all election model." Despite the popular focus on single-member district (SMD) elections, such MMDs have a long history in the United States, especially at the state and local level. In 1962, 41 state legislatures had MMDs, often with winner-take-all models; even today, 10 state legislatures elect representatives for at least one chamber in such a manner. City councils, state parties, and other organizations often adopt more sophisticated techniques, using variations on Ranked Choice Voting (RCV) to elect multiple winners from each of several districts.

We present the first nontrivial approximation algorithm for the bottleneck asymmetric traveling salesman problem . Given an asymmetric metric cost between n vertices, the problem is to find a Hamiltonian cycle that minimizes its bottleneck (or maximum-length edge) cost. We achieve an O (log n / log log n ) approximation performance guarantee by giving a novel algorithmic technique to shortcut Eulerian circuits while bounding the lengths of the shortcuts needed. This allows us to build on a related result of Asadpour, Goemans, Mądry, Oveis Gharan, and Saberi to obtain this guarantee. Furthermore, we show how our technique yields stronger approximation bounds in some cases, such as the bounded orientable genus case studied by Oveis Gharan and Saberi. We also explore the possibility of further improvement upon our main result through a comparison to the symmetric counterpart of the problem.

Bike-sharing systems provide a sustainable and affordable transportation alternative in many American cities. However, they also face intricate challenges due to imbalance, caused by asymmetric traffic demand. That imbalance often-times leads to bike-sharing stations being empty (full), causing out-of-stock events for customers that want to rent (return) bikes at such stations. In recent years, the study of data-driven methods to help support the operation of such system, has developed as a popular research area.

We present Sincronia, a near-optimal network design for coflows that can be implemented on top on any transport layer (for flows) that supports priority scheduling. Sincronia achieves this using a key technical result --- we show that given a "right" ordering of coflows, any per-flow rate allocation mechanism achieves average coflow completion time within 4X of the optimal as long as (co)flows are prioritized with respect to the ordering.

We consider constrained versions of the prize-collecting traveling salesman and the minimum spanning tree problems. The goal is to maximize the number of vertices in the returned tour/tree subject to a bound on the tour/tree cost. We present a 2-approximation algorithm for these problems based on a primal-dual approach. The algorithm relies on finding a threshold value for the dual variable corresponding to the budget constraint in the primal and then carefully constructing a tour/tree that is just within budget. Thereby, we improve the best-known guarantees from 3+epsilon and 2+epsilon for the tree and the tour version, respectively. Our analysis extends to the setting with weighted vertices, in which we want to maximize the total weight of vertices in the tour/tree subject to the same budget constraint.

We consider the following single-machine scheduling problem, which is often denoted $1||\sum f_{j}$: we are given $n$ jobs to be scheduled on a single machine, where each job $j$ has an integral processing time $p_j$, and there is a nondecreasing, nonnegative cost function $f_j(C_{j})$ that specifies the cost of finishing $j$ at time $C_{j}$; the objective is to minimize $\sum_{j=1}^n f_j(C_j)$. Bansal and Pruhs recently gave the first constant approximation algorithm with a performance guarantee of 16. We improve on this result by giving a primal-dual pseudo-polynomial-time algorithm based on the recently introduced knapsack-cover inequalities. The algorithm finds a schedule of cost at most four times the constructed dual solution. Although we show that this bound is tight for our algorithm, we leave open the question of whether the integrality gap of the linear program is less than 4. Finally, we show how the technique can be adapted to yield, for any $\epsilon >0$, a polynomial time $(4+\epsilon )$-approximation algorithm for this problem.

Bike-sharing systems are becoming increasingly prevalent in urban environments. They provide a low-cost, environmentally-friendly transportation alternative for cities. The management of these systems gives rise to many optimization problems. Chief among these problems is the issue of bicycle rebalancing. Users imbalance the system by creating demand in an asymmetric pattern. This necessitates action to put the system back in balance with the requisite levels of bicycles at each station to facilitate future use. In this paper, we tackle the problem of maintaing system balance during peak rush-hour usageas well as rebalancing overnight to prepare the systemfor rush-hour usage. We provide novel problem formulationsthat have been motivated by both a close collaborationwith the New York City bike share (Citibike) and a careful analysisof system usage data. We analyze system data to discover the best placement of bikes tofacilitate usage. We solve routing problems forovernight shifts as well as clustering problems for handlingmid rush-hour usage. The tools developed from this research are currently in daily use at NYC Bike Share LLC, operators of Citibike.

We present a deterministic (1+√5/2)-approximation algorithm for the s - t path TSP for an arbitrary metric. Given a symmetric metric cost on n vertices including two prespecified endpoints, the problem is to find a shortest Hamiltonian path between the two endpoints; Hoogeveen showed that the natural variant of Christofides' algorithm is a 5/3-approximation algorithm for this problem, and this asymptotically tight bound in fact has been the best approximation ratio known until now. We modify this algorithm so that it chooses the initial spanning tree based on an optimal solution to the Held-Karp relaxation rather than a minimum spanning tree; we prove this simple but crucial modification leads to an improved approximation ratio, surpassing the 20-year-old ratio set by the natural Christofides' algorithm variant. Our algorithm also proves an upper bound of 1+√5/2 on the integrality gap of the path-variant Held-Karp relaxation. The techniques devised in this article can be applied to other optimization problems as well: these applications include improved approximation algorithms and improved LP integrality gap upper bounds for the prize-collecting s - t path problem and the unit-weight graphical metric s - t path TSP.

We present a deterministic (1+√5/2)-approximation algorithm for the s-t path TSP for an arbitrary metric. Given a symmetric metric cost on $n$ vertices including two prespecified endpoints, the problem is to find a shortest Hamiltonian path between the two endpoints; Hoogeveen showed that the natural variant of Christofides' algorithm is a 5/3-approximation algorithm for this problem, and this asymptotically tight bound in fact had been the best approximation ratio known until now. We modify this algorithm so that it chooses the initial spanning tree based on an optimal solution to the Held-Karp relaxation rather than a minimum spanning tree; we prove this simple but crucial modification leads to an improved approximation ratio, surpassing the 20-year-old barrier set by the natural Christofides' algorithm variant. Our algorithm also proves an upper bound of 1+√5/2 on the integrality gap of the path-variant Held-Karp relaxation. The techniques devised in this paper can be applied to other optimization problems as well: these applications include improved approximation algorithms and improved LP integrality gap upper bounds for the prize-collecting s-t path problem and the unit-weight graphical metric s-t path TSP.

Stochastic optimization problems provide a means to model uncertainty in the input data where the uncertainty is modeled by a probability distribution over the possible realizations of the actual data. We consider a broad class of these problems in which the realized input is revealed through a series of stages and hence are called multistage stochastic programming problems. Multistage stochastic programming and, in particular, multistage stochastic linear programs with full recourse, is a domain that has received a great deal of attention within the operations research community, mostly from the perspective of computational results in application settings. Our main result is to give the first fully polynomial approximation scheme for a broad class of multistage stochastic linear programming problems with any constant number of stages. The algorithm analyzed, known as the sample average approximation method, is quite simple and is the one most commonly used in practice. The algorithm accesses the input by means of a “black box” that can generate, given a series of outcomes for the initial stages, a sample of the input according to the conditional probability distribution (given those outcomes). We use this to obtain the first approximation algorithms for a variety of $k$-stage generalizations of basic combinatorial optimization problems including the set cover, vertex cover, multicut on trees, facility location, and multicommodity flow problems.

We consider a fault-tolerant generalization of the classical uncapacitated facility location problem, where each client j has a requirement that r j distinct facilities serve it, instead of just one. We give a 2.076-approximation algorithm for this problem using LP rounding, which is currently the best-known performance guarantee. Our algorithm exploits primal and dual complementary slackness conditions and is based on clustered randomized rounding . A technical difficulty that we overcome is the presence of terms with negative coefficients in the dual objective function, which makes it difficult to bound the cost in terms of dual variables. For the case where all requirements are the same, we give a primal-dual 1.52-approximation algorithm. We also consider a fault-tolerant version of the k -median problem. In the metric k -median problem, we are given n points in a metric space. We must select k of these to be centers, and then assign each input point j to the selected center that is closest to it. In the fault-tolerant version we want j to be assigned to r j distinct centers. The goal is to select the k centers so as to minimize the sum of assignment costs. The primal-dual algorithm for fault-tolerant facility location with uniform requirements also yields a 4-approximation algorithm for the fault-tolerant k -median problem for this case. This the first constant-factor approximation algorithm for the uniform requirements case.

We consider two fundamental stochastic optimization problems that arise in the context of supply-chain models, the single-period newsvendor problem and its multiperiod extension with independent demands. These problems are among the most well-studied stochastic optimization problems in the Operations Research literature. Most commonly, these problems are studied from the perspective that the input probability distributions are given in terms of specific probability distribution functions that are computationally tractable; under this assumption, both problems can be solved efficiently. Unfortunately, this information is unlikely to be available in practice, and hence we make the more realistic assumption that the probability distribution is given by a "black box" from which independent samples can be drawn. We give the first fully polynomial randomized approximation schemes for these two problems in this sampling-based model.Our work provides new insights into the power of two of the most often-used approaches to solving stochastic optimization problems, the sample average approximation (SAA) and stochastic dynamic programming. For the newsvendor problem, we show that by taking a polynomial number of samples and then solving the newsvendor problem with respect to the resulting approximation to the true distribution, we obtain provably near-optimal solution. This significantly extends the class of problems for which the SAA is known to yield a scheme. Finally, we show how to adapt the framework of stochastic dynamic programming to yield an approximation scheme for the multiperiod newsvendor problem with independent demands. We believe that this is an interesting first step towards the goal of providing a mechanism for deriving efficient approximate stochastic dynamic programming methods for a wide range of multistage stochastic optimization problems.

Stochastic optimization problems attempt to model uncertainty in the data by assuming that the input is specified by a probability distribution. We consider the well-studied paradigm of 2-stage models with recourse: first, given only distributional information about (some of) the data one commits on initial actions, and then once the actual data is realized (according to the distribution), further (recourse) actions can be taken. We show that for a broad class of 2-stage linear models with recourse, one can, for any ϵ > 0, in time polynomial in 1/ϵ and the size of the input, compute a solution of value within a factor (1+ϵ) of the optimum, in spite of the fact that exponentially many second-stage scenarios may occur. In conjunction with a suitable rounding scheme, this yields the first approximation algorithms for 2-stage stochastic integer optimization problems where the underlying random data is given by a “black box” and no restrictions are placed on the costs in the two stages. Our rounding approach for stochastic integer programs shows that an approximation algorithm for a deterministic analogue yields, with a small constant-factor loss, provably near-optimal solutions for the stochastic generalization. Among the range of applications, we consider are stochastic versions of the multicommodity flow, set cover, vertex cover, and facility location problems.

Stochastic optimization problems provide a means to model uncertainty in the input data where the uncertainty is modeled by a probability distribution over the possible realizations of the actual data. We consider a broad class of these problems in which the realized input is revealed through a series of stages, and hence are called multi-stage stochastic programming problems. Our main result is to give the first fully polynomial approximation scheme for a broad class of multi-stage stochastic linear programming problems with any constant number of stages. The algorithm analyzed, known as the sample average approximation (SAA) method, is quite simple, and is the one most commonly used in practice. The algorithm accesses the input by means of a "black box" that can generate, given a series of outcomes for the initial stages, a sample of the input according to the conditional probability distribution (given those outcomes). We use this to obtain the first polynomial-time approximation algorithms for a variety of k-stage generalizations of basic combinatorial optimization problems.

Stochastic optimization problems attempt to model uncertainty in the data by assuming that (part of) the input is specified in terms of a probability distribution. We consider the well-studied paradigm of 2-stage models with recourse: first, given only distributional information about (some of) the data one commits on initial actions, and then once the actual data is realized (according to the distribution), further (recourse) actions can be taken. We give the first approximation algorithms for 2-stage discrete stochastic optimization problems with recourse for which the underlying random data is given by a "black box" and no restrictions are placed on the costs in the two stages, based on an FPRAS for the LP relaxation of the stochastic problem (which has exponentially many variables and constraints). Among the range of applications we consider are stochastic versions of the set cover, vertex cover, facility location, multicut (on trees), and multicommodity flow problems.

We consider several classical models in deterministic inventory theory: the single-item lot-sizing problem, the joint replenishment problem, and the multi-stage assembly problem. These inventory models have been studied extensively, and play a fundamental role in broader planning issues, such as the management of supply chains. We shall give a novel primal-dual framework for designing algorithms for these models that significantly improve known results in several ways: the performance guarantees for the quality of the solutions improve on or match previously known results; the performance guarantees hold under much more general assumptions about the structure of the costs, and the algorithms and their analysis are significantly simpler than previous known results. Finally, our primal-dual framework departs from the structure of previously studied primal-dual approximation algorithms in significant ways, and we believe that our approach may find application in other settings.We provide 2-approximation algorithms for the joint replenishment problem and for the assembly problem, and solve the single-item lot-sizing problem to optimality. The results for the joint replenishment and the lot-sizing problems also hold for their generalizations with back orders allowed. As a byproduct of our work, we prove known and new upper bounds on the integrality gap of the LP relaxations for these problems.

We consider the uncapacitated facility location problem. In this problem, there is a set of locations at which facilities can be built; a fixed cost f i is incurred if a facility is opened at location i. Furthermore, there is a set of demand locations to be serviced by the opened facilities; if the demand location j is assigned to a facility at location i, then there is an associated service cost proportional to the distance between i and j, c ij . The objective is to determine which facilities to open and an assignment of demand points to the opened facilities, so as to minimize the total cost. We assume that the distance function c is symmetric and satisfies the triangle inequality. For this problem we obtain a (1+2/e)-approximation algorithm, where $1+2/e \approx 1.736$, which is a significant improvement on the previously known approximation guarantees. The algorithm works by rounding an optimal fractional solution to a linear programming relaxation. Our techniques use properties of optimal solutions to the linear program, randomized rounding, as well as a generalization of the decomposition techniques of Shmoys, Tardos, and Aardal [Proceedings of the 29th ACM Symposium on Theory of Computing, El Paso, TX, 1997, pp. 265--274].

No abstract available.

Article Free Access Share on A constant-factor approximation algorithm for the k-median problem (extended abstract) Authors: Moses Charikar Stanford University, Stanford, CA Stanford University, Stanford, CAView Profile , Sudipto Guha Stanford University, Stanford, CA Stanford University, Stanford, CAView Profile , Éva Tardos Cornell University, Ithaca, NY Cornell University, Ithaca, NYView Profile , David B. Shmoys Cornell University, Ithaca, NY Cornell University, Ithaca, NYView Profile Authors Info & Claims STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of ComputingMay 1999 Pages 1–10https://doi.org/10.1145/301250.301257Published:01 May 1999Publication History 170citation1,175DownloadsMetricsTotal Citations170Total Downloads1,175Last 12 Months198Last 6 weeks31 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

We present new approximation algorithms for several facility location problems.In each facility location problem that we study, there is a set of locations at which we may build a facility (such as a warehouse), where the cost of building at location i is ~i; ftiermore, there is a set of client locations (such as stores) that require to be serviced by a facility, and if a client at location j is assigned to a facility at location i, a cost of cl] is incurred that is proportional to the distance between i and j.The objective is to determine a set of locations at which to open facilities so as to minimize the total facility and assignment costs.In the incapacitated case, each facility can service an unlimited number of clients, whereas in the capacitated case, each facility can serve, for example, at most u clients.These models and a number of closely related ones have been studied extensively in the Operations Research literature.We shall consider the case in which the distances between locations are non-negative, symmetric and satisfy the triangle inequality.For the incapacitated facility location, we give a polynomial-time algorithm that finds a solution of cost within a factor of 3.16 of the optimal.This is the first constant performance guarantee known for this problem.We also present approximation algorithms with constant performance guarantees for a number of capacitated models as well as a generalization in which there is a 2-level hierarchy of facilities.Our results are based on the filtering and rounding technique of Lin & Wter.We also give a randomized variant of this technique that can then be derandomized to yield improved deterministic performance guarantees.

The problem of scheduling jobs on parallel machines is studied when (1) the existence of a job is not known until its unknown release date and (2) the processing requirement of a job is not known until the job is processed to completion. Two general algorithmic techniques are demonstrated for converting existing polynomial-time algorithms that require complete knowledge about the input data into algorithms that need less advance knowledge. Information-theoretic lower bounds on the length of on-line schedules are proven for several basic parallel machine models, and almost all of our algorithms construct schedules with lengths that either match or come within a constant factor of the lower bound.

In the job shop scheduling problem, there are m machines and n jobs. A job consists of a sequence of operations, each of which must be processed on a specified machine, and the aim is to complete all jobs as quickly as possible. This problem is strongly .$\mathcal{NP}$-hard even for very restrictive special cases. The authors give the first randomized and deterministic polynomial-time algorithms that yield polylogarithmic approximations to the optimal length schedule. These algorithms also extend to the more general case where a job is given not by a linear ordering of the machines on which it must be processed but by an arbitrary partial order. Comparable bounds can also be obtained when there are $m'$ types of machines, a specified number of machines of each type, and each operation must be processed on one of the machines of a specified type, as well as for the problem of scheduling unrelated parallel machines subject to chain precedence constraints.

In this paper interior-point methods for linear programming, developed in the context of sequential computation, are used to obtain a parallel algorithm for the bipartite matching problem. This algorithm finds a maximum cardinality matching in a bipartite graph with n nodes and m edges in $O(\sqrt m \log ^3 n)$ time on a CRCW PRAM. The results here extend to the weighted bipartite matching problem and to the zero-one minimum-cost flow problem, yielding $O(\sqrt m \log ^2 n\log nC)$ algorithms, where $C > 1$ is an upper bound on the absolute value of the integral weights or costs in the two problems, respectively. The results here improve previous bounds on these problems and introduce interior-point methods to the context of parallel algorithm design.

Fast algorithms that find approximate solutions for a general class of problems, which are called fractional packing and covering problems, are presented. The only previously known algorithms for solving these problems are based on general linear programming techniques. The techniques developed greatly outperform the general methods in many applications, and are extensions of a method previously applied to find approximate solutions to multicommodity flow problems. The algorithms are based on a Lagrangian relaxation technique, and an important result is a theoretical analysis of the running time of a Lagrangian relaxation based algorithm. Several applications of the algorithms are presented.>

The authors study the problem of scheduling jobs on parallel machines when the existence of a job is not known until an unknown release date and the processing requirement of a job is not known until the job is processed to completion. They demonstrate two general algorithmic techniques for converting existing polynomial-time algorithms that require complete knowledge about the input data into algorithms that need less advance knowledge. They prove information-theoretic lower bounds on the lengths of online schedules for several basic parallel machine models and then show that the algorithms construct schedules with lengths that either match or come within a constant factor of the lower bounds.>

In their 1971 paper on the travelling salesman problem and minimum spanning trees, Held and Karp showed that finding an optimally weighted 1-tree is equivalent to solving a linear program for the traveling salesman problem (TSP) with only node-degree constraints and subtour elimination constraints. In this paper we show that the Held-Karp 1-trees have a certain monotonicity property: given a particular instance of the symmetric TSP with triangle inequality, the cost of the minimum weighted 1-tree is monotonic with respect to the set of nodes included. As a consequence, we obtain an alternate proof of a result of Wolsey and show that linear programs with node-degree and subtour elimination constraints must have a cost at least 23OPT where OPT is the cost of the optimum solution to the TSP instance.

A persuasive coin is a sufficiently unbiased source of randomness visible to sufficiently many processors in a distributed system. An algorithm is described for achieving a persuasive coin in the presence of an extremely powerful adversary where the number of rounds of message exchange among the processors is constant, independent of the number n of processors in the system as well as the number of faults, provided the total number of faulty processors does not exceed a certain constant multiple of $n/\log n$. As a corollary an $\Omega (n/\log n)$-resilient probabilistic protocol for Byzantine agreement running in constant expected time is obtained. Combining this with a generalization of a technique of Bracha, a probabilistic Byzantine agreement protocol tolerant of almost ${n / 4}$ failures with $O(\log \log n)$ expected running time is obtained.

Interior-point methods for linear programming, developed in the context of sequential computation, are used to obtain a parallel algorithm for the bipartite matching problem. The algorithm runs in O*( square root m) time. The results extend to the weighted bipartite matching problem and to the zero-one minimum-cost flow problem, yielding O*( square root m log C) algorithms. This improves previous bounds on these problems and illustrates the importance of interior-point methods in parallel algorithm design.>

Several constrained scheduling problems are considered. The first polynomial approximation schemes for the problem of minimizing maximum completion time in a two-machine flow shop with release dates and for the problem of minimizing maximum lateness for the single and parallel-machine problem with release dates are described. All of these algorithms are based upon the notion of an outline, a set of information with which it is possible to compute, with relatively simple procedures and in polynomial time, an optimal or near-optimal solution to the problem instance under consideration. Two related precedence-constrained scheduling problems are discussed, and new approximation results are presented.>

Using simple protocols, it is shown how to achieve consensus in constant expected time, within a variety of fail-stop and omission failure models. Significantly, the strongest models considered are completely asynchronous. All of the results are based on distributively flipping a coin, which is usable by a significant majority of the processors. Finally, a nearly matching lower bound is also given for randomized protocols for consensus.

We present a polynomial approximation scheme for the minimum makespan problem on uniform parallel processors. More specifically, the problem is to find a schedule for a set of independent jobs on a collection of machines of different speeds so that the last job to finish is completed as quickly as possible. We give a family of polynomial-time algorithms $\{ {A_\varepsilon } \}$ such that $A_\varepsilon $ delivers a solution that is within a relative error $\varepsilon $ of the optimum. This is a dramatic improvement over previously known algorithms; the best performance guarantee previously proved for a polynomial-time algorithm ensured a relative error no more than 40 percent. The technique employed is the dual approximation approach, where infeasible but superoptimal solutions for a related (dual) problem are converted to the desired feasible but possibly suboptimal solution.

We consider the following scheduling problem. There are m parallel machines and n independent jobs. Each job is to be assigned to one of the machines. The processing of job j on machine i requires time pij. The objective is to find a schedule that minimizes the makespan. Our main result is a polynomial algorithm which constructs a schedule that is guaranteed to be no longer than twice the optimum. We also present a polynomial approximation scheme for the case that the number of machines is fixed. Both approximation results are corollaries of a theorem about the relationship of a class of integer programming problems and their linear programming relaxations. In particular, we give a polynomial method to round the fractional extreme points of the linear program to integral points that nearly satisfy the constraints. In contrast to our main result, we prove that no polynomial algorithm can achieve a worst-case ratio less than 3/2 unless P = NP. We finally obtain a complexity classification for all special cases with a fixed number of processing times.

The problem of scheduling a set of n jobs on m identical machines so as to minimize the makespan time is perhaps the most well-studied problem in the theory of approximation algorithms for NP-hard optimization problems. In this paper the strongest possible type of result for this problem, a polynomial approximation scheme, is presented. More precisely, for each ε, an algorithm that runs in time O (( n /ε) 1/ε 2 ) and has relative error at most ε is given. In addition, more practical algorithms for ε = 1/5 + 2 - k and ε = 1/6 + 2 - k , which have running times O ( n ( k + log n )) and O ( n ( km 4 + log n )) are presented. The techniques of analysis used in proving these results are extremely simple, especially in comparison with the baroque weighting techniques used previously. The scheme is based on a new approach to constructing approximation algorithms, which is called dual approximation algorithms, where the aim is to find superoptimal, but infeasible, solutions, and the performance is measured by the degree of infeasibility allowed. This notion should find wide applicability in its own right and should be considered for any optimization problem where traditional approximation algorithms have been particularly elusive.

We present a distributed protocol for achieving a distributed coin in the presence of an extremely powerful adversary in constant time. The protocol can tolerate up to n/log n malicious processor failures where n is the number of processors in the system. The protocol needs only a fixed constant number of rounds of message exchange; no preprocessing is required. As a corollary we obtain an (n/log n)-resilient probabilistic protocol for Byzantine agreement running in constant expected time. Combining this with a generalization of a technique of Bracha, we obtain a probabilistic Byzantine agreement protocol tolerant of almost n/3 failures with O(log log n) expected running time.

In this paper a powerful, and yet simple, technique for devising approximation algorithms for a wide variety of NP-complete problems in routing, location, and communication network design is investigated. Each of the algorithms presented here delivers an approximate solution guaranteed to be within a constant factor of the optimal solution. In addition, for several of these problems we can show that unless P = NP, there does not exist a polynomial-time algorithm that has a better performance guarantee.

The problem of scheduling a set of n jobs on m identical machines so as to minimize the makespan time is perhaps the most well-studied problem in the theory of approximation algorithms for NP-hard optimization problems. In this paper we present the strongest possible type of result for this problem, a polynomial approximation scheme. More precisely, for each ε, we give an algorithm that runs in time O((n/ε)1/ε2) and has relative error at most ε. For algorithms that are polynomial in n and m, the strongest previously-known result was that the MULTIFIT algorithm delivers a solution with no worse than 20% relative error. In addition, we present a refinement of our scheme in the case where the performance guarantee is equal to that of MUL-TIFIT, that yields an algorithm that is both more efficient and easier to analyze than MULTIFIT. In this case, in order to guarantee a maximum relative error of 1/5+2-k, the algorithm runs in O(n(k+logn)) time. The scheme is based on a new approach to constructing approximation algorithms, which we call dual approximation algorithms, where the aim is find superoptimal, but infeasible solutions, and the performance is measured by the degree of infeasibility allowed. This notion should find wide applicability in its own right, and should be considered for any optimization problem where traditional approximation algorithms have been particularly elusive.

Article Simple constant-time consensus protocols in realistic failure models (extended abstract) Share on Authors: Benny Chor MIT Cambridge, MA MIT Cambridge, MAView Profile , Michael Merritt AT&T Bell Labs, Murray Hill, NJ and MIT, Cambridge, MA AT&T Bell Labs, Murray Hill, NJ and MIT, Cambridge, MAView Profile , David B. Shmoys Harvard University, Cambridge, MA Harvard University, Cambridge, MAView Profile Authors Info & Claims PODC '85: Proceedings of the fourth annual ACM symposium on Principles of distributed computingAugust 1985 Pages 152–162https://doi.org/10.1145/323596.323610Online:01 August 1985Publication History 10citation211DownloadsMetricsTotal Citations10Total Downloads211Last 12 Months4Last 6 weeks2 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 SiteGet Access

In this paper we investigate a powerful, and yet simple, technique for devising approximation algorithms for a wide variety of NP-complete problems in routing, location, and communication network design. Each of the algorithms presented here delivers an approximate solution guaranteed to be within a constant factor of the optimal solution. In addition, for several of these problems we can show that unless P=NP, there does not exist a polynomial-time algorithm that has a better performance guarantee.