An Improved Greedy Curvature Bound in Finite-Horizon String Optimization with Application to a Sensor Coverage Problem Article Swipe
Brandon Van Over
,
Bowen Li
,
Edwin K. P. Chong
,
Ali Pezeshki
·
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2308.15758
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2308.15758
We study the optimization problem of choosing strings of finite length to maximize string submodular functions on string matroids, which is a broader class of problems than maximizing set submodular functions on set matroids. We provide a lower bound for the performance of the greedy algorithm in our problem, and then prove that our bound is superior to the greedy curvature bound of Conforti and Cornuejols. Our bound has lower computational complexity than most previously proposed curvature bounds. Finally, we demonstrate the strength of our result on a sensor coverage problem.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2308.15758
- https://arxiv.org/pdf/2308.15758
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4386348054
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4386348054Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2308.15758Digital Object Identifier
- Title
-
An Improved Greedy Curvature Bound in Finite-Horizon String Optimization with Application to a Sensor Coverage ProblemWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2023Year of publication
- Publication date
-
2023-08-30Full publication date if available
- Authors
-
Brandon Van Over, Bowen Li, Edwin K. P. Chong, Ali PezeshkiList of authors in order
- Landing page
-
https://arxiv.org/abs/2308.15758Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2308.15758Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2308.15758Direct OA link when available
- Concepts
-
Matroid, Submodular set function, String (physics), Greedy algorithm, Upper and lower bounds, Curvature, Mathematics, Set (abstract data type), Finite set, Combinatorics, Mathematical optimization, Computer science, Geometry, Mathematical analysis, Mathematical physics, Programming languageTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4386348054 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2308.15758 |
| ids.doi | https://doi.org/10.48550/arxiv.2308.15758 |
| ids.openalex | https://openalex.org/W4386348054 |
| fwci | |
| type | preprint |
| title | An Improved Greedy Curvature Bound in Finite-Horizon String Optimization with Application to a Sensor Coverage Problem |
| 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.9925000071525574 |
| 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/T10237 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9635999798774719 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1702 |
| topics[1].subfield.display_name | Artificial Intelligence |
| topics[1].display_name | Cryptography and Data Security |
| topics[2].id | https://openalex.org/T11269 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9524000287055969 |
| 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 | Algorithms and Data Compression |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C106286213 |
| concepts[0].level | 2 |
| concepts[0].score | 0.9111825227737427 |
| 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.8815487623214722 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q7631710 |
| concepts[1].display_name | Submodular set function |
| concepts[2].id | https://openalex.org/C157486923 |
| concepts[2].level | 2 |
| concepts[2].score | 0.6968708634376526 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q1376436 |
| concepts[2].display_name | String (physics) |
| concepts[3].id | https://openalex.org/C51823790 |
| concepts[3].level | 2 |
| concepts[3].score | 0.682549774646759 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q504353 |
| concepts[3].display_name | Greedy algorithm |
| concepts[4].id | https://openalex.org/C77553402 |
| concepts[4].level | 2 |
| concepts[4].score | 0.6517876386642456 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q13222579 |
| concepts[4].display_name | Upper and lower bounds |
| concepts[5].id | https://openalex.org/C195065555 |
| concepts[5].level | 2 |
| concepts[5].score | 0.58873051404953 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q214881 |
| concepts[5].display_name | Curvature |
| concepts[6].id | https://openalex.org/C33923547 |
| concepts[6].level | 0 |
| concepts[6].score | 0.5566952228546143 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[6].display_name | Mathematics |
| concepts[7].id | https://openalex.org/C177264268 |
| concepts[7].level | 2 |
| concepts[7].score | 0.509515106678009 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q1514741 |
| concepts[7].display_name | Set (abstract data type) |
| concepts[8].id | https://openalex.org/C162392398 |
| concepts[8].level | 2 |
| concepts[8].score | 0.426803320646286 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q272404 |
| concepts[8].display_name | Finite set |
| concepts[9].id | https://openalex.org/C114614502 |
| concepts[9].level | 1 |
| concepts[9].score | 0.4251406490802765 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[9].display_name | Combinatorics |
| concepts[10].id | https://openalex.org/C126255220 |
| concepts[10].level | 1 |
| concepts[10].score | 0.34302273392677307 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[10].display_name | Mathematical optimization |
| concepts[11].id | https://openalex.org/C41008148 |
| concepts[11].level | 0 |
| concepts[11].score | 0.2519535422325134 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[11].display_name | Computer science |
| concepts[12].id | https://openalex.org/C2524010 |
| concepts[12].level | 1 |
| concepts[12].score | 0.07766759395599365 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q8087 |
| concepts[12].display_name | Geometry |
| concepts[13].id | https://openalex.org/C134306372 |
| concepts[13].level | 1 |
| concepts[13].score | 0.07339927554130554 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[13].display_name | Mathematical analysis |
| concepts[14].id | https://openalex.org/C37914503 |
| concepts[14].level | 1 |
| concepts[14].score | 0.0 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q156495 |
| concepts[14].display_name | Mathematical physics |
| concepts[15].id | https://openalex.org/C199360897 |
| concepts[15].level | 1 |
| concepts[15].score | 0.0 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q9143 |
| concepts[15].display_name | Programming language |
| keywords[0].id | https://openalex.org/keywords/matroid |
| keywords[0].score | 0.9111825227737427 |
| keywords[0].display_name | Matroid |
| keywords[1].id | https://openalex.org/keywords/submodular-set-function |
| keywords[1].score | 0.8815487623214722 |
| keywords[1].display_name | Submodular set function |
| keywords[2].id | https://openalex.org/keywords/string |
| keywords[2].score | 0.6968708634376526 |
| keywords[2].display_name | String (physics) |
| keywords[3].id | https://openalex.org/keywords/greedy-algorithm |
| keywords[3].score | 0.682549774646759 |
| keywords[3].display_name | Greedy algorithm |
| keywords[4].id | https://openalex.org/keywords/upper-and-lower-bounds |
| keywords[4].score | 0.6517876386642456 |
| keywords[4].display_name | Upper and lower bounds |
| keywords[5].id | https://openalex.org/keywords/curvature |
| keywords[5].score | 0.58873051404953 |
| keywords[5].display_name | Curvature |
| keywords[6].id | https://openalex.org/keywords/mathematics |
| keywords[6].score | 0.5566952228546143 |
| keywords[6].display_name | Mathematics |
| keywords[7].id | https://openalex.org/keywords/set |
| keywords[7].score | 0.509515106678009 |
| keywords[7].display_name | Set (abstract data type) |
| keywords[8].id | https://openalex.org/keywords/finite-set |
| keywords[8].score | 0.426803320646286 |
| keywords[8].display_name | Finite set |
| keywords[9].id | https://openalex.org/keywords/combinatorics |
| keywords[9].score | 0.4251406490802765 |
| keywords[9].display_name | Combinatorics |
| keywords[10].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[10].score | 0.34302273392677307 |
| keywords[10].display_name | Mathematical optimization |
| keywords[11].id | https://openalex.org/keywords/computer-science |
| keywords[11].score | 0.2519535422325134 |
| keywords[11].display_name | Computer science |
| keywords[12].id | https://openalex.org/keywords/geometry |
| keywords[12].score | 0.07766759395599365 |
| keywords[12].display_name | Geometry |
| keywords[13].id | https://openalex.org/keywords/mathematical-analysis |
| keywords[13].score | 0.07339927554130554 |
| keywords[13].display_name | Mathematical analysis |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2308.15758 |
| 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 | cc-by |
| locations[0].pdf_url | https://arxiv.org/pdf/2308.15758 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | https://openalex.org/licenses/cc-by |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2308.15758 |
| locations[1].id | doi:10.48550/arxiv.2308.15758 |
| 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 | cc-by |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | https://openalex.org/licenses/cc-by |
| 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.2308.15758 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5008464915 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Brandon Van Over |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Van Over, Brandon |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5100387262 |
| authorships[1].author.orcid | https://orcid.org/0000-0001-7525-9672 |
| authorships[1].author.display_name | Bowen Li |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Li, Bowen |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5070385137 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-7622-4815 |
| authorships[2].author.display_name | Edwin K. P. Chong |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Chong, Edwin K. P. |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5028995727 |
| authorships[3].author.orcid | https://orcid.org/0000-0002-7142-5685 |
| authorships[3].author.display_name | Ali Pezeshki |
| authorships[3].author_position | last |
| authorships[3].raw_author_name | Pezeshki, Ali |
| authorships[3].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://arxiv.org/pdf/2308.15758 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2023-09-02T00:00:00 |
| display_name | An Improved Greedy Curvature Bound in Finite-Horizon String Optimization with Application to a Sensor Coverage Problem |
| 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.9925000071525574 |
| 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/W4320232260, https://openalex.org/W4252399622, https://openalex.org/W1499990180, https://openalex.org/W4241672388, https://openalex.org/W2352672974, https://openalex.org/W2402949237, https://openalex.org/W2964314169, https://openalex.org/W2594118609, https://openalex.org/W2765425000, https://openalex.org/W3204684126 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2308.15758 |
| 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 | cc-by |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2308.15758 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by |
| 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/2308.15758 |
| primary_location.id | pmh:oai:arXiv.org:2308.15758 |
| 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 | cc-by |
| primary_location.pdf_url | https://arxiv.org/pdf/2308.15758 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | https://openalex.org/licenses/cc-by |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2308.15758 |
| publication_date | 2023-08-30 |
| publication_year | 2023 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 21, 36, 87 |
| abstract_inverted_index.We | 0, 34 |
| abstract_inverted_index.in | 46 |
| abstract_inverted_index.is | 20, 55 |
| abstract_inverted_index.of | 5, 8, 24, 42, 62, 83 |
| abstract_inverted_index.on | 16, 31, 86 |
| abstract_inverted_index.to | 11, 57 |
| abstract_inverted_index.we | 79 |
| abstract_inverted_index.Our | 66 |
| abstract_inverted_index.and | 49, 64 |
| abstract_inverted_index.for | 39 |
| abstract_inverted_index.has | 68 |
| abstract_inverted_index.our | 47, 53, 84 |
| abstract_inverted_index.set | 28, 32 |
| abstract_inverted_index.the | 2, 40, 43, 58, 81 |
| abstract_inverted_index.most | 73 |
| abstract_inverted_index.than | 26, 72 |
| abstract_inverted_index.that | 52 |
| abstract_inverted_index.then | 50 |
| abstract_inverted_index.bound | 38, 54, 61, 67 |
| abstract_inverted_index.class | 23 |
| abstract_inverted_index.lower | 37, 69 |
| abstract_inverted_index.prove | 51 |
| abstract_inverted_index.study | 1 |
| abstract_inverted_index.which | 19 |
| abstract_inverted_index.finite | 9 |
| abstract_inverted_index.greedy | 44, 59 |
| abstract_inverted_index.length | 10 |
| abstract_inverted_index.result | 85 |
| abstract_inverted_index.sensor | 88 |
| abstract_inverted_index.string | 13, 17 |
| abstract_inverted_index.bounds. | 77 |
| abstract_inverted_index.broader | 22 |
| abstract_inverted_index.problem | 4 |
| abstract_inverted_index.provide | 35 |
| abstract_inverted_index.strings | 7 |
| abstract_inverted_index.Conforti | 63 |
| abstract_inverted_index.Finally, | 78 |
| abstract_inverted_index.choosing | 6 |
| abstract_inverted_index.coverage | 89 |
| abstract_inverted_index.maximize | 12 |
| abstract_inverted_index.problem, | 48 |
| abstract_inverted_index.problem. | 90 |
| abstract_inverted_index.problems | 25 |
| abstract_inverted_index.proposed | 75 |
| abstract_inverted_index.strength | 82 |
| abstract_inverted_index.superior | 56 |
| abstract_inverted_index.algorithm | 45 |
| abstract_inverted_index.curvature | 60, 76 |
| abstract_inverted_index.functions | 15, 30 |
| abstract_inverted_index.matroids, | 18 |
| abstract_inverted_index.matroids. | 33 |
| abstract_inverted_index.complexity | 71 |
| abstract_inverted_index.maximizing | 27 |
| abstract_inverted_index.previously | 74 |
| abstract_inverted_index.submodular | 14, 29 |
| abstract_inverted_index.Cornuejols. | 65 |
| abstract_inverted_index.demonstrate | 80 |
| abstract_inverted_index.performance | 41 |
| abstract_inverted_index.optimization | 3 |
| abstract_inverted_index.computational | 70 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 4 |
| citation_normalized_percentile |