Projection methods for finding the greatest element of the intersection of max-closed convex sets
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F24%3A00376325" target="_blank" >RIV/68407700:21230/24:00376325 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1007/s10479-024-05980-z" target="_blank" >https://doi.org/10.1007/s10479-024-05980-z</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s10479-024-05980-z" target="_blank" >10.1007/s10479-024-05980-z</a>
Alternative languages
Result language
angličtina
Original language name
Projection methods for finding the greatest element of the intersection of max-closed convex sets
Original language description
We focus on the problem of finding the greatest element of the intersection of max-closed convex sets. For this purpose, we analyze the famous method of cyclic projections and show that, if this method is suitably initialized and applied to max-closed convex sets, it converges to the greatest element of their intersection. Moreover, we propose another projection method, called the decreasing projection, which turns out both theoretically and practically preferable to Euclidean projections in this particular case. Next, we argue that several known algorithms, such as Bellman-Ford and Floyd-Warshall algorithms for shortest paths or Gauss-Seidel variant of value iteration in Markov decision processes, can be interpreted as special cases of iteratively applying decreasing projections onto certain max-closed convex sets. Finally, we link decreasing projections (and thus also the aforementioned algorithms) to bounds consistency in constraint programming.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Research Center for Informatics</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Annals of Operations Research
ISSN
0254-5330
e-ISSN
1572-9338
Volume of the periodical
340
Issue of the periodical within the volume
2-3
Country of publishing house
US - UNITED STATES
Number of pages
26
Pages from-to
811-836
UT code for WoS article
001272296700002
EID of the result in the Scopus database
2-s2.0-85199008812