Show simple item record

dc.contributor.author
Golovin, Daniel
dc.contributor.author
Krause, Andreas
dc.date.accessioned
2017-06-09T18:22:42Z
dc.date.available
2017-06-09T18:22:42Z
dc.date.issued
2011
dc.identifier.uri
http://hdl.handle.net/20.500.11850/44022
dc.description.abstract
Many important problems in discrete optimization require maximization of a monotonic submodular function subject to matroid constraints. For these problems, a simple greedy algorithm is guaranteed to obtain near-optimal solutions. In this article, we extend this classic result to a general class of adaptive optimization problems under partial observability, where each choice can depend on observations resulting from past choices. Specifically, we prove that a natural adaptive greedy algorithm provides a $1/(p+1)$ approximation for the problem of maximizing an adaptive monotone submodular function subject to $p$ matroid constraints, and more generally over arbitrary $p$-independence systems. We illustrate the usefulness of our result on a complex adaptive match-making application.
dc.language.iso
en
dc.publisher
Cornell University
dc.title
Adaptive Submodular Optimization under Matroid Constraints
dc.type
Working Paper
ethz.pages.start
1101.4450v1
ethz.size
5 p.
ethz.publication.place
Ithaca, NY
ethz.publication.status
published
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02661 - Institut für Maschinelles Lernen / Institute for Machine Learning::03908 - Krause, Andreas / Krause, Andreas
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02661 - Institut für Maschinelles Lernen / Institute for Machine Learning::03908 - Krause, Andreas / Krause, Andreas
ethz.date.deposited
2017-06-09T18:22:50Z
ethz.source
ECIT
ethz.identifier.importid
imp59364ed3ca9f719381
ethz.ecitpid
pub:72689
ethz.eth
yes
ethz.availability
Metadata only
ethz.rosetta.installDate
2017-07-18T08:11:11Z
ethz.rosetta.lastUpdated
2018-10-01T15:19:21Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Adaptive%20Submodular%20Optimization%20under%20Matroid%20Constraints&rft.date=2011&rft.spage=1101.4450v1&rft.au=Golovin,%20Daniel&Krause,%20Andreas&rft.genre=preprint&rft.btitle=Adaptive%20Submodular%20Optimization%20under%20Matroid%20Constraints
 Search print copy at ETH Library

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record