Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids Article Swipe

PDF

T-H. Hubert Chan , Zhiyi Huang , Shaofeng H.-C. Jiang , Ning Kang , Zhihao Gavin Tang ·

YOU? · · 2017 · Open Access · · DOI: https://doi.org/10.1137/1.9781611974782.78

We study the online submodular maximization problem with free disposal under a matroid constraint. Elements from some ground set arrive one by one in rounds, and the algorithm maintains a feasible set that is independent in the underlying matroid. In each round when a new element arrives, the algorithm may accept the new element into its feasible set and possibly remove elements from it, provided that the resulting set is still independent. The goal is to maximize the value of the final feasible set under some monotone submodular function, to which the algorithm has oracle access. \n \nFor k-uniform matroids, we give a deterministic algorithm with competitive ratio at least 0.2959, and the ratio approaches 1/α∞ ≈ 0.3178 as k approaches infinity, improving the previous best ratio of 0.25 by Chakrabarti and Kale (IPCO 2014), Buchbinder et al. (SODA 2015) and Chekuri et al. (ICALP 2015). We also show that our algorithm is optimal among a class of deterministic monotone algorithms that accept a new arriving element only if the objective is strictly increased. \n \nFurther, we prove that no deterministic monotone algorithm can be strictly better than 0.25-competitive even for partition matroids, the most modest generalization of k-uniform matroids, matching the competitive ratio by Chakrabarti and Kale (IPCO 2014) and Chekuri et al. (ICALP 2015). Interestingly, we show that randomized algorithms are strictly more powerful by giving a (non-monotone) randomized algorithm for partition matroids with ratio 1/α∞ ≈ 0.3178. \n \nFinally, our techniques can be extended to a more general problem that generalizes both the online sub-modular maximization problem and the online bipartite matching problem with free disposal. Using the techniques developed in this paper, we give constant-competitive algorithms for the submodular online bipartite matching problem.

Related Topics

Expectation–Maximization Algorithm

Mathematical Analysis

Software Engineering

Statistics

Concepts

Matroid Submodular set function Competitive analysis Mathematics Combinatorics Monotone polygon Set function Partition (number theory) Randomized algorithm Oracle Discrete mathematics Maximization Generalization Matching (statistics) Matroid partitioning Approximation algorithm Online algorithm Set (abstract data type) Graphic matroid Mathematical optimization Computer science Upper and lower bounds Geometry Programming language Mathematical analysis Software engineering Statistics

Metadata

Type: preprint
Language: en
Landing Page: https://doi.org/10.1137/1.9781611974782.78
PDF: https://epubs.siam.org/doi/pdf/10.1137/1.9781611974782.78
OA Status: gold
Cited By: 9
References: 21
Related Works: 10
OpenAlex ID: https://openalex.org/W2952790532

All OpenAlex metadata

Raw OpenAlex JSON

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

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.1137/1.9781611974782.78

Digital Object Identifier
Title: Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2017

Year of publication
Publication date: 2017-01-01

Full publication date if available
Authors: T-H. Hubert Chan, Zhiyi Huang, Shaofeng H.-C. Jiang, Ning Kang, Zhihao Gavin Tang

List of authors in order
Landing page: https://doi.org/10.1137/1.9781611974782.78

Publisher landing page
PDF URL: https://epubs.siam.org/doi/pdf/10.1137/1.9781611974782.78

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: gold

Open access status per OpenAlex
OA URL: https://epubs.siam.org/doi/pdf/10.1137/1.9781611974782.78

Direct OA link when available
Concepts: Matroid, Submodular set function, Competitive analysis, Mathematics, Combinatorics, Monotone polygon, Set function, Partition (number theory), Randomized algorithm, Oracle, Discrete mathematics, Maximization, Generalization, Matching (statistics), Matroid partitioning, Approximation algorithm, Online algorithm, Set (abstract data type), Graphic matroid, Mathematical optimization, Computer science, Upper and lower bounds, Geometry, Programming language, Mathematical analysis, Software engineering, Statistics

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

Total citation count in OpenAlex
Citations by year (recent): 2025: 1, 2023: 2, 2021: 2, 2020: 1, 2019: 3

