A data structure for efficiently managing a set of energy functions

Jacques Carlier (), Antoine Jouglet (), Eric Pinson () and Abderrahim Sahli ()
Additional contact information
Jacques Carlier: Sorbonne Universités, Université de Technologie de Compiègne
Antoine Jouglet: Sorbonne Universités, Université de Technologie de Compiègne
Eric Pinson: LARIS, Université Catholique de l’Ouest
Abderrahim Sahli: Univ Gustave Eiffel

Journal of Combinatorial Optimization, 2022, vol. 44, issue 4, No 17, 2460-2481

Abstract: Abstract We consider a collection of objects. Each object has an initial energy at the start of the time horizon, and a transition time at which the energy begins to decrease over time. In this paper we describe the Cooling Box, a new data structure for identifying the object with the highest energy at any time t, with values of t increasing over time. The case of decreasing linear functions is considered. Two versions are proposed, for a set of functions with identical and non-identical slopes respectively. Interestingly, we also identify the basic property of decreasing functions that makes this method possible. The data structure is then generalized to decreasing functions that are not linear. For each of these versions we describe an application.

Keywords: Data structure; Monotone functions; Complexity. (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00758-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:4:d:10.1007_s10878-021-00758-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00758-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().