PhD Proposal: Combinatorial Optimization for Barter Exchange and Tumor Phylogeny Inference
Juan Luque Chang
Monday, November 11, 2024, 11:00 am-12:30 pm 
Abstract
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.
Bio
Juan is a PhD student at the University of Maryland, advised by Professor Srinivasan. His research interests lie in Combinatorial Optimization and its applications. Juan is also a Data Science for Social Good Fellow. He holds a Math B.S. from UMBC, where he was a Sherman Scholar.
This talk is organized by Migo Gui