direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

Ehemalige Mitarbeiter

Dr. Dennis Amelunxen

Lupe

Kontakt
City University of Hong Kong
Department of Mathematics
G6613 (Green Zone), 6/F Academic 1
Tat Chee Avenue, Kowloon Tong, Hong Kong
 
Persönliche Homepage
sites.google.com/site/dennisamelunxen/home

Publikationen in der Arbeitsgruppe

Robust Smoothed Analysis of a Condition Number for Linear Programming
Citation key BA-Robust-Smoothed-Analysis-Of-A-Condition-Number-For-Linear-Programming
Author Peter Bürgisser and Dennis Amelunxen
Pages 221-251
Year 2012
ISSN 0025-5610
DOI 10.1007/s10107-010-0346-x
Journal Mathematical Programming
Volume 131
Number 1-2, Ser. A
Abstract We perform a smoothed analysis of the GCC-condition number $C(A)$ of the linear programming feasibility problem $\exists x\in\mathbb R^m+1 Ax < 0$. Suppose that $\barA$ is any matrix with rows $\bara_i$ of euclidean norm $1$ and, independently for all $i$, let $a_i$ be a random perturbation of $\bara_i$ following the uniform distribution in the spherical disk in $S^m$ of angular radius $\arcsin\sigma$ and centered at $\bara_i$. We prove that $E(łn C(A)) = O(mn / \sigma)$. A similar result was shown for Renegar's condition number and Gaussian perturbations by Dunagan, Spielman, and Teng [arXiv:cs.DS/0302011]. Our result is robust in the sense that it easily extends to radially symmetric probability distributions supported on a spherical disk of radius $\arcsin\sigma$, whose density may even have a singularity at the center of the perturbation. Our proofs combine ideas from a recent paper of Bürgisser, Cucker, and Lotz (Math. Comp. 77, No. 263, 2008) with techniques of Dunagan et al.
Link to publication Link to original publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.