Per-year citation counts (last 5 years)
References (count): 21

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

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W2952790532
doi	https://doi.org/10.1137/1.9781611974782.78
ids.doi	https://doi.org/10.1137/1.9781611974782.78
ids.mag	2952790532
ids.openalex	https://openalex.org/W2952790532
fwci	1.1837067
type	preprint
title	Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids
biblio.issue
biblio.volume
biblio.last_page	1223
biblio.first_page	1204
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.9995999932289124
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.9995999932289124
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/T10237
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9983000159263611
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1702
topics[2].subfield.display_name	Artificial Intelligence
topics[2].display_name	Cryptography and Data Security
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C106286213
concepts[0].level	2
concepts[0].score	0.9348729848861694
concepts[0].wikidata	https://www.wikidata.org/wiki/Q898572
concepts[0].display_name	Matroid
concepts[1].id	https://openalex.org/C178621042
concepts[1].level	2
concepts[1].score	0.9211804270744324
concepts[1].wikidata	https://www.wikidata.org/wiki/Q7631710
concepts[1].display_name	Submodular set function
concepts[2].id	https://openalex.org/C102408133
concepts[2].level	3
concepts[2].score	0.8066805601119995
concepts[2].wikidata	https://www.wikidata.org/wiki/Q5156350
concepts[2].display_name	Competitive analysis
concepts[3].id	https://openalex.org/C33923547
concepts[3].level	0
concepts[3].score	0.6666849851608276
concepts[3].wikidata	https://www.wikidata.org/wiki/Q395
concepts[3].display_name	Mathematics
concepts[4].id	https://openalex.org/C114614502
concepts[4].level	1
concepts[4].score	0.647364616394043
concepts[4].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[4].display_name	Combinatorics
concepts[5].id	https://openalex.org/C2834757
concepts[5].level	2
concepts[5].score	0.617053210735321
concepts[5].wikidata	https://www.wikidata.org/wiki/Q4925424
concepts[5].display_name	Monotone polygon
concepts[6].id	https://openalex.org/C15312841
concepts[6].level	3
concepts[6].score	0.5806295871734619
concepts[6].wikidata	https://www.wikidata.org/wiki/Q1657198
concepts[6].display_name	Set function
concepts[7].id	https://openalex.org/C42812
concepts[7].level	2
concepts[7].score	0.5782386064529419
concepts[7].wikidata	https://www.wikidata.org/wiki/Q1082910
concepts[7].display_name	Partition (number theory)
concepts[8].id	https://openalex.org/C128669082
concepts[8].level	2
concepts[8].score	0.559709370136261
concepts[8].wikidata	https://www.wikidata.org/wiki/Q583461
concepts[8].display_name	Randomized algorithm
concepts[9].id	https://openalex.org/C55166926
concepts[9].level	2
concepts[9].score	0.5529937744140625
concepts[9].wikidata	https://www.wikidata.org/wiki/Q2892946
concepts[9].display_name	Oracle
concepts[10].id	https://openalex.org/C118615104
concepts[10].level	1
concepts[10].score	0.5308324694633484
concepts[10].wikidata	https://www.wikidata.org/wiki/Q121416
concepts[10].display_name	Discrete mathematics
concepts[11].id	https://openalex.org/C2776330181
concepts[11].level	2
concepts[11].score	0.5276480913162231
concepts[11].wikidata	https://www.wikidata.org/wiki/Q18358244
concepts[11].display_name	Maximization
concepts[12].id	https://openalex.org/C177148314
concepts[12].level	2
concepts[12].score	0.452066034078598
concepts[12].wikidata	https://www.wikidata.org/wiki/Q170084
concepts[12].display_name	Generalization
concepts[13].id	https://openalex.org/C165064840
concepts[13].level	2
concepts[13].score	0.4496607184410095
concepts[13].wikidata	https://www.wikidata.org/wiki/Q1321061
concepts[13].display_name	Matching (statistics)
concepts[14].id	https://openalex.org/C22425182
concepts[14].level	4
concepts[14].score	0.41725295782089233
concepts[14].wikidata	https://www.wikidata.org/wiki/Q6787906
concepts[14].display_name	Matroid partitioning
concepts[15].id	https://openalex.org/C148764684
concepts[15].level	2
concepts[15].score	0.4122583866119385
concepts[15].wikidata	https://www.wikidata.org/wiki/Q621751
concepts[15].display_name	Approximation algorithm
concepts[16].id	https://openalex.org/C196921405
concepts[16].level	2
concepts[16].score	0.4120582938194275
concepts[16].wikidata	https://www.wikidata.org/wiki/Q786431
concepts[16].display_name	Online algorithm
concepts[17].id	https://openalex.org/C177264268
concepts[17].level	2
concepts[17].score	0.40464484691619873
concepts[17].wikidata	https://www.wikidata.org/wiki/Q1514741
concepts[17].display_name	Set (abstract data type)
concepts[18].id	https://openalex.org/C111034964
concepts[18].level	3
concepts[18].score	0.34610801935195923
concepts[18].wikidata	https://www.wikidata.org/wiki/Q5597156
concepts[18].display_name	Graphic matroid
concepts[19].id	https://openalex.org/C126255220
concepts[19].level	1
concepts[19].score	0.32324618101119995
concepts[19].wikidata	https://www.wikidata.org/wiki/Q141495
concepts[19].display_name	Mathematical optimization
concepts[20].id	https://openalex.org/C41008148
concepts[20].level	0
concepts[20].score	0.26693689823150635
concepts[20].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[20].display_name	Computer science
concepts[21].id	https://openalex.org/C77553402
concepts[21].level	2
concepts[21].score	0.1639673113822937
concepts[21].wikidata	https://www.wikidata.org/wiki/Q13222579
concepts[21].display_name	Upper and lower bounds
concepts[22].id	https://openalex.org/C2524010
concepts[22].level	1
concepts[22].score	0.0
concepts[22].wikidata	https://www.wikidata.org/wiki/Q8087
concepts[22].display_name	Geometry
concepts[23].id	https://openalex.org/C199360897
concepts[23].level	1
concepts[23].score	0.0
concepts[23].wikidata	https://www.wikidata.org/wiki/Q9143
concepts[23].display_name	Programming language
concepts[24].id	https://openalex.org/C134306372
concepts[24].level	1
concepts[24].score	0.0
concepts[24].wikidata	https://www.wikidata.org/wiki/Q7754
concepts[24].display_name	Mathematical analysis
concepts[25].id	https://openalex.org/C115903868
concepts[25].level	1
concepts[25].score	0.0
concepts[25].wikidata	https://www.wikidata.org/wiki/Q80993
concepts[25].display_name	Software engineering
concepts[26].id	https://openalex.org/C105795698
concepts[26].level	1
concepts[26].score	0.0
concepts[26].wikidata	https://www.wikidata.org/wiki/Q12483
concepts[26].display_name	Statistics
keywords[0].id	https://openalex.org/keywords/matroid
keywords[0].score	0.9348729848861694
keywords[0].display_name	Matroid
keywords[1].id	https://openalex.org/keywords/submodular-set-function
keywords[1].score	0.9211804270744324
keywords[1].display_name	Submodular set function
keywords[2].id	https://openalex.org/keywords/competitive-analysis
keywords[2].score	0.8066805601119995
keywords[2].display_name	Competitive analysis
keywords[3].id	https://openalex.org/keywords/mathematics
keywords[3].score	0.6666849851608276
keywords[3].display_name	Mathematics
keywords[4].id	https://openalex.org/keywords/combinatorics
keywords[4].score	0.647364616394043
keywords[4].display_name	Combinatorics
keywords[5].id	https://openalex.org/keywords/monotone-polygon
keywords[5].score	0.617053210735321
keywords[5].display_name	Monotone polygon
keywords[6].id	https://openalex.org/keywords/set-function
keywords[6].score	0.5806295871734619
keywords[6].display_name	Set function
keywords[7].id	https://openalex.org/keywords/partition
keywords[7].score	0.5782386064529419
keywords[7].display_name	Partition (number theory)
keywords[8].id	https://openalex.org/keywords/randomized-algorithm
keywords[8].score	0.559709370136261
keywords[8].display_name	Randomized algorithm
keywords[9].id	https://openalex.org/keywords/oracle
keywords[9].score	0.5529937744140625
keywords[9].display_name	Oracle
keywords[10].id	https://openalex.org/keywords/discrete-mathematics
keywords[10].score	0.5308324694633484
keywords[10].display_name	Discrete mathematics
keywords[11].id	https://openalex.org/keywords/maximization
keywords[11].score	0.5276480913162231
keywords[11].display_name	Maximization
keywords[12].id	https://openalex.org/keywords/generalization
keywords[12].score	0.452066034078598
keywords[12].display_name	Generalization
keywords[13].id	https://openalex.org/keywords/matching
keywords[13].score	0.4496607184410095
keywords[13].display_name	Matching (statistics)
keywords[14].id	https://openalex.org/keywords/matroid-partitioning
keywords[14].score	0.41725295782089233
keywords[14].display_name	Matroid partitioning
keywords[15].id	https://openalex.org/keywords/approximation-algorithm
keywords[15].score	0.4122583866119385
keywords[15].display_name	Approximation algorithm
keywords[16].id	https://openalex.org/keywords/online-algorithm
keywords[16].score	0.4120582938194275
keywords[16].display_name	Online algorithm
keywords[17].id	https://openalex.org/keywords/set
keywords[17].score	0.40464484691619873
keywords[17].display_name	Set (abstract data type)
keywords[18].id	https://openalex.org/keywords/graphic-matroid
keywords[18].score	0.34610801935195923
keywords[18].display_name	Graphic matroid
keywords[19].id	https://openalex.org/keywords/mathematical-optimization
keywords[19].score	0.32324618101119995
keywords[19].display_name	Mathematical optimization
keywords[20].id	https://openalex.org/keywords/computer-science
keywords[20].score	0.26693689823150635
keywords[20].display_name	Computer science
keywords[21].id	https://openalex.org/keywords/upper-and-lower-bounds
keywords[21].score	0.1639673113822937
keywords[21].display_name	Upper and lower bounds
language	en
locations[0].id	doi:10.1137/1.9781611974782.78
locations[0].is_oa	True
locations[0].source
locations[0].license
locations[0].pdf_url	https://epubs.siam.org/doi/pdf/10.1137/1.9781611974782.78
locations[0].version	publishedVersion
locations[0].raw_type	proceedings-article
locations[0].license_id
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name	Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
locations[0].landing_page_url	https://doi.org/10.1137/1.9781611974782.78
locations[1].id	pmh:oai:hub.hku.hk:10722/241683
locations[1].is_oa	False
locations[1].source.id	https://openalex.org/S4377196271
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	False
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	The HKU Scholars Hub (University of Hong Kong)
locations[1].source.host_organization	https://openalex.org/I889458895
locations[1].source.host_organization_name	University of Hong Kong
locations[1].source.host_organization_lineage	https://openalex.org/I889458895
locations[1].license
locations[1].pdf_url
locations[1].version	submittedVersion
locations[1].raw_type	Conference_Paper
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published	False
locations[1].raw_source_name
locations[1].landing_page_url	http://hdl.handle.net/10722/241683
indexed_in	crossref
authorships[0].author.id	https://openalex.org/A5018708584
authorships[0].author.orcid	https://orcid.org/0000-0002-8340-235X
authorships[0].author.display_name	T-H. Hubert Chan
authorships[0].author_position	first
authorships[0].raw_author_name	T-H. Hubert Chan
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5044562275
authorships[1].author.orcid	https://orcid.org/0000-0003-2963-9556
authorships[1].author.display_name	Zhiyi Huang
authorships[1].author_position	middle
authorships[1].raw_author_name	Zhiyi Huang
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5063670809
authorships[2].author.orcid	https://orcid.org/0000-0001-7972-827X
authorships[2].author.display_name	Shaofeng H.-C. Jiang
authorships[2].author_position	middle
authorships[2].raw_author_name	Shaofeng H.-C Jiang
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5100642732
authorships[3].author.orcid	https://orcid.org/0000-0003-1566-3184
authorships[3].author.display_name	Ning Kang
authorships[3].author_position	middle
authorships[3].raw_author_name	Ning Kang
authorships[3].is_corresponding	False
authorships[4].author.id	https://openalex.org/A5032128738
authorships[4].author.orcid	https://orcid.org/0000-0002-5094-1971
authorships[4].author.display_name	Zhihao Gavin Tang
authorships[4].author_position	last
authorships[4].raw_author_name	Zhihao Gavin Tang
authorships[4].is_corresponding	False
has_content.pdf	True
has_content.grobid_xml	True
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://epubs.siam.org/doi/pdf/10.1137/1.9781611974782.78
open_access.oa_status	gold
open_access.any_repository_has_fulltext	False
created_date	2019-06-27T00:00:00
display_name	Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T03:46:38.306776
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.9995999932289124
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/W2058489697, https://openalex.org/W2980228156, https://openalex.org/W2378157773, https://openalex.org/W4303709689, https://openalex.org/W1978795414, https://openalex.org/W2153065381, https://openalex.org/W4367050287, https://openalex.org/W2106412416, https://openalex.org/W2072414647, https://openalex.org/W2400862597
cited_by_count	9
counts_by_year[0].year	2025
counts_by_year[0].cited_by_count	1
counts_by_year[1].year	2023
counts_by_year[1].cited_by_count	2
counts_by_year[2].year	2021
counts_by_year[2].cited_by_count	2
counts_by_year[3].year	2020
counts_by_year[3].cited_by_count	1
counts_by_year[4].year	2019
counts_by_year[4].cited_by_count	3
locations_count	2
best_oa_location.id	doi:10.1137/1.9781611974782.78
best_oa_location.is_oa	True
best_oa_location.source
best_oa_location.license
best_oa_location.pdf_url	https://epubs.siam.org/doi/pdf/10.1137/1.9781611974782.78
best_oa_location.version	publishedVersion
best_oa_location.raw_type	proceedings-article
best_oa_location.license_id
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name	Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
best_oa_location.landing_page_url	https://doi.org/10.1137/1.9781611974782.78
primary_location.id	doi:10.1137/1.9781611974782.78
primary_location.is_oa	True
primary_location.source
primary_location.license
primary_location.pdf_url	https://epubs.siam.org/doi/pdf/10.1137/1.9781611974782.78
primary_location.version	publishedVersion
primary_location.raw_type	proceedings-article
primary_location.license_id
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name	Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
primary_location.landing_page_url	https://doi.org/10.1137/1.9781611974782.78
publication_date	2017-01-01
publication_year	2017
referenced_works	https://openalex.org/W1966079129, https://openalex.org/W1482405521, https://openalex.org/W2132651631, https://openalex.org/W1771298372, https://openalex.org/W2048837158, https://openalex.org/W2401584318, https://openalex.org/W2143996311, https://openalex.org/W2042873949, https://openalex.org/W2104806240, https://openalex.org/W1770502437, https://openalex.org/W2179494254, https://openalex.org/W1955698431, https://openalex.org/W2054428995, https://openalex.org/W1562932642, https://openalex.org/W2480626043, https://openalex.org/W1536154726, https://openalex.org/W1722931978, https://openalex.org/W1674178071, https://openalex.org/W1816320414, https://openalex.org/W2952981324, https://openalex.org/W1578666690
referenced_works_count	21
abstract_inverted_index.a	11, 29, 43, 100, 153, 161, 224, 242
abstract_inverted_index.k	117
abstract_inverted_index.In	39
abstract_inverted_index.We	0, 144
abstract_inverted_index.as	116
abstract_inverted_index.at	106
abstract_inverted_index.be	180, 239
abstract_inverted_index.by	21, 127, 200, 222
abstract_inverted_index.et	134, 140, 208
abstract_inverted_index.if	166
abstract_inverted_index.in	23, 35, 267
abstract_inverted_index.is	33, 69, 74, 150, 169
abstract_inverted_index.no	175
abstract_inverted_index.of	79, 125, 155, 193
abstract_inverted_index.to	75, 89, 241
abstract_inverted_index.we	98, 172, 213, 270
abstract_inverted_index.The	72
abstract_inverted_index.al.	135, 141, 209
abstract_inverted_index.and	25, 58, 109, 129, 138, 202, 206, 254
abstract_inverted_index.are	218
abstract_inverted_index.can	179, 238
abstract_inverted_index.for	186, 228, 274
abstract_inverted_index.has	93
abstract_inverted_index.it,	63
abstract_inverted_index.its	55
abstract_inverted_index.may	49
abstract_inverted_index.new	44, 52, 162
abstract_inverted_index.one	20, 22
abstract_inverted_index.our	148, 236
abstract_inverted_index.set	18, 31, 57, 68, 83
abstract_inverted_index.the	2, 26, 36, 47, 51, 66, 77, 80, 91, 110, 121, 167, 189, 197, 249, 255, 264, 275
abstract_inverted_index.≈	114, 234
abstract_inverted_index.0.25	126
abstract_inverted_index.Kale	130, 203
abstract_inverted_index.also	145
abstract_inverted_index.best	123
abstract_inverted_index.both	248
abstract_inverted_index.each	40
abstract_inverted_index.even	185
abstract_inverted_index.free	8, 261
abstract_inverted_index.from	15, 62
abstract_inverted_index.give	99, 271
abstract_inverted_index.goal	73
abstract_inverted_index.into	54
abstract_inverted_index.more	220, 243
abstract_inverted_index.most	190
abstract_inverted_index.only	165
abstract_inverted_index.show	146, 214
abstract_inverted_index.some	16, 85
abstract_inverted_index.than	183
abstract_inverted_index.that	32, 65, 147, 159, 174, 215, 246
abstract_inverted_index.this	268
abstract_inverted_index.when	42
abstract_inverted_index.with	7, 103, 231, 260
abstract_inverted_index.(IPCO	131, 204
abstract_inverted_index.(SODA	136
abstract_inverted_index.2014)	205
abstract_inverted_index.2015)	137
abstract_inverted_index.Using	263
abstract_inverted_index.among	152
abstract_inverted_index.class	154
abstract_inverted_index.final	81
abstract_inverted_index.least	107
abstract_inverted_index.prove	173
abstract_inverted_index.ratio	105, 111, 124, 199, 232
abstract_inverted_index.round	41
abstract_inverted_index.still	70
abstract_inverted_index.study	1
abstract_inverted_index.under	10, 84
abstract_inverted_index.value	78
abstract_inverted_index.which	90
abstract_inverted_index.(ICALP	142, 210
abstract_inverted_index.0.3178	115
abstract_inverted_index.2014),	132
abstract_inverted_index.2015).	143, 211
abstract_inverted_index.accept	50, 160
abstract_inverted_index.arrive	19
abstract_inverted_index.better	182
abstract_inverted_index.giving	223
abstract_inverted_index.ground	17
abstract_inverted_index.modest	191
abstract_inverted_index.online	3, 250, 256, 277
abstract_inverted_index.oracle	94
abstract_inverted_index.paper,	269
abstract_inverted_index.remove	60
abstract_inverted_index.0.2959,	108
abstract_inverted_index.1/α∞	113, 233
abstract_inverted_index.Chekuri	139, 207
abstract_inverted_index.element	45, 53, 164
abstract_inverted_index.general	244
abstract_inverted_index.matroid	12
abstract_inverted_index.optimal	151
abstract_inverted_index.problem	6, 245, 253, 259
abstract_inverted_index.rounds,	24
abstract_inverted_index.Elements	14
abstract_inverted_index.arrives,	46
abstract_inverted_index.arriving	163
abstract_inverted_index.disposal	9
abstract_inverted_index.elements	61
abstract_inverted_index.extended	240
abstract_inverted_index.feasible	30, 56, 82
abstract_inverted_index.matching	196, 258, 279
abstract_inverted_index.matroid.	38
abstract_inverted_index.matroids	230
abstract_inverted_index.maximize	76
abstract_inverted_index.monotone	86, 157, 177
abstract_inverted_index.possibly	59
abstract_inverted_index.powerful	221
abstract_inverted_index.previous	122
abstract_inverted_index.problem.	280
abstract_inverted_index.provided	64
abstract_inverted_index.strictly	170, 181, 219
abstract_inverted_index.algorithm	27, 48, 92, 102, 149, 178, 227
abstract_inverted_index.bipartite	257, 278
abstract_inverted_index.developed	266
abstract_inverted_index.disposal.	262
abstract_inverted_index.function,	88
abstract_inverted_index.improving	120
abstract_inverted_index.infinity,	119
abstract_inverted_index.k-uniform	96, 194
abstract_inverted_index.maintains	28
abstract_inverted_index.matroids,	97, 188, 195
abstract_inverted_index.objective	168
abstract_inverted_index.partition	187, 229
abstract_inverted_index.resulting	67
abstract_inverted_index.Buchbinder	133
abstract_inverted_index.algorithms	158, 217, 273
abstract_inverted_index.approaches	112, 118
abstract_inverted_index.randomized	216, 226
abstract_inverted_index.submodular	4, 87, 276
abstract_inverted_index.techniques	237, 265
abstract_inverted_index.underlying	37
abstract_inverted_index.Chakrabarti	128, 201
abstract_inverted_index.competitive	104, 198
abstract_inverted_index.constraint.	13
abstract_inverted_index.generalizes	247
abstract_inverted_index.independent	34
abstract_inverted_index.sub-modular	251
abstract_inverted_index.independent.	71
abstract_inverted_index.maximization	5, 252
abstract_inverted_index.deterministic	101, 156, 176
abstract_inverted_index.(non-monotone)	225
abstract_inverted_index.Interestingly,	212
abstract_inverted_index.generalization	192
abstract_inverted_index.0.25-competitive	184
abstract_inverted_index.constant-competitive	272
abstract_inverted_index.access. \n \nFor	95
abstract_inverted_index.0.3178. \n \nFinally,	235
abstract_inverted_index.increased. \n \nFurther,	171
cited_by_percentile_year.max	97
cited_by_percentile_year.min	89
countries_distinct_count	0
institutions_distinct_count	5
citation_normalized_percentile.value	0.79137056
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	False