The Library
Submodular maximization over multiple matroids via generalized exchange properties
Tools
Lee, Jon, Sviridenko, Maxim and Vondrák, Jan (2009) Submodular maximization over multiple matroids via generalized exchange properties. Lecture Notes in Computer Science, Vol.5687 . pp. 244-257. doi:10.1007/978-3-642-03685-9_19 ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/978-3-642-03685-9_19
Abstract
In this paper, we consider the problem of maximizing a non-negative submodular function f, defined on a (finite) ground set N, subject to matroid constraints. A function f:2NR is submodular if for all S, T ⊆ N, f(S ∪ T) + f(S ∩ T) ≤ f(S) + f(T). Furthermore, all submodular functions that we deal with are assumed to be non-negative. Throughout, we assume that our submodular function f is given by a value oracle; i.e., for a given set S ⊆ N, an algorithm can query an oracle to find the value f(S). Without loss of generality, we take the ground set N to be [n] = {1,2,...,n}.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | Lecture Notes in Computer Science | ||||
Publisher: | Springer | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | ||||
Official Date: | 2009 | ||||
Dates: |
|
||||
Volume: | Vol.5687 | ||||
Page Range: | pp. 244-257 | ||||
DOI: | 10.1007/978-3-642-03685-9_19 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |