Submodular Optimization Problems and Greedy Strategies: A Survey Article Swipe

PDF

Yajing Liu , Edwin K. P. Chong , Ali Pezeshki , Zhenliang Zhang ·

YOU? · · 2019 · Open Access · · DOI: https://doi.org/10.48550/arxiv.1905.03308

The greedy strategy is an approximation algorithm to solve optimization problems arising in decision making with multiple actions. How good is the greedy strategy compared to the optimal solution? In this survey, we mainly consider two classes of optimization problems where the objective function is submodular. The first is set submodular optimization, which is to choose a set of actions to optimize a set submodular objective function, and the second is string submodular optimization, which is to choose an ordered set of actions to optimize a string submodular function. Our emphasis here is on performance bounds for the greedy strategy in submodular optimization problems. Specifically, we review performance bounds for the greedy strategy, more general and improved bounds in terms of curvature, performance bounds for the batched greedy strategy, and performance bounds for Nash equilibria.

Related Topics

Concepts

Submodular set function Greedy algorithm Set function Set (abstract data type) Mathematical optimization String (physics) Optimization problem Function (biology) Mathematics Computer science Mathematical physics Evolutionary biology Programming language Biology

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/1905.03308
PDF: https://arxiv.org/pdf/1905.03308
OA Status: green
References: 67
Related Works: 10
OpenAlex ID: https://openalex.org/W2944632132

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W2944632132

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.1905.03308

Digital Object Identifier
Title: Submodular Optimization Problems and Greedy Strategies: A Survey

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2019

Year of publication
Publication date: 2019-05-08

Full publication date if available
Authors: Yajing Liu, Edwin K. P. Chong, Ali Pezeshki, Zhenliang Zhang

List of authors in order
Landing page: https://arxiv.org/abs/1905.03308

Publisher landing page
PDF URL: https://arxiv.org/pdf/1905.03308

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/1905.03308

