Carnegie Mellon University
Browse

On the complexity of computing the diameter of a polytope

Download (1.03 MB)
journal contribution
posted on 1993-01-01, 00:00 authored by Frieze, Shang-Hua Teng
Abstract: "In this paper, some results on the complexity of computing the combinatorial diameter of a polytope are presented. We show that it is D[superscript P]-hard to determine the diameter of a polytope specified by linear inequalities with integer data. Our result partially resolves a long-term open question."

History

Publisher Statement

All Rights Reserved

Date

1993-01-01

Usage metrics

    Categories

    Keywords

    Computational complexity.Polytopes.Linear programming.Mathematical Sciences not elsewhere classified

    Licence

    In Copyright

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC