Contributed Session Thu.2.H 3013

Thursday, 13:15 - 14:45 h, Room: H 3013

Cluster 2: Combinatorial optimization [...]

Inverse problems


Chair: Peter Gritzmann



Thursday, 13:45 - 14:10 h, Room: H 3013, Talk 2

Daniele Catanzaro
An exact algorithm to reconstruct phylogenetic trees under the minimum evolution criterion

Coauthors: Roberto Aringhieri, Marco Di Summa, Raffaele Pesenti


We investigate one of the most important NP-hard versions of the phylogeny estimation problem, called the Minimum Evolution Problem (MEP). Specifically, we investigate the theoretical foundation of the MEP and its relationships with the Balanced Minimum Evolution Problem. Moreover, we present a new exact approach to solution of the MEP based on a sophisticated combination of both a branch-price-and-cut approach and a non-isomorphic enumeration of all possible phylogenies for a set of n taxa. This peculiar approach allows to break symmetries in the problem and to improve upon the performances of the best-so-far exact algorithm for the MEP. Hopefully, our findings will provide new perspective on the mathematics of the MEP and suggest new directions on the development of future efficient exact approaches to solution of the problem.



Thursday, 14:15 - 14:40 h, Room: H 3013, Talk 3

Peter Gritzmann
On some discrete inverse problems: Combinatorial optimization in discrete and refraction tomography

Coauthors: Andreas Alpers, Barbara Langfeld, Markus Wiegelmann


Discrete Tomography is concerned with the retrieval of finite or finitely presented sets in some Rd from their X-rays in a given finite number of directions.
In the talk we focus on recent results on uniqueness and reconstruction issues.
In particular, we give new conditions on when a subset J of possible positions is already determined by the given data that allow us to settle conjectures of Kuba (1997) and of Brunetti & Daurat (2005).
% (This part of the talk is based on joint work with Barbara Langfeld and Markus Wiegelmann.)
Further, we indicate how new challenges in refraction
tomography relate to issues in computational convexity.
%(Joint work with Andreas Alpers).


  There are three major facts that should be watched out for in all payday loans in the United States. In this section we give only a brief summary recommendation for admission of Cheap Levitra. Full information can be found in the instructions for receiving medications with vardenafil.