{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:33:30Z","timestamp":1740123210479,"version":"3.37.3"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[2024,7,19]],"date-time":"2024-07-19T00:00:00Z","timestamp":1721347200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,7,19]],"date-time":"2024-07-19T00:00:00Z","timestamp":1721347200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001823","name":"Ministerstvo \u0160kolstv\u00ed, Ml\u00e1de\u017ee a T\u011blov\u00fdchovy","doi-asserted-by":"publisher","award":["CZ.02.1.01\/0.0\/0.0\/16_019\/0000765"],"award-info":[{"award-number":["CZ.02.1.01\/0.0\/0.0\/16_019\/0000765"]}],"id":[{"id":"10.13039\/501100001823","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007655","name":"Czech Technical University in Prague","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007655","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2024,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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.<\/jats:p>","DOI":"10.1007\/s10479-024-05980-z","type":"journal-article","created":{"date-parts":[[2024,7,19]],"date-time":"2024-07-19T16:01:43Z","timestamp":1721404903000},"page":"811-836","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Projection methods for finding the greatest element of the intersection of max-closed convex sets"],"prefix":"10.1007","volume":"340","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1944-6569","authenticated-orcid":false,"given":"Tom\u00e1\u0161","family":"Dlask","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,7,19]]},"reference":[{"key":"5980_CR1","volume-title":"Constrained Markov Decision Processes: Stochastic Modeling","author":"E Altman","year":"1999","unstructured":"Altman, E. (1999). Constrained Markov Decision Processes: Stochastic Modeling. Danvers, MA: Routledge."},{"key":"5980_CR2","doi-asserted-by":"crossref","unstructured":"Apt, K.R. (1999). The rough guide to constraint propagation. In: Principles and Practice of Constraint Programming\u2013CP\u201999: 5th International Conference, CP\u201999, Alexandria, VA, USA, October 11-14, 1999. Proceedings 5, pp. 1\u201323. Springer","DOI":"10.1007\/978-3-540-48085-3_1"},{"issue":"3","key":"5980_CR3","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1137\/S0036144593251710","volume":"38","author":"HH Bauschke","year":"1996","unstructured":"Bauschke, H. H., & Borwein, J. M. (1996). On projection algorithms for solving convex feasibility problems. SIAM review, 38(3), 367\u2013426.","journal-title":"SIAM review"},{"issue":"1","key":"5980_CR4","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R Bellman","year":"1958","unstructured":"Bellman, R. (1958). On a routing problem. Quarterly of applied mathematics, 16(1), 87\u201390.","journal-title":"Quarterly of applied mathematics"},{"key":"5980_CR5","unstructured":"Bertsekas, D.P. (1991). Linear network optimization."},{"issue":"4","key":"5980_CR6","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1137\/0801026","volume":"1","author":"DP Bertsekas","year":"1991","unstructured":"Bertsekas, D. P. (1991). An auction algorithm for shortest paths. SIAM Journal on Optimization, 1(4), 425\u2013447.","journal-title":"SIAM Journal on Optimization"},{"key":"5980_CR7","doi-asserted-by":"crossref","unstructured":"Bessiere, C. (2006). Constraint propagation. In: Handbook of Constraint Programming. Elsevier, Amsterdam. Chap. 3","DOI":"10.1016\/S1574-6526(06)80007-6"},{"key":"5980_CR8","doi-asserted-by":"crossref","unstructured":"Boyle, J.P., & Dykstra, R.L. (1986). A method for finding projections onto the intersection of convex sets in Hilbert spaces. In: Advances in Order Restricted Statistical Inference: Proceedings of the Symposium on Order Restricted Statistical Inference Held in Iowa City, Iowa, September 11\u201313, 1985, pp. 28\u201347. Springer","DOI":"10.1007\/978-1-4613-9940-7_3"},{"issue":"2","key":"5980_CR9","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.disopt.2012.11.001","volume":"10","author":"R Chandrasekaran","year":"2013","unstructured":"Chandrasekaran, R., & Subramani, K. (2013). A combinatorial algorithm for Horn programs. Discrete Optimization, 10(2), 85\u2013101.","journal-title":"Discrete Optimization"},{"key":"5980_CR10","doi-asserted-by":"crossref","unstructured":"Choi, C.W., Harvey, W., Lee, J.H.-M., & Stuckey, P.J. (2006). Finite domain bounds consistency revisited. In: Australasian Joint Conference on Artificial Intelligence, pp. 49\u201358. Springer","DOI":"10.1007\/11941439_9"},{"key":"5980_CR11","first-page":"245","volume-title":"Foundations of Artificial Intelligence","author":"D Cohen","year":"2006","unstructured":"Cohen, D., & Jeavons, P. (2006). The complexity of constraint languages. Foundations of Artificial Intelligence (Vol. 2, pp. 245\u2013280). Amsterdam: Elsevier."},{"issue":"3","key":"5980_CR12","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/BF02683333","volume":"35","author":"PL Combettes","year":"1997","unstructured":"Combettes, P. L. (1997). Hilbertian convex feasibility problem: convergence of projection methods. Applied Mathematics and Optimization, 35(3), 311\u2013330.","journal-title":"Applied Mathematics and Optimization"},{"issue":"1","key":"5980_CR13","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/BF01584992","volume":"3","author":"RW Cottle","year":"1972","unstructured":"Cottle, R. W., & Veinott, A. F. (1972). Polyhedral sets having a least element. Mathematical Programming, 3(1), 238\u2013249.","journal-title":"Mathematical Programming"},{"issue":"5","key":"5980_CR14","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1090\/S0002-9904-1950-09407-5","volume":"56","author":"HS Coxeter","year":"1950","unstructured":"Coxeter, H. S. (1950). Self-dual configurations and regular graphs. Bulletin of the American Mathematical Society, 56(5), 413\u2013455.","journal-title":"Bulletin of the American Mathematical Society"},{"key":"5980_CR15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511809088","volume-title":"Introduction to Lattices and Order","author":"BA Davey","year":"2002","unstructured":"Davey, B. A., & Priestley, H. A. (2002). Introduction to Lattices and Order. Cambridge: Cambridge University Press."},{"issue":"1","key":"5980_CR16","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.jat.2006.02.005","volume":"142","author":"F Deutsch","year":"2006","unstructured":"Deutsch, F., & Hundal, H. (2006). The rate of convergence for the cyclic projections algorithm I: Angles between convex sets. Journal of Approximation Theory, 142(1), 36\u201355.","journal-title":"Journal of Approximation Theory"},{"key":"5980_CR17","doi-asserted-by":"publisher","DOI":"10.1137\/9781611971941","volume-title":"Alternating Projection Methods","author":"R Escalante","year":"2011","unstructured":"Escalante, R., & Raydan, M. (2011). Alternating Projection Methods. Philadelphia: SIAM."},{"key":"5980_CR18","volume-title":"Handbook of Markov Decision Processes: Methods and Applications","author":"EA Feinberg","year":"2012","unstructured":"Feinberg, E. A., & Shwartz, A. (2012). Handbook of Markov Decision Processes: Methods and Applications (Vol. 40). New York: Springer."},{"issue":"6","key":"5980_CR19","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"RW Floyd","year":"1962","unstructured":"Floyd, R. W. (1962). Algorithm 97: shortest path. Communications of the ACM, 5(6), 345.","journal-title":"Communications of the ACM"},{"key":"5980_CR20","doi-asserted-by":"crossref","unstructured":"Ford\u00a0Jr, L., & Fulkerson, D. (1962). Flows in Networks.","DOI":"10.1515\/9781400875184"},{"issue":"1","key":"5980_CR21","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/BF01580374","volume":"11","author":"H Gabbay","year":"1976","unstructured":"Gabbay, H. (1976). A note on polyhedral sets having a least element. Mathematical Programming, 11(1), 94\u201396.","journal-title":"Mathematical Programming"},{"issue":"1","key":"5980_CR22","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/BF02614077","volume":"36","author":"N Gaffke","year":"1989","unstructured":"Gaffke, N., & Mathar, R. (1989). A cyclic projection algorithm via duality. Metrika, 36(1), 29\u201354.","journal-title":"Metrika"},{"issue":"1","key":"5980_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02288320","volume":"13","author":"G Gallo","year":"1988","unstructured":"Gallo, G., & Pallottino, S. (1988). Shortest path algorithms. Annals of operations research, 13(1), 1\u201379.","journal-title":"Annals of operations research"},{"key":"5980_CR24","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0163-9","volume-title":"Algebraic Graph Theory","author":"C Godsil","year":"2001","unstructured":"Godsil, C., & Royle, G. F. (2001). Algebraic Graph Theory (Vol. 207). New York: Springer."},{"issue":"3","key":"5980_CR25","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1287\/opre.47.3.445","volume":"47","author":"D Goldfarb","year":"1999","unstructured":"Goldfarb, D., & Jin, Z. (1999). An O(nm)-time network simplex algorithm for the shortest path problem. Operations Research, 47(3), 445\u2013448.","journal-title":"Operations Research"},{"key":"5980_CR26","unstructured":"Grant, M., & Boyd, S. (2014). CVX: Matlab Software for Disciplined Convex Programming, version 2.1. http:\/\/cvxr.com\/cvx."},{"key":"5980_CR27","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"2012","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., & Schrijver, A. (2012). Geometric Algorithms and Combinatorial Optimization (Vol. 2). Berlin: Springer."},{"issue":"1","key":"5980_CR28","first-page":"96","volume":"23","author":"I Halperin","year":"1962","unstructured":"Halperin, I. (1962). The product of projection operators. Acta Sci. Math. (Szeged), 23(1), 96\u201399.","journal-title":"Acta Sci. Math. (Szeged)"},{"issue":"2","key":"5980_CR29","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/0004-3702(95)00107-7","volume":"79","author":"PG Jeavons","year":"1995","unstructured":"Jeavons, P. G., & Cooper, M. C. (1995). Tractable constraints on ordered domains. Artificial Intelligence, 79(2), 327\u2013339.","journal-title":"Artificial Intelligence"},{"key":"5980_CR30","doi-asserted-by":"crossref","unstructured":"Kong, S., Lee, J.H., & Li, S. (2018). Multiagent simple temporal problem: The arc-consistency approach. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 32.","DOI":"10.1609\/aaai.v32i1.12087"},{"issue":"2","key":"5980_CR31","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1109\/TAC.1971.1099667","volume":"16","author":"H Kushner","year":"1971","unstructured":"Kushner, H., & Kleinman, A. (1971). Accelerated procedures for the solution of discrete Markov control problems. IEEE Transactions on Automatic Control, 16(2), 147\u2013152.","journal-title":"IEEE Transactions on Automatic Control"},{"key":"5980_CR32","volume-title":"Introduction to Algorithms","author":"CE Leiserson","year":"1994","unstructured":"Leiserson, C. E., Rivest, R. L., Cormen, T. H., & Stein, C. (1994). Introduction to Algorithms (Vol. 3). Cambridge: The MIT press."},{"key":"5980_CR33","unstructured":"Narboni, G.A. (2014). Propagation Properties of Min-closed CSPs. Technical communication. International Conference on Logic Programming. https:\/\/hal.science\/hal-01015663\/"},{"key":"5980_CR34","unstructured":"Osogami, T., & Morimura, T. (2015). When the optimal policy is independent of the initial state. Technical Report RT0966, IBM Research. https:\/\/dominoweb.draco.res.ibm.com\/reports\/RT0966.pdf"},{"key":"5980_CR35","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"CH Papadimitriou","year":"1998","unstructured":"Papadimitriou, C. H., & Steiglitz, K. (1998). Combinatorial Optimization: Algorithms and Complexity. Mineola, New York: Courier Corporation."},{"key":"5980_CR36","volume-title":"Handbook of Constraint Programming","author":"F Rossi","year":"2006","unstructured":"Rossi, F., Van Beek, P., & Walsh, T. (2006). Handbook of Constraint Programming. Amsterdam: Elsevier."},{"issue":"3\u20134","key":"5980_CR37","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1561\/0600000084","volume":"11","author":"B Savchynskyy","year":"2019","unstructured":"Savchynskyy, B. (2019). Discrete graphical models - an optimization perspective. Foundations and Trends in Computer Graphics and Vision, 11(3\u20134), 160\u2013429.","journal-title":"Foundations and Trends in Computer Graphics and Vision"},{"key":"5980_CR38","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A. (2003). Combinatorial Optimization: Polyhedra and Efficiency (Vol. 24). Berlin: Springer."},{"issue":"1","key":"5980_CR39","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/0304-3991(92)90234-B","volume":"40","author":"MI Sezan","year":"1992","unstructured":"Sezan, M. I. (1992). An overview of convex projections theory and its application to image recovery problems. Ultramicroscopy, 40(1), 55\u201367.","journal-title":"Ultramicroscopy"},{"key":"5980_CR40","doi-asserted-by":"publisher","unstructured":"Sturm, J. F. (1999). Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optimization Methods and Software, 11(4), 625\u2013653. https:\/\/doi.org\/10.1080\/10556789908805766","DOI":"10.1080\/10556789908805766"},{"key":"5980_CR41","doi-asserted-by":"crossref","unstructured":"Subramani, K., & Worthington, J. (2011). A new algorithm for linear and integer feasibility in Horn constraints. In: International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, pp. 215\u2013229. Springer.","DOI":"10.1007\/978-3-642-21311-3_21"},{"issue":"3","key":"5980_CR42","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1016\/j.jda.2006.12.002","volume":"5","author":"K Subramani","year":"2007","unstructured":"Subramani, K. (2007). A zero-space algorithm for negative cost cycle detection in networks. Journal of Discrete Algorithms, 5(3), 408\u2013421.","journal-title":"Journal of Discrete Algorithms"},{"issue":"2","key":"5980_CR43","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1023\/A:1013847510365","volume":"6","author":"H Van Maaren","year":"2002","unstructured":"Van Maaren, H., & Dang, C. (2002). Simplicial pivoting algorithms for a tractable class of integer programs. Journal of Combinatorial Optimization, 6(2), 133\u2013142.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"2","key":"5980_CR44","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0024-3795(68)90002-5","volume":"1","author":"AF Veinott Jr","year":"1968","unstructured":"Veinott, A. F., Jr. (1968). Extreme points of Leontief substitution systems. Linear Algebra and its Applications, 1(2), 181\u2013194.","journal-title":"Linear Algebra and its Applications"},{"key":"5980_CR45","volume-title":"Functional operators","author":"J von Neumann","year":"1950","unstructured":"von Neumann, J. (1950). Functional operators. Annals of mathematics studies: II. The geometry of orthogonal spaces."},{"key":"5980_CR46","doi-asserted-by":"crossref","unstructured":"Werner, T., Pr\u016f\u0161a, D., & Dlask, T. (2020). Relative interior rule in block-coordinate descent. In: Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition, pp. 7559\u20137567.","DOI":"10.1109\/CVPR42600.2020.00758"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-024-05980-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-024-05980-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-024-05980-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,29]],"date-time":"2024-08-29T15:46:35Z","timestamp":1724946395000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-024-05980-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,19]]},"references-count":46,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["5980"],"URL":"https:\/\/doi.org\/10.1007\/s10479-024-05980-z","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"type":"print","value":"0254-5330"},{"type":"electronic","value":"1572-9338"}],"subject":[],"published":{"date-parts":[[2024,7,19]]},"assertion":[{"value":"15 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 March 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 July 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author has no competing interests to declare.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}