• DocumentCode
    2170662
  • Title

    Simulated annealing in convex bodies and an O*(n4) volume algorithm

  • Author

    Lovász, Lászlo ; Vempala, Santosh

  • Author_Institution
    Microsoft Res., Redmond, WA, USA
  • fYear
    2003
  • fDate
    11-14 Oct. 2003
  • Firstpage
    650
  • Lastpage
    659
  • Abstract
    We present a new algorithm for computing the volume of a convex body in Rn. The main ingredient of the algorithm is a "morphing" technique that can be viewed as a variant of simulated annealing. Its complexity is O*(n4), improving on the previous best algorithm by a factor of n.
  • Keywords
    computational complexity; computational geometry; randomised algorithms; simulated annealing; complexity; convex bodies; morphing technique; polynomial time; randomized algorithm; simulated annealing; volume computation algorithm; Artificial intelligence; Computational modeling; Engineering profession; Mathematics; Optimization methods; Polynomials; Search methods; Simulated annealing; Space stations; Temperature distribution;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on
  • ISSN
    0272-5428
  • Print_ISBN
    0-7695-2040-5
  • Type

    conf

  • DOI
    10.1109/SFCS.2003.1238237
  • Filename
    1238237
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2170662