Article Free Access Share on Approximate polynomial greatest common divisors and nearest singular polynomials Authors: N. Karmarkar Mathematical Sciences Research Center, Bell Laboratories, Murray Hill, NJ Mathematical Sciences Research Center, Bell Laboratories, Murray Hill, NJView Profile , Y. N. Lakshman Department of Mathematics and Computer Science, Drexel University, Philadelphia, PA Department of Mathematics and Computer Science, Drexel University, Philadelphia, PAView Profile Authors Info & Claims ISSAC '96: Proceedings of the 1996 international symposium on Symbolic and algebraic computationOctober 1996Pages 35–39https://doi.org/10.1145/236869.236892Published:01 October 1996Publication History 47citation598DownloadsMetricsTotal Citations47Total Downloads598Last 12 Months44Last 6 weeks8 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

Let A be an $n \times n$ matrix with 0-1 valued entries, and let ${\operatorname{per}}(A)$ be the permanent of A. This paper describes a Monte-Carlo algorithm that produces a “good in the relative sense” estimate of ${\operatorname{per}}(A)$ and has running time ${\operatorname{poly}}(n)2^{{n / 2}} $, where ${\operatorname{poly}}(n)$ denotes a function that grows polynomially with n.

Article A new parallel architecture for sparse matrix computation based on finite projective geometries Share on Author: Narendra Karmarkar AT&T Bell Laboratories, Murray Hill, NJ and Indian Institute of Technology, Bombay, India AT&T Bell Laboratories, Murray Hill, NJ and Indian Institute of Technology, Bombay, IndiaView Profile Authors Info & Claims Supercomputing '91: Proceedings of the 1991 ACM/IEEE conference on SupercomputingAugust 1991 Pages 358–369https://doi.org/10.1145/125826.126029Online:01 August 1991Publication History 10citation887DownloadsMetricsTotal Citations10Total Downloads887Last 12 Months12Last 6 weeks0 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

This paper describes data structures and programming techniques used in an implementation of Karmarkar's algorithm for linear programming. Most of our discussion focuses on applying Gaussian elimination toward the solution of a sequence of sparse symmetric positive definite systems of linear equations, the main requirement in Karmarkar's algorithm. Our approach relies on a direct factorization scheme, with an extensive symbolic factorization step performed in a preparatory stage of the linear programming algorithm. An interpretative version of Gaussian elimination makes use of the symbolic information to perform the actual numerical computations at each iteration of algorithm. We also discuss ordering algorithms that attempt to reduce the amount of fill-in in the LU factors, a procedure to build the linear system solved at each iteration, the use of a dense window data structure in the Gaussian elimination method, a preprocessing procedure designed to increase the sparsity of the linear programming coefficient matrix, and the special treatment of dense columns in the coefficient matrix. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

We present a new polynomial-time algorithm for linear programming. The running-time of this algorithm is O(n3-5L2), as compared to O(n6L2) for the ellipsoid algorithm. We prove that given a polytope P and a strictly interior point a ε P, there is a projective transformation of the space that maps P, a to P', a' having the following property. The ratio of the radius of the smallest sphere with center a', containing P' to the radius of the largest sphere with center a' contained in P' is O (n). The algorithm consists of repeated application of such projective transformations each followed by optimization over an inscribed sphere to create a sequence of points which converges to the optimal solution in polynomial-time.

We analyze the average-case behaviour of the Next-Fit algorithm for bin-packing, and obtain closed-form expressions for distributions of interest. Our analysis is based on a novel technique of partitioning the interval (0, 1) suitably and then formulating the problem as a matrix-differential equation. We compare our analytic results with previously known simulation results and show that there is an excellent agreement between the two. We also explain a certain empirically observed anomaly in the behaviour of the algorithm. Finally we establish that asymptotically perfect packing is possible when input items are drawn from a monotonically decreasing density function.

We present several polynomial-time approximation algorithms for the one-dimensional bin-packing problem. using a subroutine to solve a certain linear programming relaxation of the problem. Our main results are as follows: There is a polynomial-time algorithm A such that A(I) ≤ OPT(I) + O(log2 OPT(I)). There is a polynomial-time algorithm A such that, if m(I) denotes the number of distinct sizes of pieces occurring in instance I, then A(I) ≤ OPT(I) + O(log2 m(I)). There is an approximation scheme which accepts as input an instance I and a positive real number ε, and produces as output a packing using as most (1 + ε) OPT(I) + O(ε-2) bins. Its execution time is O(ε-c n log n), where c is a constant. These are the best asymptotic performance bounds that have been achieved to date for polynomial-time bin-packing. Each of our algorithms makes at most O(log n) calls on the LP relaxation subroutine and takes at most O(n log n) time for other operations. The LP relaxation of bin packing was solved efficiently in practice by Gilmore and Gomory. We prove its membership in P, despite the fact that it has an astronomically large number of variables.