Imagen de Portada
Código QR

The Complexity of Zadeh's Pivot Rule

The Simplex algorithm is one of the most important algorithms in discrete optimization, and is the most used algorithm for solving linear programs in practice. In the last 50 years, several pivot rules for this algorithm have been proposed and studied. For most deterministic pivot rules, exponential...

Descripción completa

Autor principal: Alexander Vincent Hopp
Formato: Libro
Publicado: Logos Verlag Berlin 2020
Acceso en línea:Ver este registro en EBSCOhost
fields @attributes:
  recordID: 1
pdfLink:
plink: https://search.ebscohost.com/login.aspx?direct=true&db=nlebk&AN=3541204&site=ehost-live
header:
  @attributes:
    shortDbName: nlebk
    uiTerm: 3541204
    longDbName: eBook Collection (EBSCOhost)
    uiTag: AN
  controlInfo:
    bkinfo:
      btl: The Complexity of Zadeh's Pivot Rule
      aug:
        au: Alexander Vincent Hopp
      isbn: 9783832552060
    imageinfo:
    pubinfo:
      dt:
        @attributes:
          year: 2020
          month: 01
          day: 01
      dtAvail:
        @attributes:
          year: 2023
          month: 04
          day: 17
      pub: Logos Verlag Berlin
      pubContract: Logos Verlag Berlin GmbH
      place: [S.l.]
      price: 0.01
      limitsGroup:
        maxCheckoutDays: 1500
        pda: N
        printPagesOffline: 100
        printPagesOnline: 100
        previewPages: 10000
      prePubGroup:
        dewey:
          @attributes:
            class: 510
            item: 510
        lc:
          @attributes:
            class: Internet Access AEU
            item: In ternet Access AEU
    artinfo:
      ui:
        3541204
        1235833310
      formats:
        fmt:
          @attributes:
            type: EB
            doid: NL$3541204$PDF
            caption: PDF
            download: Y
      tig:
        atl: The Complexity of Zadeh's Pivot Rule
        ptl: The Complexity of Zadeh's Pivot Rule
      aug:
        au: Alexander Vincent Hopp
      su: Mathematics
      sug:
        subj:
          MATHEMATICS / General
          COMPUTERS / Computer Science
          Mathematics
      ab: The Simplex algorithm is one of the most important algorithms in discrete optimization, and is the most used algorithm for solving linear programs in practice. In the last 50 years, several pivot rules for this algorithm have been proposed and studied. For most deterministic pivot rules, exponential lower bounds were found, while a probabilistic pivot rule exists that guarantees termination in expected subexponential time. One deterministic pivot rule that is of special interest is Zadeh's pivot rule since it was the most promising candidate for a polynomial pivot rule for a long time. In 2011, Friedmann proved that this is not true by providing an example forcing the Simplex algorithm to perform at least a subexponential number of iterations in the worst case when using Zadeh's pivot rule. Still, it was not known whether Zadeh's pivot rule might achieve subexponential worst case running time. Next to analyzing Friedmann's construction in detail, we develop the first exponential lower bound for Zadeh's pivot rule. This closes a long-standing open problem by ruling out this pivot rule as a candidate for a deterministic, subexponential pivot rule in several areas of linear optimization and game theory.
      pubtype: eBook
      doctype: Book
      ougenre: Book
    language: English
    copyright:
      @attributes:
        flag: N
      copyrightText:
    holdings:
      @attributes:
        islocal: N