Submodular function minimization under a submodular set covering constraint

Naoyuki Kamiyama

doi:10.1007/978-3-642-20877-5_14

Submodular function minimization under a submodular set covering constraint

Naoyuki Kamiyama

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

5 Citations (Scopus)

Abstract

In this paper, we consider the problem of minimizing a submodular function under a submodular set covering constraint. We propose an approximation algorithm for this problem by extending the algorithm of Iwata and Nagano [FOCS'09] for the set cover problem with a submodular cost function.

Original language	English
Title of host publication	Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings
Pages	133-141
Number of pages	9
DOIs	https://doi.org/10.1007/978-3-642-20877-5_14
Publication status	Published - 2011
Externally published	Yes
Event	8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011 - Tokyo, Japan Duration: May 23 2011 → May 25 2011

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6648 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011
Country/Territory	Japan
City	Tokyo
Period	5/23/11 → 5/25/11

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-20877-5_14

Cite this

Kamiyama, N. (2011). Submodular function minimization under a submodular set covering constraint. In Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings (pp. 133-141). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6648 LNCS). https://doi.org/10.1007/978-3-642-20877-5_14

Submodular function minimization under a submodular set covering constraint. / Kamiyama, Naoyuki.
Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings. 2011. p. 133-141 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6648 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kamiyama, N 2011, Submodular function minimization under a submodular set covering constraint. in Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6648 LNCS, pp. 133-141, 8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011, Tokyo, Japan, 5/23/11. https://doi.org/10.1007/978-3-642-20877-5_14

Kamiyama N. Submodular function minimization under a submodular set covering constraint. In Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings. 2011. p. 133-141. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-20877-5_14

@inproceedings{be107697b51249419c2f4b0882c427c0,

title = "Submodular function minimization under a submodular set covering constraint",

abstract = "In this paper, we consider the problem of minimizing a submodular function under a submodular set covering constraint. We propose an approximation algorithm for this problem by extending the algorithm of Iwata and Nagano [FOCS'09] for the set cover problem with a submodular cost function.",

author = "Naoyuki Kamiyama",

year = "2011",

doi = "10.1007/978-3-642-20877-5_14",

language = "English",

isbn = "9783642208768",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "133--141",

booktitle = "Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings",

note = "8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011 ; Conference date: 23-05-2011 Through 25-05-2011",

}

TY - GEN

T1 - Submodular function minimization under a submodular set covering constraint

AU - Kamiyama, Naoyuki

PY - 2011

Y1 - 2011

N2 - In this paper, we consider the problem of minimizing a submodular function under a submodular set covering constraint. We propose an approximation algorithm for this problem by extending the algorithm of Iwata and Nagano [FOCS'09] for the set cover problem with a submodular cost function.

AB - In this paper, we consider the problem of minimizing a submodular function under a submodular set covering constraint. We propose an approximation algorithm for this problem by extending the algorithm of Iwata and Nagano [FOCS'09] for the set cover problem with a submodular cost function.

UR - http://www.scopus.com/inward/record.url?scp=79955771902&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79955771902&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-20877-5_14

DO - 10.1007/978-3-642-20877-5_14

M3 - Conference contribution

AN - SCOPUS:79955771902

SN - 9783642208768

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 133

EP - 141

BT - Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings

T2 - 8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011

Y2 - 23 May 2011 through 25 May 2011

ER -

Submodular function minimization under a submodular set covering constraint

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this