The Stochastic Shortest Path Problem: A polyhedral combinatorics perspective [PDF]
European Journal of Operational Research, 2020 In this paper, we give a new framework for the stochastic shortest path problem in finite state and action spaces. Our framework generalizes both the frameworks proposed by Bertsekas and Tsitsikli and by Bertsekas and Yu. We prove that the problem is well-defined and (weakly) polynomial when (i) there is a way to reach the target state from any initial
Guillot, Matthieu, Stauffer, Gautier
openaire +6 more sources
Polyhedral combinatorics of UPGMA cones
Advances in Applied Mathematics, 2013 Distance-based methods such as UPGMA (Unweighted Pair Group Method with Arithmetic Mean) continue to play a significant role in phylogenetic research. We use polyhedral combinatorics to analyze the natural subdivision of the positive orthant induced by classifying the input vectors according to tree topologies returned by the algorithm.
Davidson, Ruth, Sullivant, Seth
openaire +4 more sources
Polyhedral geometry and combinatorics of an autocatalytic ecosystem
Journal of Mathematical ChemistryDeveloping a mathematical understanding of autocatalysis in reaction networks has both theoretical and practical implications. We review definitions of autocatalytic networks and prove some properties for minimal autocatalytic subnetworks (MASs). We show that it is possible to classify MASs in equivalence classes, and develop mathematical results about
Gagrani, Praful +3 more
openaire +4 more sources
Ricci Curvature on Polyhedral Surfaces via Optimal Transportation
Axioms, 2014 The problem of correctly defining geometric objects, such as the curvature, is a hard one in discrete geometry. In 2009, Ollivier defined a notion of curvature applicable to a wide category of measured metric spaces, in particular to graphs.
Benoît Loisel, Pascal Romon
doaj +1 more source
Multiple sequence alignment with arbitrary gap costs: Computing an optimal solution using polyhedral combinatorics [PDF]
Bioinformatics, 2002 Abstract Multiple sequence alignment is one of the dominant problems in computational molecular biology. Numerous scoring functions and methods have been proposed, most of which result in NP-hard problems. In this paper we propose for the first time a general formulation for multiple alignment with arbitrary gap-costs based on an integer
Althaus, E. +3 more
openaire +3 more sources
Polyhedral combinatorics of bisectors
Advances in GeometryAbstract For any polyhedral norm, the bisector of two points is a polyhedral complex. We study combinatorial aspects of this complex. We investigate the sensitivity of the presence of labelled maximal cells in the bisector relative to the position of the two points.
Jal, Aryaman, Jochemko, Katharina
openaire +2 more sources
Polyhedral combinatorics of the
Discrete Applied Mathematics, 2016 The K-partitioning problem consists in partitioning the vertices of a weighted graph in K sets in order to minimize a function related to the edge weights. We introduce a linear mixed integer formulation with edge variables and representative variables. We investigate the polyhedral combinatorics of the problem, study several families of facet-defining
Alès, Zacharie +2 more
openaire +4 more sources
Discrete Yamabe Problem for Polyhedral Surfaces. [PDF]
Discrete Comput Geom, 2023 Dal Poz Kouřimská H.
europepmc +1 more source
An Invitation to Ehrhart Theory: Polyhedral Geometry and its Applications in Enumerative Combinatorics [PDF]
, 2015 30 pages, 18 ...
openaire +2 more sources
An interaction network approach predicts protein cage architectures in bionanotechnology. [PDF]
Proc Natl Acad Sci U S A, 2023 Fatehi F, Twarock R.
europepmc +1 more source