A Performance Bound for the Greedy Algorithm in a Generalized Class of String Optimization Problems
We present a simple performance bound for the greedy scheme in string optimization problems that obtains strong results. Our approach vastly generalizes the group of previously established greedy curvature bounds by Conforti and Cornu\'{e}jols (1984). We consider three constants, $\alpha_G$, $\alpha_G'$, and $\alpha_G''$ introduced by Conforti and Cornu\'{e}jols (1984), that are used in performance bounds of greedy schemes in submodular set optimization. We first generalize both of the $\alpha_G$ and $\alpha_G''$ bounds to string optimization problems in a manner that includes maximizing submodular set functions over matroids as a special case. We then derive a much simpler and computable bound that allows for applications to a far more general class of functions with string domains. We prove that our bound is superior to both the $\alpha_G$ and $\alpha_G''$ bounds and provide a counterexample to show that the $\alpha_G'$ bound is incorrect under the assumptions in Conforti and Cornu\'{e}jols (1984). We conclude with two applications. The first is an application of our result to sensor coverage problems. We demonstrate our performance bound in cases where the objective function is set submodular and string submodular. The second is an application to a social welfare maximization problem with black-box utility functions.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Scalable Greedy Feature Selection via Weak Submodularity
Greedy algorithms are widely used for problems in machine learning such as feature selection and set function optimization. Unfortunately, for large datasets, the running time of even greedy algorithms can be quite high.…
feature selectionNon-submodular Function Maximization subject to a Matroid Constraint, with Applications
The standard greedy algorithm has been recently shown to enjoy approximation guarantees for constrained non-submodular nondecreasing set function maximization. While these recent results allow to better characterize the …
Point ProcessesPure Planning to Pure Policies and In Between with a Recursive Tree Planner
A recursive tree planner (RTP) is designed to function as a pure planner without policies at one extreme and run a pure greedy policy at the other. In between, the RTP exploits policies to improve planning performance an…
MuJoCoGeneralized Policy Elimination: an efficient algorithm for Nonparametric Contextual Bandits
We propose the Generalized Policy Elimination (GPE) algorithm, an oracle-efficient contextual bandit (CB) algorithm inspired by the Policy Elimination algorithm of \cite{dudik2011}. We prove the first regret optimality g…
Multi-Armed BanditsGeneralized Boosting
Boosting is a widely used learning technique in machine learning for solving classification problems. In boosting, one predicts the label of an example using an ensemble of weak classifiers. While boosting has shown trem…
Additive modelsClassificationGeneral Classificationimage-classification+1