waashk/acm huggingface dataset:
expanding graphs and the average-case analysis of algorithms for matchings and related problems  hall's theorem states that a bipartite graph has a perfect matching if and only if every set of vertices has an equal number of neighbours. equivalently, it states that every non-maximum matching has an augmenting path if the graph is an expander with expansion 1. we use this insight to demonstrate that if a graph is an expander with expansion more than one than every non-maximum matching has a short augmenting path and, therefore, the bipartite matching algorithm performs much better on such graphs than in the worst case. we then apply this idea to the average case analysis of various augmenting path algorithms and to the approximation of the permanent. in particular, we demonstrate that the following algorithms perform much better on the average than in the worst case. in fact, they will rarely exhibit their worst-case running times.  hopcroft-karp's algorithm for bipartite matchings.  micali-vazirani's and even-kariv's algorithms for non-bipartite matchings.  gabow-tarjan's parallel algorithm for bipartite matchings.  dinic's algorithm for k-factors and 0-1 network flows.  jerrum-sinclair's approximation scheme for the permanent.  it seems rather surprising that the algorithms which are the fastest known for worst- case inputs also do exceedingly on almost every graph.  r. motwani
two fortran packages for assessing initial value methods  we present a discussion and description of a collection of fortran routines designed to aid in the assessment of initial value methods for ordinary differential equations. although the overall design characteristics are similar to those of earlier testing packages [2,6] that were used for the comparison of methods [5,7], the details and objectives of the current collection are quite different. our principal objective is the development of testing tools that can be used to assess the efficiency and reliability of a standard numerical method without requiring significant modifications to the method and without the tools themselves affecting the performance of the method.  w. h. enright j. d. pryce
bounds for width two branching programs  branching programs for the computation of boolean functions were first studied in the master's thesis of masek.7 in a rather straightforward manner they generalize the concept of a decision tree to a decision graph.  let p be a branching program with edges labelled by the boolean variables, x1,...,xn and their complements. given an input a (a1,...,an) ε {0,1}n, program p computes a function value fp(a) in the following way.  the nodes of p play the role of states or configurations. in particular, sinks play the role of final states or stopping configurations.  the length of program p is the length of the longest path in p. following cobham,2capacity of the program is defined to be the logarithm to the base 2 of the number of nodes in p. length and capacity are lower bounds on time and space requirements for any reasonable model of sequential computation. clearly, any n-variable boolean function can be computed by a branching program of length n if the capacity is not constrained. since space lower bounds in excess of log n remain a fundamental challenge, we consider restricted branching programs in the hope of gaining insight into this problem and the closely related problem of time-space trade-offs.  allan borodin danny dolev faith e. fich wolfgang paul
estimating small cell-loss ratios in atm switches via importance sampling  the cell-loss ratio at a given node in an atm switch, defined as the steady- state fraction of packets of information that are lost at that node due to buffer overflow, is typically a very small quantity that is hard to estimate by simulation. cell losses are rare events, and importance sampling is sometimes the appropriate tool in this situation. however, finding the right change of measure is generally difficult. in this article, importance sampling is applied to estimate the cell-loss ratio in an atm switch modeled as a queuing network that is fed by several sources emitting cells according to a markov-modulated on/off process, and in which all the cells from the same source have the same destination. the charge of measure is obtained via an adaptation of a heuristic proposed by chang et al. {1994} for intree networks. the numerical experiments confirm important efficiency improvements even for large nonintree networks and a large number of sources. experiments with different variants of the importance sampling methodology are also reported, and a number of practical issues are illustrated and discussed.
minimizing capacity violations in a transshipment network  the problem of minimizing capacity violation is a variation of the transshipment problem. it is equivalent to the problem of computing maximum mean surplus cuts which arises in the dual approach to the minimum cost network circulation problem. mccormick and ervolina [15] proposed an algorithm which computes a sequence of cuts with increasing mean surpluses, and stops when an optimal one is found. the mean surplus of this cut is equal to the minimum possible maximum capacity violation. mccormick and ervolina proved that the number of iterations in this algorithm is o(m). one iteration, i.e., finding the subsequent cut, amounts to computing maximum flow in an appropriate network. we prove that the number of iterations in this algorithm is (n). this gives the best known upper bound o(n2m) for the problem. we also show a tight analysis of this algorithm for the case with integral capacities and demands, and present some improvements.  tomasz radzik
sequential random sampling  fast algorithms for selecting a random set of exactly k records from a file of n records are constructed. selection is sequential: the sample records are chosen in the same order in which they occur in the file. all procedures run in o(k) time. the "geometric" method has two versions: with or without o(k) auxiliary space. a further procedure uses hashing techniques and requires o(k) space.  j. h. ahrens u. dieter
forests, frames, and games: algorithms for matroid sums and applications  this paper presents improved algorithms for matroid partitioning problems, such as finding a maximum cardinality set of edges of a graph that can be partitioned into k forests. the notion of a clamp in a matroid sum is introduced. efficient algorithms for problems involving clumps are presented. applications of these algorithms to problems arising in the study of structural rigidity of graphs, the shannon switching game and others are given.  harold gabow herbert westermann
discrete-time optimal control problems with general constraints  this paper presents a computational procedure for solving combined discrete- time optimal control and optimal parameter selection problems subject to general constraints. the approach adopted is to convert the problem into a nonlinear programming problem which can be solved using standard optimization software. the main features of the procedure are the way the controls are parametrized and the conversion of all constraints into a standard form suitable for computation. the software is available commercially as a fortran program dmiser3 together with a companion program miser3 for solving continuous-time problems.  m. e. fisher l. s. jennings
linear expected-time algorithms for connectivity problems (extended abstract)  researchers in recent years have developed many graph algorithms that are fast in the worst case, but little work has been done on graph algorithms that are fast on the average. (exceptions include the work of angluin and valiant [1], karp [7], and schnorr [9].) in this paper we analyze the expected running time of four algorithms for solving graph connectivity problems. our goal is to exhibit algorithms whose expected time is within a constant factor of optimum and to shed light on the properties of random graphs.  in section 2 we develop and analyze a simple algorithm that finds the connected components of an undirected graph with n vertices in o(n) expected time. in sections 3 and 4 we describe algorithms for finding the strong components of a directed graph and the blocks of an undirected graph in o(n) expected time. the time required for these three problems is Ω(m) in the worst case, where m is the number of edges in the graph, since all edges must be examined; but our results show that only o(n) edges must be examined on the average.*@@@@  in section 5 we present an algorithm for finding a minimum weight spanning forest in an undirected graph with edge weights in o(m) expected time.  richard m. karp robert endre tarjan
computing frobenius maps and factoring polynomials  a new probabilistic algorithm for factoring univariate polynomials over finite fields is presented whose asymptotic running time improves upon previous results. to factor a polynomial of degree n over fq, the algorithm uses o((n2 \\+ n log q)•(log n)2 log log n) arithmetic operations in fq. the main technical innovation is a new way to compute frobenius and trace maps in the ring of polynomials modulo the polynomial to be factored.  joachim von zur gathen victor shoup
an improved primal simplex variant for pure processing networks  in processing networks, ordinary network constraints are supplemented by proportional flow restrictions on arcs entering or leaving some nodes. this paper describes a new primal partitioning algorithm for solving pure processing networks using a working basis of variable dimension. in testing against mpsx/370 on a class of randomly generated problems, a fortran implementation of this algorithm was found to be an order-of-magnitude faster. besides indicating the use of our methods in stand-alone fashion, the computational results also demonstrate the desirability of using these methods as a high-level module in a mathematical programming system.  michael d. chang chou-hong j. chen michael engquist
algorithm 650: efficient square root implementation on the 68000  two square root algorithms (for integer and floating point data types) are presented, which aresimpler and more efficient than standard procedures. these could be effectively used as the basis ofhardware-based square root generators as well as for software implementations. one possible appli-cation for an efficient square root routine would be in calculating trigonometric and exponentialfunctions. (this application may be primarily of academic interest, however, since standard tran-scendental function generators would generally be more efficient.) three accompanying mc68000implementations of the algorithm for 32-bit integer and ieee single- and double-precision data areavailable on the calgo listing. these programs return rounding status in the condition code register,and they exhibit the following approximate runtime performance at 8 mhz: 105-134 ps (integer);180-222 ps (single precision); 558-652 ps (double precision).  kenneth c. johnson
designing software for one-dimensional partial differential equations  users of software for solving partial differential equations are often surprised by its inability to formulate their problems.  computer scientists speak of partial differential equations (pdes) as canonical coupled systems, typically in divergence form. physicists, chemists, and engineers start with the same description, but then add real-world things like "rankine-hugoniot" conditions, integro-differential operators, and eulerian (moving) coordinate systems.  this paper describes a generalization of the classical pde formulation that allows users to formulate virtually any pde problem. the extended formulation has been used successfully on a wide range of nontrivial problems in the physical sciences that cannot even be written down in the classical form.  n. l. schryer
algorithm 734; a fortran 90 code for unconstrained nonlinear minimization  this paper describes a fortran 90 implementation of acm transactions on mathematical software algorithm 630, a minimization algorithm designed for use in a limited-memory environment. it includes implementation of the buckley- lenir method, nocedal's limited memory algorithm, and an experimental limited- memory implementation of a factored update due to powell, as well as a fairly standard quasi-newton implementation due originally to shanno. this algorithm uses a number of the new features of fortran 90 to offer capabilities that were not formerly available.  a. g. buckley
parallel implementation of domain decomposition techniques on intel's hypercube  parallel implementation of domain decomposition techniques for elliptic pdes in rectangular regions is considered. this technique is well suited for parallel processing, since in the solution process the subproblems either are independent or can be easily converted into decoupled problems. more than 80% of execution time is spent on solving these independent and decoupled problems.  the hypercube architecture is used for concurrent execution. the performance of the parallel algorithm is compared against the sequential version. the speed-up, efficiency, and communication factors are studied as functions the number of processors. extensive tests are performed to find, for a given mesh size, the number of subregions and nodes that minimize the overall execution time.  m. haghoo w. proskurowski
a fast normal random number generator  a method is presented for generating pseudorandom numbers with a normal distribution. the technique uses the ratio of uniform deviates method discovered by kinderman and monahan with an improved set of bounding curves. an optimized quadratic fit reduces the expected number of logarithm evaluations to 0.012 per normal deviate. the method gives a theoretically correct distribution and can be implemented in 15 lines of fortran. timing and source size comparisons are made with other methods for generating normal deviates. the proposed algorithm compares favorably with some of the better algorithms.  joseph l. leva
higher-dimensional voronoi diagrams in linear expected time  this work is the first to validate theoretically the suspicions of many researchers --- that the "average" voronoi diagram is combinatorially quite simple and can be constructed quickly. specifically, assuming that dimension d is fixed, and that n input points are chosen independently from the uniform distribution on the unit d-ball, it is proved that  the expected number of simplices of the dual of the voronoi diagram is (n) (exact constants are derived for the high-order term), and  a relatively simple algorithm exists for constructing the voronoi diagram in (n) time.  it is likely that the methods developed in the analysis will be applicable to other related quantities and other probability distributions.  r. a. dwyer
a mathematical software environment  several hundred scientists and engineers work at amoco production company's tulsa research center. naturally, scientific computing is an important part of their research in petroleum exploration and production. general purpose mathematical and statistical software is often overlooked when it could be used in place of writing code. our strategy for increasing the awareness and usage of existing software is through advertisement of software via a reusable software catalog, through regular in-house presentations of a mathematical software seminar, and through the development of a mathematical software environment, a collection of programs and procedures created to encourage the use of general purpose mathematical software.  donald l. williams
the design of ma48: a code for the direct solution of sparse unsymmetric linear systems of equations  we describe the design of a new code for the direct solution of sparse unsymmetric linear systems of equations. the new code utilizes a novel restructuring of the symbolic and numerical phases, which increases speed and saves storage without sacrifice of numerical stability. other features include switching to full-matrix processing in all phases of the computation enabling the use of all three levels of blas, treatment of rectangular or rank- deficient matrices, partial factorization, and integrated facilities for iterative refinement and error estimation.  i. s. duff j. k. reid
a variable order runge-kutta method for initial value problems with rapidly varying right-hand sides  explicit runge-kutta methods (rkms) are among the most popular classes of formulas for the approximate numerical integration of nonstiff, initial value problems. however, high-order runge- kutta methods require more function evaluations per integration step than, for example, adams methods used in pece mode, and so, with rkms, it is expecially important to avoid rejected steps. steps are often rejected when certain derivatives of the solutions are very large for part of the region of integration. this corresponds, for example, to regions where the solution has a sharp front or, in the limit, some derivative of the solution is discontinuous. in these circumstances the assumption that the local truncation error is changing slowly is invalid, and so any step- choosing algorithm is likely to produce an unacceptable step. in this paper we derive a family of explicit runge-kutta formulas. each formula is very efficient for problems with smooth solution as well as problems having rapidly varying solutions. each member of this family consists of a fifty-order formula that contains imbedded formulas of all orders 1 through 4. by computing solutions at several different orders, it is possible to detect sharp fronts or discontinuities before all the function evaluations defining the full runge-kutta step have been computed. we can then either accpet a lower order solution or abort the step, depending on which course of action seems appropriate. the efficiency of the new algorithm is demonstrated on the detest test set as well as on some difficult test problems with sharp fronts or discontinuities.  j. r. cash alan h. karp
algorithm 681: intbis, a portable interval newton/bisection package  we present a portable software package for finding all real roots of a system of nonlinear equations within a region defined by bounds on the variables. where practical, the package should find all roots with mathematical certainty. though based on interval newton methods, it is self- contained. it allows various control and output options and does not require programming if the equations are polynomials; it is structured for further algorithmic research. its practicality does not depend in a simple way on the dimension of the system or on the degree of nonlinearity.  r. baker kearfott manuel novoa
remark on algorithm 566  we report the development of second- derivative fortran routines to supplement algorithm 566 developed by j. more et al. (acm trans. math. softw. 7, 14-41, 136-- 140, 1981). algorithm 566 provides function and gradient subroutines of 18 test functions for multivariate minimization. our supplementary hessian segments enable users to test optimization software that requires second derivative information. eigenvalue analysis throughout the minimization is now possible, with the goal of better understanding progress by different minimization algorithms and the relation of progress to eigenvalue distribution and condition number.  victoria z. averbukh samuel figueroa tamar schlick
algorithm 649: a package for computing trigonometric fourier coefficients based on lyness's algorithm  we present a package that allows the computation of the trigonometric fourier coefficients of a smooth function. the function can be provided as a subprogram or as a data list of function values at equally spaced points.  the computational cost of the algorithm does not depend on the required number of fourier coefficients. numerical results of comparative tests with a standard integrator for oscillatory functions are also reported.  g. giunta a. murli
a concurrent neural network algorithm for the traveling salesman problem  a binary neuromorphic data structure is used to encode the n --- city traveling salesman problem (tsp). in this representation the computational complexity, in terms of number of neurons, is reduced from hopfield and tank's (n2) to (n log2 n). a continuous synchronous neural network algorithm in conjunction with the lagrange multiplier, is used to solve the problem. the algorithm has been implemented on the ncube hypercube multiprocessor. this algorithm converges faster and has a higher probability to reach a valid tour than previously available results.  n. toomarian
a logarithmic poisson execution time model for software reliability measurement  a new software reliability model is developed that predicts expected failures (and hence related reliability quantities) as well or better than existing software reliability models, and is simpler than any of the models that approach it in predictive validity. the model incorporates both execution time and calendar time components, each of which is derived. the model is evaluated, using actual data, and compared with other models.  j. d. musa k. okumoto
a revised simplex method with integer q-matrices we describe a modification of the simplex formulas in which q-matrices are used to implement exact computations with an integer multiprecision library. our motivation comes from the need for efficient and exact incremental solvers in the implementation of constraint solving languages such as prolog. we explain how to reformulate the problem and the different steps of the simplex algorithm. we compare some measurements obtained with integer and rational computations. david-olivier azulay jean-françois pique
computing selected eigenvalues of sparse unsymmetric matrices using subspace iteration  this paper discusses the design and development of a code to calculate the eigenvalues of a large sparse real unsymmetric matrix that are the rightmost, leftmost, or are of the largest modulus. a subspace iteration algorithm is used to compute a sequence of sets of vectors that converge to an orthonormal basis for the invariant subspace corresponding to the required eigenvalues. this algorithm is combined with chebychev acceleration if the rightmost or leftmost eigenvalues are sought, or if the eigenvalues of largest modulus are known to be the rightmost or leftmost eigenvalues. an option exists for computing the corresponding eigenvectors. the code does not need the matrix explicitly since it only requires the user to multiply sets of vectors by the matrix. sophisticated and novel iteration controls, stopping criteria, and restart facilities are provided. the code is shown to be efficient and competitive on a range of test problems.  i. s. duff j. a. scott
further results on equivalence and decomposition in queueing network models  this paper addresses three aspects related to the notion of exact equivalence in queueing models.  in many cases the parameters of a system equivalent to a given model involve only a small subset of conditional probabilities of the state of the original model given the equivalent one. it is shown that meaningful bounds may be obtained for the conditional probabilities of interest with little computational effort. such bounds are useful in assessing processing capacities as well as the accuracy of approximate solutions.  as a second point it is shown that the notion of exact equivalence may be easily extended to networks with non-exponential servers. this is done for both the methods of supplementary variables and for the imbedded markov chain technique. qualitative analysis of approximation methods is also discussed.  finally, numerical methods based on the notion of exact equivalence, i.e. operating on conditional probabilities, are considered.  alexandre brandwajn