Graduate Exam Abstract

Abstract: We present a simple performance bound for the greedy scheme in string optimization problems. Our approach generalizes the family of greedy curvature bounds established by Conforti and Cornuejols (1984). Specifically, we examine three bounds they introduced for evaluating the performance of the greedy scheme in maximizing monotone submodular set functions. We first generalize two of these bounds to string optimization problems in a manner that includes maximizing monotone submodular set functions as a special case. Next, we derive a simpler and more computable bound that applies to a broader class of functions with string domains. We then prove that our bound is superior to two of their bounds and provide a counterexample to show that the third bound is incorrect under the assumptions in Conforti and Cornuejols (1984). We demonstrate our results through two applications. First, we apply our bound to sensor coverage problems with both monotone set and string submodular objective functions. The second application is a social welfare maximization problem involving a monotone non-submodular black-box utility function.

Adviser: Edwin Chong
Co-Adviser: Ali Pezeshki
Non-ECE Member: Haonan Wang
Member 3: Rocky Luo
Addional Members: None

Publications:
None

Program of Study:
Math 501
Math 510
Math 520
Math 617
Math 670
Stat 421
Stat 520
Stat 720