Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with simplex:
TR05-156 | 13th December 2005
Jonathan A. Kelner, Daniel A. Spielman

A Randomized Polynomial-Time Simplex Algorithm for Linear Programming (Preliminary Version)

We present the first randomized polynomial-time simplex algorithm for linear programming. Like the other known polynomial-time algorithms for linear programming, its running time depends polynomially on the number of bits used to represent its input.

We begin by reducing the input linear program to a special form in which we ... more >>>

TR20-096 | 22nd June 2020
Igor Sergeev

On the asymptotic complexity of sorting

We investigate the number of pairwise comparisons sufficient to sort $n$ elements chosen from a linearly ordered set. This number is shown to be $\log_2(n!) + o(n)$ thus improving over the previously known upper bounds of the form $\log_2(n!) + \Theta(n)$. The new bound is achieved by the proposed group ... more >>>

ISSN 1433-8092 | Imprint