Dennis Amelunxen

  1. Robust Smoothed Analysis of a Condition Number for Linear Programming.

    Authors: Peter Bürgisser, Dennis Amelunxen
    Subjects: Optimization and Control
    Abstract

    We perform a smoothed analysis of the GCC-condition number C(A) of the linear
    programming feasibility problem \exists x\in\R^{m+1} Ax < 0. Suppose that
    \bar{A} is any matrix with rows \bar{a_i} of euclidean norm 1 and,
    independently for all i, let a_i be a random perturbation of \bar{a_i}
    following the uniform distribution in the spherical disk in S^m of angular
    radius \arcsin\sigma and centered at \bar{a_i}. We prove that E(\ln C(A)) =
    O(mn / \sigma).

RSS-материал