A Linear Programming Approach for Resource-Aware Information-Theoretic Tree Abstractions Article Swipe
Daniel T. Larsson
,
Dilip Kumar Maity
,
Panagiotis Tsiotras
·
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2208.04220
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2208.04220
In this chapter, an integer linear programming formulation for the problem of obtaining task-relevant, multi-resolution, environment abstractions for resource-constrained autonomous agents is presented. The formulation leverages concepts from information-theoretic signal compression, specifically, the information bottleneck (IB) method, to pose an abstraction problem as an optimal encoder search over the space of multi-resolution trees. The abstractions emerge in a task-relevant manner as a function of agent information-processing constraints. We detail our formulation, and show how hierarchical tree structures, signal encoders, and information-theoretic methods for signal compression can be unified under a common theme. A discussion delineating the benefits and drawbacks of our formulation is presented, as well as a detailed explanation how our approach can be interpreted within the context of generating abstractions for resource-constrained autonomous systems. It is shown that the resulting information-theoretic abstraction problem over the space of multi-resolution trees can be formulated as a integer linear programming (ILP) problem. We demonstrate the approach on a number of examples, and provide a discussion detailing the differences of the proposed framework compared to existing methods. Lastly, we consider a linear program relaxation of the ILP problem, thereby demonstrating that multi-resolution information-theoretic tree abstractions can be obtained by solving a convex program.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2208.04220
- https://arxiv.org/pdf/2208.04220
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4302788655
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4302788655Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2208.04220Digital Object Identifier
- Title
-
A Linear Programming Approach for Resource-Aware Information-Theoretic Tree AbstractionsWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2022Year of publication
- Publication date
-
2022-08-08Full publication date if available
- Authors
-
Daniel T. Larsson, Dilip Kumar Maity, Panagiotis TsiotrasList of authors in order
- Landing page
-
https://arxiv.org/abs/2208.04220Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2208.04220Direct 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/2208.04220Direct OA link when available
- Concepts
-
Computer science, Integer programming, Tree (set theory), Theoretical computer science, Abstraction, Context (archaeology), Linear programming, Mathematical optimization, Algorithm, Mathematics, Biology, Epistemology, Philosophy, Paleontology, Mathematical analysisTop 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/W4302788655 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2208.04220 |
| ids.doi | https://doi.org/10.48550/arxiv.2208.04220 |
| ids.openalex | https://openalex.org/W4302788655 |
| fwci | |
| type | preprint |
| title | A Linear Programming Approach for Resource-Aware Information-Theoretic Tree Abstractions |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T11010 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9052000045776367 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1702 |
| topics[0].subfield.display_name | Artificial Intelligence |
| topics[0].display_name | Logic, Reasoning, and Knowledge |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C41008148 |
| concepts[0].level | 0 |
| concepts[0].score | 0.7601038217544556 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[0].display_name | Computer science |
| concepts[1].id | https://openalex.org/C56086750 |
| concepts[1].level | 2 |
| concepts[1].score | 0.587354302406311 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q6042592 |
| concepts[1].display_name | Integer programming |
| concepts[2].id | https://openalex.org/C113174947 |
| concepts[2].level | 2 |
| concepts[2].score | 0.558811366558075 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q2859736 |
| concepts[2].display_name | Tree (set theory) |
| concepts[3].id | https://openalex.org/C80444323 |
| concepts[3].level | 1 |
| concepts[3].score | 0.5212924480438232 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[3].display_name | Theoretical computer science |
| concepts[4].id | https://openalex.org/C124304363 |
| concepts[4].level | 2 |
| concepts[4].score | 0.5177818536758423 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q673661 |
| concepts[4].display_name | Abstraction |
| concepts[5].id | https://openalex.org/C2779343474 |
| concepts[5].level | 2 |
| concepts[5].score | 0.4727262556552887 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q3109175 |
| concepts[5].display_name | Context (archaeology) |
| concepts[6].id | https://openalex.org/C41045048 |
| concepts[6].level | 2 |
| concepts[6].score | 0.4341951310634613 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q202843 |
| concepts[6].display_name | Linear programming |
| concepts[7].id | https://openalex.org/C126255220 |
| concepts[7].level | 1 |
| concepts[7].score | 0.37946105003356934 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[7].display_name | Mathematical optimization |
| concepts[8].id | https://openalex.org/C11413529 |
| concepts[8].level | 1 |
| concepts[8].score | 0.29365408420562744 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[8].display_name | Algorithm |
| concepts[9].id | https://openalex.org/C33923547 |
| concepts[9].level | 0 |
| concepts[9].score | 0.1586330533027649 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[9].display_name | Mathematics |
| concepts[10].id | https://openalex.org/C86803240 |
| concepts[10].level | 0 |
| concepts[10].score | 0.0 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q420 |
| concepts[10].display_name | Biology |
| concepts[11].id | https://openalex.org/C111472728 |
| concepts[11].level | 1 |
| concepts[11].score | 0.0 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q9471 |
| concepts[11].display_name | Epistemology |
| concepts[12].id | https://openalex.org/C138885662 |
| concepts[12].level | 0 |
| concepts[12].score | 0.0 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q5891 |
| concepts[12].display_name | Philosophy |
| concepts[13].id | https://openalex.org/C151730666 |
| concepts[13].level | 1 |
| concepts[13].score | 0.0 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q7205 |
| concepts[13].display_name | Paleontology |
| concepts[14].id | https://openalex.org/C134306372 |
| concepts[14].level | 1 |
| concepts[14].score | 0.0 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[14].display_name | Mathematical analysis |
| keywords[0].id | https://openalex.org/keywords/computer-science |
| keywords[0].score | 0.7601038217544556 |
| keywords[0].display_name | Computer science |
| keywords[1].id | https://openalex.org/keywords/integer-programming |
| keywords[1].score | 0.587354302406311 |
| keywords[1].display_name | Integer programming |
| keywords[2].id | https://openalex.org/keywords/tree |
| keywords[2].score | 0.558811366558075 |
| keywords[2].display_name | Tree (set theory) |
| keywords[3].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[3].score | 0.5212924480438232 |
| keywords[3].display_name | Theoretical computer science |
| keywords[4].id | https://openalex.org/keywords/abstraction |
| keywords[4].score | 0.5177818536758423 |
| keywords[4].display_name | Abstraction |
| keywords[5].id | https://openalex.org/keywords/context |
| keywords[5].score | 0.4727262556552887 |
| keywords[5].display_name | Context (archaeology) |
| keywords[6].id | https://openalex.org/keywords/linear-programming |
| keywords[6].score | 0.4341951310634613 |
| keywords[6].display_name | Linear programming |
| keywords[7].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[7].score | 0.37946105003356934 |
| keywords[7].display_name | Mathematical optimization |
| keywords[8].id | https://openalex.org/keywords/algorithm |
| keywords[8].score | 0.29365408420562744 |
| keywords[8].display_name | Algorithm |
| keywords[9].id | https://openalex.org/keywords/mathematics |
| keywords[9].score | 0.1586330533027649 |
| keywords[9].display_name | Mathematics |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2208.04220 |
| 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/2208.04220 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| 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/2208.04220 |
| locations[1].id | doi:10.48550/arxiv.2208.04220 |
| 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.2208.04220 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5065726020 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-2544-6709 |
| authorships[0].author.display_name | Daniel T. Larsson |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Larsson, Daniel T. |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5042246095 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-4284-3578 |
| authorships[1].author.display_name | Dilip Kumar Maity |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Maity, Dipankar |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5077667229 |
| authorships[2].author.orcid | https://orcid.org/0000-0001-7563-4129 |
| authorships[2].author.display_name | Panagiotis Tsiotras |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Tsiotras, Panagiotis |
| authorships[2].is_corresponding | False |
| 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/2208.04220 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2022-10-07T00:00:00 |
| display_name | A Linear Programming Approach for Resource-Aware Information-Theoretic Tree Abstractions |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T11010 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9052000045776367 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1702 |
| primary_topic.subfield.display_name | Artificial Intelligence |
| primary_topic.display_name | Logic, Reasoning, and Knowledge |
| related_works | https://openalex.org/W4285278887, https://openalex.org/W2365237642, https://openalex.org/W2995925505, https://openalex.org/W3116484972, https://openalex.org/W2941986668, https://openalex.org/W4232431455, https://openalex.org/W4388675521, https://openalex.org/W2108135022, https://openalex.org/W3148810651, https://openalex.org/W2898772359 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2208.04220 |
| 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/2208.04220 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| 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/2208.04220 |
| primary_location.id | pmh:oai:arXiv.org:2208.04220 |
| 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/2208.04220 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| 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/2208.04220 |
| publication_date | 2022-08-08 |
| publication_year | 2022 |
| referenced_works_count | 0 |
| abstract_inverted_index.A | 92 |
| abstract_inverted_index.a | 57, 61, 89, 107, 145, 156, 162, 178, 198 |
| abstract_inverted_index.In | 0 |
| abstract_inverted_index.It | 126 |
| abstract_inverted_index.We | 67, 151 |
| abstract_inverted_index.an | 3, 39, 43 |
| abstract_inverted_index.as | 42, 60, 104, 106, 144 |
| abstract_inverted_index.be | 86, 114, 142, 194 |
| abstract_inverted_index.by | 196 |
| abstract_inverted_index.in | 56 |
| abstract_inverted_index.is | 21, 102, 127 |
| abstract_inverted_index.of | 11, 50, 63, 99, 119, 138, 158, 167, 182 |
| abstract_inverted_index.on | 155 |
| abstract_inverted_index.to | 37, 172 |
| abstract_inverted_index.we | 176 |
| abstract_inverted_index.ILP | 184 |
| abstract_inverted_index.The | 23, 53 |
| abstract_inverted_index.and | 71, 79, 97, 160 |
| abstract_inverted_index.can | 85, 113, 141, 193 |
| abstract_inverted_index.for | 8, 17, 82, 122 |
| abstract_inverted_index.how | 73, 110 |
| abstract_inverted_index.our | 69, 100, 111 |
| abstract_inverted_index.the | 9, 32, 48, 95, 117, 130, 136, 153, 165, 168, 183 |
| abstract_inverted_index.(IB) | 35 |
| abstract_inverted_index.from | 27 |
| abstract_inverted_index.over | 47, 135 |
| abstract_inverted_index.pose | 38 |
| abstract_inverted_index.show | 72 |
| abstract_inverted_index.that | 129, 188 |
| abstract_inverted_index.this | 1 |
| abstract_inverted_index.tree | 75, 191 |
| abstract_inverted_index.well | 105 |
| abstract_inverted_index.(ILP) | 149 |
| abstract_inverted_index.agent | 64 |
| abstract_inverted_index.shown | 128 |
| abstract_inverted_index.space | 49, 137 |
| abstract_inverted_index.trees | 140 |
| abstract_inverted_index.under | 88 |
| abstract_inverted_index.agents | 20 |
| abstract_inverted_index.common | 90 |
| abstract_inverted_index.convex | 199 |
| abstract_inverted_index.detail | 68 |
| abstract_inverted_index.emerge | 55 |
| abstract_inverted_index.linear | 5, 147, 179 |
| abstract_inverted_index.manner | 59 |
| abstract_inverted_index.number | 157 |
| abstract_inverted_index.search | 46 |
| abstract_inverted_index.signal | 29, 77, 83 |
| abstract_inverted_index.theme. | 91 |
| abstract_inverted_index.trees. | 52 |
| abstract_inverted_index.within | 116 |
| abstract_inverted_index.Lastly, | 175 |
| abstract_inverted_index.context | 118 |
| abstract_inverted_index.encoder | 45 |
| abstract_inverted_index.integer | 4, 146 |
| abstract_inverted_index.method, | 36 |
| abstract_inverted_index.methods | 81 |
| abstract_inverted_index.optimal | 44 |
| abstract_inverted_index.problem | 10, 41, 134 |
| abstract_inverted_index.program | 180 |
| abstract_inverted_index.provide | 161 |
| abstract_inverted_index.solving | 197 |
| abstract_inverted_index.thereby | 186 |
| abstract_inverted_index.unified | 87 |
| abstract_inverted_index.approach | 112, 154 |
| abstract_inverted_index.benefits | 96 |
| abstract_inverted_index.chapter, | 2 |
| abstract_inverted_index.compared | 171 |
| abstract_inverted_index.concepts | 26 |
| abstract_inverted_index.consider | 177 |
| abstract_inverted_index.detailed | 108 |
| abstract_inverted_index.existing | 173 |
| abstract_inverted_index.function | 62 |
| abstract_inverted_index.methods. | 174 |
| abstract_inverted_index.obtained | 195 |
| abstract_inverted_index.problem, | 185 |
| abstract_inverted_index.problem. | 150 |
| abstract_inverted_index.program. | 200 |
| abstract_inverted_index.proposed | 169 |
| abstract_inverted_index.systems. | 125 |
| abstract_inverted_index.detailing | 164 |
| abstract_inverted_index.drawbacks | 98 |
| abstract_inverted_index.encoders, | 78 |
| abstract_inverted_index.examples, | 159 |
| abstract_inverted_index.framework | 170 |
| abstract_inverted_index.leverages | 25 |
| abstract_inverted_index.obtaining | 12 |
| abstract_inverted_index.resulting | 131 |
| abstract_inverted_index.autonomous | 19, 124 |
| abstract_inverted_index.bottleneck | 34 |
| abstract_inverted_index.discussion | 93, 163 |
| abstract_inverted_index.formulated | 143 |
| abstract_inverted_index.generating | 120 |
| abstract_inverted_index.presented, | 103 |
| abstract_inverted_index.presented. | 22 |
| abstract_inverted_index.relaxation | 181 |
| abstract_inverted_index.abstraction | 40, 133 |
| abstract_inverted_index.compression | 84 |
| abstract_inverted_index.delineating | 94 |
| abstract_inverted_index.demonstrate | 152 |
| abstract_inverted_index.differences | 166 |
| abstract_inverted_index.environment | 15 |
| abstract_inverted_index.explanation | 109 |
| abstract_inverted_index.formulation | 7, 24, 101 |
| abstract_inverted_index.information | 33 |
| abstract_inverted_index.interpreted | 115 |
| abstract_inverted_index.programming | 6, 148 |
| abstract_inverted_index.structures, | 76 |
| abstract_inverted_index.abstractions | 16, 54, 121, 192 |
| abstract_inverted_index.compression, | 30 |
| abstract_inverted_index.constraints. | 66 |
| abstract_inverted_index.formulation, | 70 |
| abstract_inverted_index.hierarchical | 74 |
| abstract_inverted_index.demonstrating | 187 |
| abstract_inverted_index.specifically, | 31 |
| abstract_inverted_index.task-relevant | 58 |
| abstract_inverted_index.task-relevant, | 13 |
| abstract_inverted_index.multi-resolution | 51, 139, 189 |
| abstract_inverted_index.multi-resolution, | 14 |
| abstract_inverted_index.resource-constrained | 18, 123 |
| abstract_inverted_index.information-theoretic | 28, 80, 132, 190 |
| abstract_inverted_index.information-processing | 65 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 3 |
| citation_normalized_percentile |