Efficient Algorithms for Lipschitz Selections of Set-Valued Mappings in \bf R²: long version

2025/03/24 by Pavel Shvartsman, Shvartsman, Pavel
Computer Science · Mathematics · #46E35 #Advanced Banach Space Theory #FOS: Mathematics #Fixed Point Theorems Analysis #Functional Analysis (math.FA) #Optimization and Variational Analysis

paper · pdf · doi:10.48550/arxiv.2503.19094

openalex publication_date 2025/03/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let F be a set-valued mapping from an N-element metric space (\mathcal M,ρ) into the family of all closed half-planes in \bf R². In this paper, we provide an efficient algorithm for a Lipschitz selection of F, i.e., a Lipschitz mapping f:\mathcal M→\bf R² such that f(x)∈ F(x) for all x∈\mathcal M. Given a constant λ>0, this algorithm produces the following two outcomes: (1) The algorithm guarantees that there is no Lipschitz selection of F with Lipschitz constant at most λ; (2) The algorithm returns a Lipschitz selection of F with Lipschitz constant at most 3λ. The total work and storage required by this selection algorithm are at most CN² where C is an absolute constant.

Related

• Existence Criteria for Lipschitz Selections of Set-Valued Mappings in \bf R²
• The Core of a 2-Dimensional Set-Valued Mapping. Existence Criteria and Efficient Algorithms for Lipschitz Selections of Low Dimensional Set-Valued Mappings
• On the Core of a Low Dimensional Set-Valued Mapping
• Sharp finiteness principles for Lipschitz selections
• A Pointwise Lipschitz Selection Theorem