Bounding the Greedy Strategy in Finite-Horizon String Optimization

DOI10.1109/CDC.2015.7402826arXiv1503.07511MaRDI QIDQ6260293FDOQ6260293

Authors: Ya-Jing Liu, Edwin K. P. Chong, Ali Pezeshki 

Publication date: 25 March 2015

Abstract: We consider an optimization problem where the decision variable is a string of bounded length. For some time there has been an interest in bounding the performance of the greedy strategy for this problem. Here, we provide weakened sufficient conditions for the greedy strategy to be bounded by a factor of $(1-(1-1/K{)}^K)$, where $K$ is the optimization horizon length. Specifically, we introduce the notions of $K$-submodularity and $K$-GO-concavity, which together are sufficient for this bound to hold. By introducing a notion of emph{curvature} $etain(0,1]$, we prove an even tighter bound with the factor $(1/eta)(1-e^{-eta})$. Finally, we illustrate the strength of our results by considering two example applications. We show that our results provide weaker conditions on parameter values in these applications than in previous results.

This page was built for publication: Bounding the Greedy Strategy in Finite-Horizon String Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6260293)