Linear Programming in O([n3/ln n]L) Operations

K. M Anstreicher

doi:10.1137/S1052623497323194

Back

Linear Programming in O([n3/ln n]L) Operations

Journal article

Peer reviewed

Linear Programming in O([n3/ln n]L) Operations

K. M Anstreicher

SIAM journal on optimization, Vol.9(4), pp.803-812

01/01/1999

DOI: 10.1137/S1052623497323194

View Online

Abstract

We show that the complexity to solve linear programming problems, using standard linear algebra, can be reduced to O([n3/ln n]L) operations, where n is the number of variables in a standard-form problem with integer data of bit size L. Our technique combines partial updating with a preconditioned conjugate gradient method, in a scheme first suggested by Nesterov and Nemirovskii.

Algorithms

Linear algebra

Linear programming

Methods

Details

Title: Subtitle: Linear Programming in O([n3/ln n]L) Operations
Creators: K. M Anstreicher
Resource Type: Journal article
Publication Details: SIAM journal on optimization, Vol.9(4), pp.803-812
Publisher: Society for Industrial and Applied Mathematics
DOI: 10.1137/S1052623497323194
ISSN: 1052-6234
eISSN: 1095-7189
Language: English
Date published: 01/01/1999
Academic Unit: Industrial and Systems Engineering; Computer Science; Business Analytics
Record Identifier: 9984380444402771

Metrics

3 Record Views

74 Times Cited - Web of Science