PhD Proposal: Combinatorial Optimization for Barter Exchange and Tumor Phylogeny Inference

https://umd.zoom.us/j/94659535269?pwd=WPc9MH3hPvaFx0Co4Hxla04ZLoz0J3.1

Abstract:

Combinatorial optimization encompasses many intractable problems with important applications. Nevertheless, important applications demand solutions, be they approximate or exact. In this manuscript we hone in on two such problems. First, a novel centralized barter exchange model where items have different values, and where the goal of the clearinghouse is to find a reallocation of items maximimizing utility, subject to agents being properly compensated for the value they give away. Second, we study tumor phylogeny reconstruction from single-cell sequence data, under the simple assumption that (exceedingly rare) false-positive mutation calls can be ignored. The objective is thus correcting false-negative errors and missing values to obtain a most likely perfect phylogeny (i.e., an evolutionary tree where no mutation is gained more than once and where no mutation is lost). In tackling these two problems, we make heavy use of the flexible paradigm of Combinatorial Optimization via (randomized) Linear Program rounding. We present existing results and propose future research directions.