Direct OA link when available
Concepts: Submodular set function, Greedy algorithm, Set function, Set (abstract data type), Mathematical optimization, String (physics), Optimization problem, Function (biology), Mathematics, Computer science, Mathematical physics, Evolutionary biology, Programming language, Biology

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
References (count): 67

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W2944632132
doi	https://doi.org/10.48550/arxiv.1905.03308
ids.doi	https://doi.org/10.48550/arxiv.1905.03308
ids.mag	2944632132
ids.openalex	https://openalex.org/W2944632132
fwci
type	preprint
title	Submodular Optimization Problems and Greedy Strategies: A Survey
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T10720
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9998999834060669
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1703
topics[0].subfield.display_name	Computational Theory and Mathematics
topics[0].display_name	Complexity and Algorithms in Graphs
topics[1].id	https://openalex.org/T12288
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9976000189781189
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1705
topics[1].subfield.display_name	Computer Networks and Communications
topics[1].display_name	Optimization and Search Problems
topics[2].id	https://openalex.org/T10374
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9901999831199646
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1703
topics[2].subfield.display_name	Computational Theory and Mathematics
topics[2].display_name	Advanced Graph Theory Research
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C178621042
concepts[0].level	2
concepts[0].score	0.9887862205505371
concepts[0].wikidata	https://www.wikidata.org/wiki/Q7631710
concepts[0].display_name	Submodular set function
concepts[1].id	https://openalex.org/C51823790
concepts[1].level	2
concepts[1].score	0.7596962451934814
concepts[1].wikidata	https://www.wikidata.org/wiki/Q504353
concepts[1].display_name	Greedy algorithm
concepts[2].id	https://openalex.org/C15312841
concepts[2].level	3
concepts[2].score	0.6728613376617432
concepts[2].wikidata	https://www.wikidata.org/wiki/Q1657198
concepts[2].display_name	Set function
concepts[3].id	https://openalex.org/C177264268
concepts[3].level	2
concepts[3].score	0.6234530210494995
concepts[3].wikidata	https://www.wikidata.org/wiki/Q1514741
concepts[3].display_name	Set (abstract data type)
concepts[4].id	https://openalex.org/C126255220
concepts[4].level	1
concepts[4].score	0.6116144061088562
concepts[4].wikidata	https://www.wikidata.org/wiki/Q141495
concepts[4].display_name	Mathematical optimization
concepts[5].id	https://openalex.org/C157486923
concepts[5].level	2
concepts[5].score	0.5506236553192139
concepts[5].wikidata	https://www.wikidata.org/wiki/Q1376436
concepts[5].display_name	String (physics)
concepts[6].id	https://openalex.org/C137836250
concepts[6].level	2
concepts[6].score	0.5338678359985352
concepts[6].wikidata	https://www.wikidata.org/wiki/Q984063
concepts[6].display_name	Optimization problem
concepts[7].id	https://openalex.org/C14036430
concepts[7].level	2
concepts[7].score	0.464322030544281
concepts[7].wikidata	https://www.wikidata.org/wiki/Q3736076
concepts[7].display_name	Function (biology)
concepts[8].id	https://openalex.org/C33923547
concepts[8].level	0
concepts[8].score	0.44890257716178894
concepts[8].wikidata	https://www.wikidata.org/wiki/Q395
concepts[8].display_name	Mathematics
concepts[9].id	https://openalex.org/C41008148
concepts[9].level	0
concepts[9].score	0.44665735960006714
concepts[9].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[9].display_name	Computer science
concepts[10].id	https://openalex.org/C37914503
concepts[10].level	1
concepts[10].score	0.0
concepts[10].wikidata	https://www.wikidata.org/wiki/Q156495
concepts[10].display_name	Mathematical physics
concepts[11].id	https://openalex.org/C78458016
concepts[11].level	1
concepts[11].score	0.0
concepts[11].wikidata	https://www.wikidata.org/wiki/Q840400
concepts[11].display_name	Evolutionary biology
concepts[12].id	https://openalex.org/C199360897
concepts[12].level	1
concepts[12].score	0.0
concepts[12].wikidata	https://www.wikidata.org/wiki/Q9143
concepts[12].display_name	Programming language
concepts[13].id	https://openalex.org/C86803240
concepts[13].level	0
concepts[13].score	0.0
concepts[13].wikidata	https://www.wikidata.org/wiki/Q420
concepts[13].display_name	Biology
keywords[0].id	https://openalex.org/keywords/submodular-set-function
keywords[0].score	0.9887862205505371
keywords[0].display_name	Submodular set function
keywords[1].id	https://openalex.org/keywords/greedy-algorithm
keywords[1].score	0.7596962451934814
keywords[1].display_name	Greedy algorithm
keywords[2].id	https://openalex.org/keywords/set-function
keywords[2].score	0.6728613376617432
keywords[2].display_name	Set function
keywords[3].id	https://openalex.org/keywords/set
keywords[3].score	0.6234530210494995
keywords[3].display_name	Set (abstract data type)
keywords[4].id	https://openalex.org/keywords/mathematical-optimization
keywords[4].score	0.6116144061088562
keywords[4].display_name	Mathematical optimization
keywords[5].id	https://openalex.org/keywords/string
keywords[5].score	0.5506236553192139
keywords[5].display_name	String (physics)
keywords[6].id	https://openalex.org/keywords/optimization-problem
keywords[6].score	0.5338678359985352
keywords[6].display_name	Optimization problem
keywords[7].id	https://openalex.org/keywords/function
keywords[7].score	0.464322030544281
keywords[7].display_name	Function (biology)
keywords[8].id	https://openalex.org/keywords/mathematics
keywords[8].score	0.44890257716178894
keywords[8].display_name	Mathematics
keywords[9].id	https://openalex.org/keywords/computer-science
keywords[9].score	0.44665735960006714
keywords[9].display_name	Computer science
language	en
locations[0].id	pmh:oai:arXiv.org:1905.03308
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/1905.03308
locations[0].version	submittedVersion
locations[0].raw_type
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/1905.03308
locations[1].id	doi:10.48550/arxiv.1905.03308
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.1905.03308
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5100629029
authorships[0].author.orcid	https://orcid.org/0000-0001-5467-5976
authorships[0].author.display_name	Yajing Liu
authorships[0].countries	US
authorships[0].affiliations[0].institution_ids	https://openalex.org/I1297288678
authorships[0].affiliations[0].raw_affiliation_string	National Renewable energy laboratory
authorships[0].institutions[0].id	https://openalex.org/I1297288678
authorships[0].institutions[0].ror	https://ror.org/036266993
authorships[0].institutions[0].type	facility
authorships[0].institutions[0].lineage	https://openalex.org/I1297288678, https://openalex.org/I1330989302, https://openalex.org/I2800842121
authorships[0].institutions[0].country_code	US
authorships[0].institutions[0].display_name	National Renewable Energy Laboratory
authorships[0].author_position	first
authorships[0].raw_author_name	Yajing Liu
authorships[0].is_corresponding	False
authorships[0].raw_affiliation_strings	National Renewable energy laboratory
authorships[1].author.id	https://openalex.org/A5070385137
authorships[1].author.orcid	https://orcid.org/0000-0002-7622-4815
authorships[1].author.display_name	Edwin K. P. Chong
authorships[1].countries	US
authorships[1].affiliations[0].institution_ids	https://openalex.org/I92446798
authorships[1].affiliations[0].raw_affiliation_string	Colorado State University
authorships[1].institutions[0].id	https://openalex.org/I92446798
authorships[1].institutions[0].ror	https://ror.org/03k1gpj17
authorships[1].institutions[0].type	education
authorships[1].institutions[0].lineage	https://openalex.org/I92446798
authorships[1].institutions[0].country_code	US
authorships[1].institutions[0].display_name	Colorado State University
authorships[1].author_position	middle
authorships[1].raw_author_name	Edwin K. P. Chong
authorships[1].is_corresponding	False
authorships[1].raw_affiliation_strings	Colorado State University
authorships[2].author.id	https://openalex.org/A5028995727
authorships[2].author.orcid	https://orcid.org/0000-0002-7142-5685
authorships[2].author.display_name	Ali Pezeshki
authorships[2].countries	US
authorships[2].affiliations[0].institution_ids	https://openalex.org/I92446798
authorships[2].affiliations[0].raw_affiliation_string	Colorado State University
authorships[2].institutions[0].id	https://openalex.org/I92446798
authorships[2].institutions[0].ror	https://ror.org/03k1gpj17
authorships[2].institutions[0].type	education
authorships[2].institutions[0].lineage	https://openalex.org/I92446798
authorships[2].institutions[0].country_code	US
authorships[2].institutions[0].display_name	Colorado State University
authorships[2].author_position	middle
authorships[2].raw_author_name	Ali Pezeshki
authorships[2].is_corresponding	False
authorships[2].raw_affiliation_strings	Colorado State University
authorships[3].author.id	https://openalex.org/A5061318346
authorships[3].author.orcid	https://orcid.org/0000-0002-3620-7228
authorships[3].author.display_name	Zhenliang Zhang
authorships[3].countries	US
authorships[3].affiliations[0].institution_ids	https://openalex.org/I4210095624
authorships[3].affiliations[0].raw_affiliation_string	alibaba group
authorships[3].institutions[0].id	https://openalex.org/I4210095624
authorships[3].institutions[0].ror	https://ror.org/00rn0m335
authorships[3].institutions[0].type	company
authorships[3].institutions[0].lineage	https://openalex.org/I4210095624, https://openalex.org/I45928872
authorships[3].institutions[0].country_code	US
authorships[3].institutions[0].display_name	Alibaba Group (United States)
authorships[3].author_position	last
authorships[3].raw_author_name	Zhenliang Zhang
authorships[3].is_corresponding	False
authorships[3].raw_affiliation_strings	alibaba group
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/1905.03308
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Submodular Optimization Problems and Greedy Strategies: A Survey
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T10720
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9998999834060669
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1703
primary_topic.subfield.display_name	Computational Theory and Mathematics
primary_topic.display_name	Complexity and Algorithms in Graphs
related_works	https://openalex.org/W4313349761, https://openalex.org/W2963719189, https://openalex.org/W2963059222, https://openalex.org/W2901206941, https://openalex.org/W2968699064, https://openalex.org/W4300407000, https://openalex.org/W2964314169, https://openalex.org/W2735578456, https://openalex.org/W4312724132, https://openalex.org/W4296167846
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:1905.03308
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/1905.03308
best_oa_location.version	submittedVersion
best_oa_location.raw_type
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/1905.03308
primary_location.id	pmh:oai:arXiv.org:1905.03308
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/1905.03308
primary_location.version	submittedVersion
primary_location.raw_type
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/1905.03308
publication_date	2019-05-08
publication_year	2019
referenced_works	https://openalex.org/W2889243215, https://openalex.org/W2040114800, https://openalex.org/W2605341677, https://openalex.org/W3104299892, https://openalex.org/W2033885045, https://openalex.org/W2038888321, https://openalex.org/W2962744701, https://openalex.org/W2179494254, https://openalex.org/W2144933361, https://openalex.org/W2963012133, https://openalex.org/W1966079129, https://openalex.org/W1601081659, https://openalex.org/W1498671329, https://openalex.org/W2964123308, https://openalex.org/W2330024298, https://openalex.org/W2108203093, https://openalex.org/W2162765276, https://openalex.org/W1971161781, https://openalex.org/W3104333431, https://openalex.org/W1967800450, https://openalex.org/W1989453388, https://openalex.org/W2121671791, https://openalex.org/W2020927880, https://openalex.org/W1973315504, https://openalex.org/W2472207966, https://openalex.org/W2011193572, https://openalex.org/W123178497, https://openalex.org/W2911981421, https://openalex.org/W2258857078, https://openalex.org/W2098432798, https://openalex.org/W1515891729, https://openalex.org/W2066767736, https://openalex.org/W2166588237, https://openalex.org/W2084562801, https://openalex.org/W2118362147, https://openalex.org/W1977557143, https://openalex.org/W2080379754, https://openalex.org/W1991528957, https://openalex.org/W2949203029, https://openalex.org/W2500139799, https://openalex.org/W2109015671, https://openalex.org/W1993536641, https://openalex.org/W1279320161, https://openalex.org/W2621717961, https://openalex.org/W2158760370, https://openalex.org/W3103262232, https://openalex.org/W2109974898, https://openalex.org/W2964139335, https://openalex.org/W2962795549, https://openalex.org/W2131824593, https://openalex.org/W3008838497, https://openalex.org/W2962747165, https://openalex.org/W2092765469, https://openalex.org/W2080169294, https://openalex.org/W1997959284, https://openalex.org/W60525624, https://openalex.org/W2053853578, https://openalex.org/W2091165295, https://openalex.org/W1985123706, https://openalex.org/W2086917808, https://openalex.org/W2263717697, https://openalex.org/W2741807132, https://openalex.org/W1680189815, https://openalex.org/W2045492898, https://openalex.org/W2050000782, https://openalex.org/W2146416675, https://openalex.org/W2014369282
referenced_works_count	67
abstract_inverted_index.a	56, 62, 85
abstract_inverted_index.In	29
abstract_inverted_index.an	4, 78
abstract_inverted_index.in	12, 100, 118
abstract_inverted_index.is	3, 20, 44, 48, 53, 70, 75, 92
abstract_inverted_index.of	37, 58, 81, 120
abstract_inverted_index.on	93
abstract_inverted_index.to	7, 25, 54, 60, 76, 83
abstract_inverted_index.we	32, 105
abstract_inverted_index.How	18
abstract_inverted_index.Our	89
abstract_inverted_index.The	0, 46
abstract_inverted_index.and	67, 115, 129
abstract_inverted_index.for	96, 109, 124, 132
abstract_inverted_index.set	49, 57, 63, 80
abstract_inverted_index.the	21, 26, 41, 68, 97, 110, 125
abstract_inverted_index.two	35
abstract_inverted_index.Nash	133
abstract_inverted_index.good	19
abstract_inverted_index.here	91
abstract_inverted_index.more	113
abstract_inverted_index.this	30
abstract_inverted_index.with	15
abstract_inverted_index.first	47
abstract_inverted_index.solve	8
abstract_inverted_index.terms	119
abstract_inverted_index.where	40
abstract_inverted_index.which	52, 74
abstract_inverted_index.bounds	95, 108, 117, 123, 131
abstract_inverted_index.choose	55, 77
abstract_inverted_index.greedy	1, 22, 98, 111, 127
abstract_inverted_index.mainly	33
abstract_inverted_index.making	14
abstract_inverted_index.review	106
abstract_inverted_index.second	69
abstract_inverted_index.string	71, 86
abstract_inverted_index.actions	59, 82
abstract_inverted_index.arising	11
abstract_inverted_index.batched	126
abstract_inverted_index.classes	36
abstract_inverted_index.general	114
abstract_inverted_index.optimal	27
abstract_inverted_index.ordered	79
abstract_inverted_index.survey,	31
abstract_inverted_index.actions.	17
abstract_inverted_index.compared	24
abstract_inverted_index.consider	34
abstract_inverted_index.decision	13
abstract_inverted_index.emphasis	90
abstract_inverted_index.function	43
abstract_inverted_index.improved	116
abstract_inverted_index.multiple	16
abstract_inverted_index.optimize	61, 84
abstract_inverted_index.problems	10, 39
abstract_inverted_index.strategy	2, 23, 99
abstract_inverted_index.algorithm	6
abstract_inverted_index.function,	66
abstract_inverted_index.function.	88
abstract_inverted_index.objective	42, 65
abstract_inverted_index.problems.	103
abstract_inverted_index.solution?	28
abstract_inverted_index.strategy,	112, 128
abstract_inverted_index.curvature,	121
abstract_inverted_index.submodular	50, 64, 72, 87, 101
abstract_inverted_index.equilibria.	134
abstract_inverted_index.performance	94, 107, 122, 130
abstract_inverted_index.submodular.	45
abstract_inverted_index.optimization	9, 38, 102
abstract_inverted_index.Specifically,	104
abstract_inverted_index.approximation	5
abstract_inverted_index.optimization,	51, 73
cited_by_percentile_year
countries_distinct_count	1
institutions_distinct_count	4
sustainable_development_goals[0].id	https://metadata.un.org/sdg/16
sustainable_development_goals[0].score	0.800000011920929
sustainable_development_goals[0].display_name	Peace, Justice and strong institutions
citation_normalized_percentile