| Speaker: Ademir Hujdurovic Affiliation: University of Primorska Time: 14:00 Wednesday, 20 December, 2017 Location: 303-G14 |
| Motivated by applications in cancer genomics, Hajirasouliha and Raphael in 2014 introduced the minimum conflict-free row split (MCRS) problem: split each row of a given binary matrix into a bitwise OR of a set of rows so that the resulting matrix corresponds to a perfect phylogeny and has the minimum possible number of rows among all matrices with this property. Hajirasouliha and Raphael also proposed the study of a similar problem, in which the task is to minimize the number of distinct rows of the resulting matrix. In this talk, I will present a new formulations of the two problems, showing that the problems are equivalent to two optimization problems on branchings in a derived directed acyclic graph. Building on these formulations, we obtain new results on the two problems, including: (i) a strengthening of the previous heuristic algorithm via a new min-max result in digraphs generalizing Dilworth's theorem, (ii) APX-hardness results for both problems, (iii) approximation algorithms, and (iv) a simple Integer Linear Programming formulations of both problems. This work relates to several well studied notions in combinatorial optimization: chain partitions in partially ordered sets, laminar hypergraphs, and colourings of graphs. This talk is based on a joint work with Edin Husic, Ursa Kacar, Martin Milanic, Bernard Ries, Romeo Rizzi and Alexandru I. Tomescu. |