Tropical Fermat–Weber Problems over Non-Finite Data and their Inverse Formulations

John Sabol, Ruriko Yoshida · 2026

Read Tropical Fermat–Weber Problems over Non-Finite Data and their Inverse Formulations by John Sabol, Ruriko Yoshida (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-27503.txt.

Introduction

Sabol and Yoshida study where to place a facility when distance itself is measured tropically, and data points may run off to infinity. The Fermat-Weber problem seeks a point minimising the weighted sum of distances to given sites. Their distance comes from the tropical one-infinity pseudonorm, a polyhedral gauge function with tunable asymmetry that is unchanged by constant shifts, so it descends to tropical projective space. In 2026, non-finite data, points at the boundary of that space, enter the formulation.

Several variants of the inverse problem are investigated: given a desired location, find data or weights that make it optimal. Linear programming formulations solve these inverse variants. The forward problem's known structure guides the inversion throughout. Tropical location theory thus gains both a wider data class and a design toolkit. Planners can work backwards from the answer they want.

Catalog record

CREATORJohn Sabol, Ruriko Yoshida
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE80 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.27503

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Tropical Fermat–Weber Problems over Non-Finite Data and their Inverse Formulations John Sabol, Ruriko Yoshida Abstract The term tropical pseudonorm refers to a family of (not necessarily symmetric) gauge functions that arise in tropical or idempotent geometry. An important characteristic of these gauges is their invariance under translation by a constant vector, allowing them to descent naturally to tropical projective spaces. In this work, we explore the tropical one-infinity pseudonorm, a polyhedral hybrid gauge that allows for tunable asymmetry, in the context of a Fermat–Weber location problem. We extend previous formulations in considering non-finite data, and we investigate several variants of the inverse problem, providing linear programming formulations for their solution. keywords Location problem, Tropical metric, Hybrid norm, Inverse linear programming, Max-plus semiring, Polyhedral gauge functions 1 Introduction Broadly speaking, a location problem can be described as follows: given a set \mathcal{X} , some finite subset V\coloneq(v_{1},\ldots,v_{m})\subset\mathcal{X} of points (sometimes called customers or sites ), and a map d:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R} measuring distance/cost between two points, find a point x^{*}\in\mathcal{X} that minimize some function f:\mathcal{X}\rightarrow\mathbb{R} of the distances between x^{*} and the points in V . When the goal is to find a point x^{*} that minimizes the weighted sum of distances between itself and the points in V , i.e., x^{*}\in\argmin_{x\in\mathcal{X}}f(x),\qquad f(x)=\sum_{i=1}^{m}w_{i}d(x,v_{i}), (1) the problem is often called the Fermat–Weber problem (or sometimes simply the “Weber problem”). In the classic setup, w_{i}\in\mathbb{R}_{>0} are positive weights that denote the relative importance of the elements in V . Whenever weights are uniform, i.e., w_{i}=w_{j} for all i,j\in[m]\coloneq\{1,\ldots,m\} , we say the problem is unweighted . Unweighted Fermat–Weber problems of the form Eq. 1 are also called 1 -medians. The set of all such minimizers in \mathcal{X} is called the Fermat–Weber set of V , denoted as \mathcal{X}^{*} : \mathcal{X}^{*}\coloneq\bigl\{x^{*}:x^{*}\in\argmin_{x\in\mathcal{X}}\sum_{i=1}^{m}w_{i}d(x,v_{i}\bigr\}. We will sometimes use notation like \mathrm{FW}(\cdot)^{*} to denote the Fermat–Weber set of a specific problem instance. That is, we will use the asterisk as a notational device to distinguish between the Fermat–Weber problem \mathrm{FW}(\cdot) , and its set of optimal solutions \mathrm{FW}(\cdot)^{*} . The Fermat–Weber problem is well-studied in the Euclidean setting, with Weiszfeld’s algorithm 39 providing an iterative method for computing a solution as early as 1937. Beyond the Euclidean setting, Fermat–Weber problems under \ell^{p} norms, particularly the rectilinear ( \ell^{1} ) and Chebyshev ( \ell^{\infty} ) metrics in the plane, have also been studied extensively in the location-theory literature 24 ; 14 ; 19 ; 16 . Many generalizations have been explored, such as for non-symmetric distance functions 15 , and negatively weighted points 31 . Still, considerably less attention has been paid to projective spaces. Beginning with Lin and Yoshida 23 , several authors have investigated the Fermat–Weber problem using a tropical distance , a pseudometric (not necessarily symmetric) that is invariant under scalar addition, and which has found applications in the field of phylogenetics, see e.g., 22 ; 9 ; 12 . The invariance under scalar addition suggests we work in a quotient space called the tropical projective torus , denoted \mathbb{R}^{n}/\mathbb{R}\mathbf{1} . We continue work in this direction, using the hybrid tropical distance introduced in 33 which generalizes the symmetric and asymmetric tropical distances considered previously. By leveraging optimality conditions associated with the subdifferential of the objective function, we extend the tropical Fermat–Weber problem to data that are not necessarily finite and show that finite solutions (if they exist) can be computed through straightforward modifications to the dual network flow graph. Then, we consider a class of tropical Fermat–Weber inverse problems which, in a certain sense, exchange the roles between certain input data and decision variables. We provide conditions on feasibility and explicit linear programming (LP) formulations for their solution. 2 Preliminaries We begin with a brief overview of tropical mathematics and its intersection with location problems. \langle\cdot,\cdot\rangle represents the Euclidean inner product, \# the cardinality of a set, and [n]=\{1,\ldots,n\} the set of all positive integers up to n . The non-negative (resp. positive) orthant is denoted \mathbb{R}^{n}_{\geq 0} (resp. \mathbb{R}^{n}_{>0} ). We use \mathbf{0} to denote the origin, and similarly, \mathbf{1}=(1,\ldots,1) for the vector of all-ones. The notation \mathbf{1}_{K} indicates the vector with 1 in the k -th index for each k\in K\subseteq[n] and zeros elsewhere. Thus, \mathbf{1}_{k} indicates the k -th standard basis vector. 2.1 Tropical Mathematics Tropical mathematics refers to a branch of mathematics built on replacing the usual arithmetic operation of addition with either minimum or maximum, and replacing multiplication with addition. The choice in convention regarding tropical addition results in the so-called min-plus or max-plus algebra. In the min-plus algebra (\mathbb{R}_{\min},\oplus,\odot) , we have \mathbb{R}_{\min}\coloneq\mathbb{R}\cup\{+\infty\} with a\oplus b=\min(a,b) for a,b\in\mathbb{R}_{\min} , where \infty serves as additive identity. Similarly, in the max-plus algebra (\mathbb{R}_{\max},\boxplus,\odot) , we have \mathbb{R}_{\max}\coloneq\mathbb{R}\cup\{-\infty\} with a\boxplus b=\max(a,b) for a,b\in\mathbb{R}_{\max} with -\infty as additive identity. Note that the lack of additive inverses make these structures semirings. The isomorphism between min-plus and max-plus semirings is easily seen by the identity -\min(-a,-b)=\max(a,b) . Component-wise application of the operations leads to the tropical semimodule \mathbb{R}_{\min}^{n} (resp. \mathbb{R}_{\max}^{n} ). For a\in\mathbb{R}_{\min}^{n} , the subset of indices corresponding to finite elements define the support of a , i.e. \mathrm{supp}(a)\coloneq\{i\mid a_{i}\in\mathbb{R}\} . Tropical geometry can be viewed as the piecewise-linear geometry induced by logarithmic coordinates on projective cones, where multiplicative structure becomes additive and asymptotic dominance relations become explicit. This perspective is especially useful in asymptotic analysis, optimization, and related areas such as large deviations and statistical mechanics. An important feature of tropical geometry is its invariance with regard to (tropical) scalar multiplication. That is, the elements of \mathbb{R}_{\min} (resp. \mathbb{R}_{\max} ) form an equivalence class given by the relation x\sim x+c\mathbf{1} for any c\in\mathbb{R} . We sometimes write \tilde{x} to denote the equivalence class associated with x . This invariance implies that one operates in tropical projective space , which for the min-plus semiring, is defined as \mathbb{TP}^{n-1}_{\mathrm{min}}\coloneq\bigl\{\mathbb{R}_{\min}\setminus\{\infty\mathbf{1}\}\bigr\}/\mathbb{R}\mathbf{1}. The tropical projective torus , denoted \mathbb{R}^{n}/\mathbb{R}\mathbf{1} is the subset of tropical projective space comprised of finite coordinates. Thus, whereas the definition of \mathbb{TP}^{n-1} depends on the version of the tropical semiring, \mathbb{R}^{n}/\mathbb{R}\mathbf{1} is the same under both conventions. When operating over \mathbb{R}^{n}/\mathbb{R}\mathbf{1} , it is common to a select a coordinate representative from the equivalence class according to some convention, such as by requiring that the first coordinate be equal to 0 . Thus, we see that \mathbb{R}^{n}/\mathbb{R}\mathbf{1} naturally identifies with \mathbb{R}^{n-1} . The natural metric over \mathbb{R}^{n}/\mathbb{R}\mathbf{1} is given by the tropical distance , \mathrm{d}_{\mathrm{tr}}(x,y)\coloneq\max_{i\in[n]}(y_{i}-x_{i})-\min_{i\in[n]}(y_{i}-x_{i}), which is closely related to (and sometimes called) Hilbert’s projective metric . \mathrm{d}_{\mathrm{tr}} is induced by the tropical norm \lVert x\rVert_{\mathrm{tr}}\coloneq\max_{i}(x_{i})-\min_{i}(x_{i}) , which one can verify defines a norm over \mathbb{R}^{n}/\mathbb{R}\mathbf{1} . Tropical hyperplanes are fundamental objects in tropical geometry. Definition 1 (Min-Plus Tropical Hyperplane, 21 ) . Given a vector a\in\mathbb{R}_{\min}^{n} with \mathrm{supp}(a)\geq 2 , the (min-plus) tropical hyperplane is given by \mathcal{T}^{\min}(a)\coloneq\{x\in\mathbb{R}^{n}:\#\argmin_{i}(a_{i}+x_{i})\geq 2\}. An equivalent definition for the max-plus tropical hyperplane \mathcal{T}^{\max}(a) for a\in\mathbb{R}_{\max}^{n} is obtained by replacing \argmin with \argmax in the definition above. The point -a , called the apex , witnesses every term a_{i}+x_{i} attain the minimum (resp. maximum) simultaneously. Any tropical hyperplane with apex -a can be viewed as a translation \mathcal{T}(a)=(-a)+\mathcal{T}(\mathbf{0}) . The union of several tropical hyperplanes \bigcup_{a\in A}\mathcal{T}^{\min}(a) forms a tropical hyperplane

Read the complete text