conjecture

Counter Example to A Conjecture on Infeasible Interior-Point Methods

  • G. Gu
  • Cornelis Roos
    • Categories Linear Programming Tags , , ,

    Based on extensive computational evidence (hundreds of thousands of randomly generated problems) the second author conjectured that $\bar{\kappa}(\zeta)=1$, which is a factor of $\sqrt{2n}$ better than that has been proved, and which would yield an $O(\sqrt{n})$ iteration full-Newton step infeasible interior-point algorithm. In this paper we present an example showing that $\bar{\kappa}(\zeta)$ is in the … Read more

    Facet Defining Inequalities among Graph Invariants: the system GraPHedron

  • Hadrien Mélot
    • Categories Graphs and Matroids Tags , , ,

    We present a new computer system, called GraPHedron, which uses a polyhedral approach to help the user to discover optimal conjectures in graph theory. We define what should be optimal conjectures and propose a formal framework allowing to identify them. Here, graphs with n nodes are viewed as points in the Euclidian space, whose coordinates … Read more