waashk/acm huggingface dataset:
expanders, sorting in rounds and superconcentrators of limited depth  expanding graphs and superconcentrators are relevant to theoretical computer science in several ways. here we use finite geometries to construct explicitly highly expanding graphs with essentially the smallest possible number of edges.  our graphs enable us to improve significantly previous results on a parallel sorting problem, by describing an explicit algorithm to sort n elements in k time units using (nαk) processors, where, e.g., α2 = 7/4.  using our graphs we can also construct efficient n-superconcentrators of limited depth. for example, we construct an n superconcentrator of depth 3 with (n4/3) edges; better than the previous known results.  n alon
algorithm 798: high-dimensional interpolation using the modified shepard method  a new implementation of the modified quadratic shepard method for the interpolation of scattered data is presented. qshep5d is a c++ translation of the original fortran 77 program qshep3d developed by renka (for 2d and 3d interpolation) which has been upgraded for 5d interpolation. this software development was motivated by the need for interpolated 5d hypervolumes of environmental response variables produced by forest growth and production models.  michael w. berry karen s. minser
error estimation in automatic quadrature routines  a new algorithm for estimating the error in quadrature approximations is presented. based on the same integrand evaluations that we need for approximating the integral, one may, for many quadrature rules, compute a sequence of null rule approximations. these null rule approximations are then used to produce an estimate of the local error. the algorithm allows us to take advantage of the degree of precision of the basic quadrature rule. in the experiments we show that the algorithm works satisfactorily for a selection of different quadrature rules on all test families of integrals.  jarle berntsen terje o. espelid
learning stochastic functions by smooth simultaneous estimation  to learn, it suffices to estimate the error of all candidate hypotheses simultaneously. we study the problem of when this "simultaneous estimation" is possible and show that it leads to new learning procedures and weaker sufficient conditions for a broad class of learning problems. we modify the standard probably approximately correct (pac) setup to allow concepts that are "stochastic functions." a deterministic function maps a set x into a set y, whereas a stochastic function is a probability distribution on x x y. we approach the simultaenous estimation problem by concentrating on a subset of all estimators, those that satisfy a natural "smoothness" constraint. the common empirical estimator falls within this class. we show that smooth simultaneous estimability can be characterized by a sampling-based criterion. also, we describe a canonical estimator for this class of problems. this canonical estimator has a unique form: it uses part of the samples to select a finite subset of hypotheses that approximates the class of candidate hypotheses, and then it uses the rest of the samples to estimate the error of each hypothesis in the subset. finally, we show that a learning procedure based on the canonical estimator will work in every case where empirical error minimization does.  kevin l. buescher p. r. kumar
algorithm 720; an algorithm for adaptive cubature over a collection of 3-dimensional simplices  an adaptive algorithm for computing an approximation to the integral of each element in a vector of functions over a 3-dimensional region covered by simplices is presented. the algorithm is encoded in fortran 77.  locally, a cubature formula of degree 8 with 43 points is used to approximate an integral. the local error estimate is based on the same evaluation points. the error estimation procedure tries to decide whether the approximation for each function has asymptotic behavior, and different actions are taken depending on that decision.  the simplex with the largest error is subdivided into 8 simplices. the local procedure is then applied to each new region. this procedure is repeated until convergence.  jarle berntsen ronald cools terje o. espelid
a linear-time heuristic for improving network partitions  an iterative mincut heuristic for partitioning networks is presented whose worst case computation time, per pass, grows linearly with the size of the network. in practice, only a very small number of passes are typically needed, leading to a fast approximation algorithm for mincut partitioning. to deal with cells of various sizes, the algorithm progresses by moving one cell at a time between the blocks of the partition while maintaining a desired balance based on the size of the blocks rather than the number of cells per block. efficient data structures are used to avoid unnecessary searching for the best cell to move and to minimize unnecessary updating of cells affected by each move.  c. m. fiduccia r. m. mattheyses
a factorization algorithm for linear ordinary differential equations  the reducibility and factorization of linear homogeneous differential equations are of great theoretical and practical importance in mathematics. although it has been known for a long time that factorization is in principle a decision procedure, its use in an automatic differential equation solver requires a more detailed analysis of the various steps involved. especially important are certain auxiliary equations, the so-called associated equations. an upper bound for the degree of its coefficients is derived. another important ingredient is the computation of optimal estimates for the size of polynomial and rational solutions of certain differential equations with rational coefficients. applying these results, the design of the factorization algorithm lodef and its implementation in the scratchpad ii computer algebra system is described.  f. schwarz
line search algorithms with guaranteed sufficient decrease  the development of software for minimization problems is often based on a line search method. we consider line search methods that satisfy sufficient decrease and curvature conditions, and formulate the problem of determining a point that satisfies these two conditions in terms of finding a point in a set t(μ). we describe a search algorithm for this problem that produces a sequence of iterates that converge to a point in t(μ) and that, except for pathological cases, terminates in a finite number of steps. numerical results for an implementation of the search algorithm on a set of test functions show that the algorithm terminates within a small number of iterations.  jorge j. more david j. thuente
exact solution of large-scale, asymmetric traveling salesman problems  a lowest-first, branch-and-bound algorithm for the asymmetric traveling salesman problem is presented. the method is based on the assignment problem relaxation and on a subtour elimination branching scheme. the effectiveness of the algorithm derives from reduction procedures and parametric solution of the relaxed problems associated with the nodes of the branch-decision tree. large- size, uniformly, randomly generated instances of complete digraphs with up to 2000 vertices are solved on a decstation 5000/240 computer in less than 3 minutes of cpu time. in addition, we solved on a pc 486/33 no wait flow shop problems with up to 1000 jobs in less than 11 minutes and real-world stacker crane problems with up to 443 movements in less than 6 seconds.  g. carpaneto m. dell'amico p. toth
a rejection technique for sampling from log-concave multivariate distributions  different universal methods (also called automatic or black-box methods) have been suggested for sampling form univariate log-concave distributions. the descriptioon of a suitable universal generator for multivariate distributions in arbitrary dimensions has not been published up to now. the new algorithm is based on the method of transformed density rejection. to construct a hat function for the rejection algorithm the multivariate density is transformed by a proper transformation t into a concave function (in the case of log- concave density t(x) = log(x).) then it is possible to construct a dominating function by taking the minimum of serveral tangent hyperplanes that are transformed back by t-1 into the original scale. the domains of different pieces of the hat function are polyhedra in the multivariate case. although this method can be shown to work, it is too slow and complicated in higher dimensions. in this article we split the  rn into simple cones. the hat function is constructed piecewise on each of the cones by tangent hyperplanes. the resulting function is no longer continuous and the rejection constant is bounded from below but the setup and the generation remains quite fast in higher dimensions; for example, n = 8. the article describes the details of how this main idea can be used to construct algorithm tdrmv that generates random tuples from a multivariate log-concave distribution with a computable density. although the developed algorithm is not a real black box method it is adjustable for a large class of log-concave densities.  josef leydold
algorithm 744; a stochastic algorithm for global optimization with constraints  a stochastic algorithm is presented for finding the global optimum of a function of n variables subject to general constraints. the algorithm is intended for moderate values of n, but it can accommodate objective and constraint functions that are discontinuous and can take advantage of parallel processors. the performance of this algorithm is compared to that of the nelder-mead simplex algorithm and a simulated annealing algorithm on a variety of nonlinear functions. in addition, one-, two-, four-, and eight-processor versions of the algorithm are compared using 64 of the nonlinear problems with constraints collected by hock and schittkowski. in general, the algorithm is more robust than the simplex algorithm, but computationally more expensive. the algorithm appears to be as robust as the simulated annealing algorithm, but computationally cheaper. issues discussed include algorithm speed and robustness, applicability to both computer and mathematical models, and parallel efficiency.  f. michael rabinowitz
the initial transient problem - estimating transient and steady state performance  in this paper, deutsch, richards and fernandez-torres (1983) fit relaxed time series (rarma) models to transient and steady state data from a simulated m/m/1 queue and a nonstationary queueing network. both systems are initially empty and idle. the statistical identification procedure (richards 1983) for the rarma model class is illustrated. improved estimates of the steady state mean of the m/m/1, and of the polynominal in time of the network's nonstationary "steady state" performance, are obtained by including the identified transient model in the rarma regression.  s. j. deutsch j. e. richards c. fernandez-torres
on the sojourn time distribution in a finite capacity processor shared queue  we consider a processor shared m/m/1 queue that can accommodate atmost a finite number k of customers. using singular perturbation techniques,we construct asymptotic approximations to the distribution of acustomer's sojourn time. we assume that k is large and treat several different cases of themodel parameters and also treat different time scales. extensivenumerical comparisons are used to back up our asymptotic formulas.  \\---author's abstract charles knessl
bootstrap confidence intervals for ratios of expectations  we are concerned with computing a confidence interval for the ratio e&amp;l; t;/italic>[y]/e[& lt;italic>x, where (x,y) is a pair of random variables. this ratio estimation problem arises in, for instance, regenerative simulation. as an alternative to confidence intervals based on asymptotic normality, we study and compare different variants of the bootstrap for one-sided and two-sided intervals. we point out situations where these techniques provide confidence intervals with coverage much closer to the nominal value than do the classical methods.  denis choquet pierre l 'ecuyer christian leger
algorithm 642: a fast procedure for calculating minimum cross-validation cubic smoothing splines  the procedure cubgcv is an implementation of a recently developed algorithm for fast o(n) calculation of a cubic smoothing spline fitted to n noisy data points, with the degree of smoothing chosen to minimize the expected mean square error at the data points when the variance of the error associated with the data is known, or, to minimize the generalized cross validation (gcv) when the variance of the error associated with the data is unknown. the data may be unequally spaced and nonuniformly weighted. the algorithm exploits the banded structure of the matrices associated with the cubic smoothing spline problem. bayesian point error estimates are also calculated in o(n) operations.  m. f. hutchinson
twisted gfsr generators ii  the twisted gfsr generators proposed in a previous article have a defect in k-distribution for k larger than the order of recurrence. in this follow up article, we introduce and analyze a new tgfsr variant having better k-distribution property. we provide an efficient algorithm to obtain the order of equidistribution, together with a tight upper bound on the order. we discuss a method to search for generators attaining this bound, and we list some of these such generators. the upper bound turns out to be (sometimes far) less than the maximum order of equidistribution for a generator of that period length, but far more than that for a gfsr with a working are of the same size.  makoto matsumoto yoshiharu kurita
algorithm 666: chabis: a mathematical software package for locating and evaluating roots of systems of nonlinear equations  chabis is a mathematical software package for the numerical solution of a system of n nonlinear equations in n variables. first, chabis locates at least one solution of the system within an n-dimensional polyhedron. then, it applies a new generalized method of bisection to this n-polyhedron in order to obtain an approximate solution of the system according to a predetermined accuracy. in this paper we briefly describe the user interface to chabis and present several details of its implementation, as well as an example of its usage.  michael n. vrahatis
algorithm 651: algorithm hfft - high-order fast-direct solution of the helmholtz equation  hfft is a software package for solving the helmholtz equation on bounded two- and three-dimensional rectangular domains with dirichlet, neumann, or periodic boundary conditions. the software is the result of combining new fourth-order accurate compact finite difference (hodie) discretizations and a fast-direct solution technique (the fourier method). in this paper we briefly describe the user interface to hfft and present an example of its usage and several details of its implementation.  ronald f. boisvert
on the number of eularian orientations of a graph  we give efficient randomized schemes to sample and approximately count eulerian orientations of any eulerian graph. eulerian orientations are natural flow-like structures, and welsh has pointed out that computing their number (i)corresponds to evaluating the tutte polynomial at the point (0, --2) [8,19] and (ii) is equivalent to evaluating "ice-type partition functions" in statistical physics [20].  our algorithms are based on a reduction to sampling and approximately counting perfect matchings for a class of graphs for which the methods of broder [3, 10] and others [4, 6] apply. a crucial step of the reduction is the "monotonicity lemma" (lemma 3.3) which is of independent combinatorial interest. roughly speaking, the monotonicity lemma establishes the intuitive fact that "increasing the number of constraints applied on a flow problem can only decrease the number of solutions". in turn, the proof of the lemma involves a new decomposition technique which decouples problematically overlapping structures (a recurrent obstacle in handling large combinatorial populations) and allows detailed enumeration arguments. as a byproduct, (i) we exhibit a class of graphs for which perfect and near-perfect matchings are polynomially related, and hence the permanent can be approximated, for reasons other than "short augmenting paths" (previously the only known approach); and (ii) we obtain a further direct sampling scheme for eulerian orientations which is faster than the one suggested by the reduction to perfect matchings.  finally, with respect to our approximate counting algorithm, we give the complementary hardness result, namely, that counting exactly eulerian orientations is #p-complete, and provide some connections with eulerian tours.  milena mihail peter winkler
fitting johnson curves to univariate and multivariate data  moment matching and percentile matching are the standard methods for fitting a distribution from johnson's translation system (the sl, s u, s b, and s n families) to a univariate data set (johnson and kotz 1970). one method for fitting a multivariate johnson distribution to a vector-valued data set is to: (a) fit each marginal distribution separately with a univariate johnson distribution; and then (b) fit a multivariate normal distribution to the transformed vectors using the sample correlation coefficients between the transformed coordinates. to make this approach numerically feasible, wilson (1983) implemented an interactive percentile matching algorithm based on a modified newton-raphson procedure. when the algorithm was applied to 80 trivariate data sets arising in a large-scale policy analysis project, excessive manual intervention was required in some situations to obtain acceptable fits (martin 1983).  james r. wilson
a statistical model for net length estimation  the prerouting estimation of net length is very important to the physical design since the estimated length can be employed as a figure-of-merit of the placement process, as an evaluation of the placement result, and in the calculation of capacitance in the predictive timing analysis. the traditional methods, bounded rectangle method, minimal spanning tree method and minimal steiner tree method, result in either poor estimation or time consuming processing. moreover, they do not consider the interference between each net and the technology influence. a statistical model for net length estimation has been developed to overcome these deficiencies. this model provides an unbiased estimate with 7 percent relative root-mean-squares error on an average.  lai-chering suen
on the number of halving planes  let s r3 be an n-set in general position. a plane containing three of the points is called a halving plane if it dissects s into two parts of equal cardinality. it is proved that the number of halving planes is at most  (n2 .998).  as a main tool, for every set y of n points in the plane a set n of size  n4) is constructed such that the points of n are distributed almost evenly in the triangles determined by y.  i. barany z. furedi l. lovasz
optimization in a distributed processing environment using genetic algorithms with multivariate crossover  we set out to demonstrate the effectiveness of distributed genetic algorithms using multivariate crossover in optimizing a function of a sizable number of independent variables. our results show that this algorithm has unique potential in optimizing such functions. the multivariate crossover meta- strategy, however, did not result in a singularly better performance of the algorithm than did simpler crossover strategies.  aaron h. konstam stephen j. hartley william l. carr
algorithm 644: a portable package for bessel functions of a complex argument and nonnegative order  this algorithm is a package of subroutines for computing bessel functions hv&amp;l; t;/italic>(1)(zhv(2)(z), iv(z), jv(z), kv(z), yv(z) and airy functions ai(z), ai′(z), bi(z), bi′(z) for ordersv≥0 and complex z in πz≤π. eight callable subroutines and their double-precision counterparts are provided. exponential scaling and sequence generation are auxiliary options.  d. e. amos
how to vectorize the algebraic multilevel iteration  we consider the algebraic multilevel iteration (amli) for the solution of systems of linear equations as they arise form a finite-difference discretization on a rectangular grid. key operation is the matrix-vector product, which can efficiently be executed on vector and parallel-vector computer architectures if the nonzero entries of the matrix are concentrated in a few diagonals. in order to maintain this structure for all matrices on all levels coarsening in alternating directions is used. in some cases it is necessary to introduce additional dummy grid hyperplanes. the data movements in the restriction and prolongation are crucial, as they produce massive memory conflicts on vector architectures. by using a simple performance model the best of the possible vectorization strategies is automatically selected at runtime. examples show that on a fujitsu vpp300 the presented implementation of amli reaches about 85% of the useful performance, and scalability with respect to computing time can be achieved.  lutz grosz
approximation algorithms for shortest path motion planning  this paper gives approximation algorithms of solving the following motion planning problem: given a set of polyhedral obstacles and points s and t, find a shortest path from s to t that avoids the obstacles. the paths found by the algorithms are piecewise linear, and the length of a path is the sum of the lengths of the line segments making up the path. approximation algorithms will be given for versions of this problem in the plane and in three- dimensional space. the algorithms return an ε-short path, that is, a path with length within (1 + ε) of shortest. let n be the total number of faces of the polyhedral obstacles, and ε a given value satisfying  < ε ≤ π. the algorithm for the planar case requires  (n log n)/ε time to build a data structure of size  ( ;n/ε). given points s and t, and ε-short path from s to t can be found with the use of the data structure in time  (< italic>n/ε \\+ n log n). the data structure is associated with a new variety of voronoi diagram. given obstacles s 3 and points s, t ε e3, an ε-short path between s and t can be found in  (nλ(n) log(/ε)/&amp;am; p;#949;4 \\+ n2 lognp log(n logp)) time, where p is the ratio of the length of the longest obstacle edge to the distance between s to t. the function λ(n) = α(n) (α(n) (1)), where the α(n) is a form of inverse of ackermann's function. for log(1/ε) and log p that are (log n), this bound is  (log n2(n)λ(n ;)/ε4).  k. clarkson
a review of recent developments in solving odes  mathematical models when simulating the behavior of physical, chemical, and biological systems often include one or more ordinary differential equations (odes). to study the system behavior predicted by a model, these equations are usually solved numerically.  although many of the current methods for solving odes were developed around the turn of the century, the past 15 years or so has been a period of intensive research. the emphasis of this survey is on the methods and techniques used in software for solving odes.  odes can be classified as stiff or nonstiff, and may be stiff for some parts of an interval and nonstiff for others. we discuss stiff equations, why they are difficult to solve, and methods and software for solving both nonstiff and stiff equations. we conclude this review by looking at techniques for dealing with special problems that may arise in some odes, for example, discontinuities.  although important theoretical developments have also taken place, we report only those developments which have directly affected the software and provide a review of this research. we present the basic concepts involved but assume that the reader has some background in numerical computing, such as a first course in numerical methods.  gopal k. gupta ron sacks-davis peter e. tescher