Unbalanced Optimal Total Variation Transport: A Theoretical Approach to Spatial Resource Allocation Problems
Authors: Nhan-Phu Chung
Jinhui Han
Bohan Li
Zehao Li
Venue: NeurIPS 2025 poster ()
Keywords: Unbalanced optimal transport; Total variation; Spatial resource allocation; Theory
Primary area: theory
TL;DR: We propose and analyze a new class of unbalanced weak optimal transport (OT) problems with total variation penalties.

Abstract: We propose and analyze a new class of unbalanced weak optimal transport (OT) problems with total variation penalties, motivated by spatial resource allocation tasks. Unlike classical OT, our framework accommodates general unbalanced nonnegative measures and incorporates cost objectives that directly capture operational trade-offs between transport cost and supply–demand mismatch. In the general setting, we establish the existence of optimal solutions and a dual formulation. We then focus on the semi-discrete setting, where one measure is discrete and the other is absolutely continuous, a structure relevant to applications such as service area partitioning for facilities like schools or medical stations. Exploiting a tessellation-based structure, we derive the corresponding explicit optimality conditions. 
We further address a quantization problem that jointly optimizes the locations and weights of discrete support points, applicable to facility location tasks such as the cost-efficient deployment of battery swap stations or e-commerce warehouses, informed by demand-side data. The dual-tessellation structure also yields explicit gradient expressions, enabling efficient numerical optimization in finite dimensions.

Unbalanced Optimal Total Variation Transport: A Theoretical Approach to Spatial Resource Allocation Problems
Nhan-Phu Chung* Institute of Applied Mathematics University of Economics Ho Chi Minh City phucnOueh. edu. vn
Jinhui Han"
Guanghua School of Management
Peking University
jinhui jinhui.han@gen, pku, edu. cn
Bohan Li' Center for Financial Engineering Soochow University bhli ielisssda.eee edu. cn
Zehao Li
Guanghua School of Management
Peking University
zehacli@stu. pku. euu.
Abstract
We propose and analyze class of unbalanced weak optimal transport (OT) problems with total variation penalties, motivated by spatial resource allocation tasks. Unlike classical OT, our framework accommodates general unbalanced non- negative measures and incorporates cost objectives that directly capture operational trade-offs between transport cost and supply-demand mismatch. In the general setting, we establish the existence of optimal solutions and a dual formulation. We then focus on the semi-discrete setting, where one measure discrete and the other is absolutely continuous, a structure relevant to applications such as service area partitioning for facilities like schools or medical stations. Exploit- ing tessellation-bant conditions. We further address quantization problem that jointly optimizes the locations and weights of discrete support points, applicable to facility location tasks such as the cost-efficient deployment of battery swap stations or e-commerce warehouses, informed by demand-side data. The dual-tessellation structure also yields explicit gradient expressions, enabling efficient numerical optimization finite dimensions.
structure, we derive the corresponding explicit optimality
Introduction
Optimal Transport (OT) provides principled way to compare and transform probability measures by reallocating mass at minimal cost, as determined by ground metric. Its sensitivity to distributional geometry and capacity to interpolate between measures have made OT a central tool in machine learning, statistics, and applied mathematies [5T]. Applications span generative modeling [6, 211,
domain adaptation [10 [6 23 28
robust statistics 45 46). clustering (35). image and shape processing [49 59 graph matching (29), stochastic dynamics [66], and posterior inference [30].
Classical OT enforces strict mass conservation, which is often impractical in real-world scenarios due to noise, outliers, or domain mismatch 45 58]. Unbalanced OT (UOT) addresses this limitation Various penalties have been
by relaxing marginal constraints through penalty functions 42
43
"quull-ontributtonn authorship listed in alphabetical order. Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

introduced to accommodate different applications, such as Kullback Leibler (KL) divergence [20 43
f-divergences 4 X² divergennce [TO], and total variation (TV) 45 53
54 62
Correspondingly.
range of computational strategies have been developed, including regression-based approaches
17
generalized Sinkhorn algorithms [20] [2], low-rank solvers [57], and GAN-based methods
65
Despite these advances, the theoretical foundations of UOT under non-superlinear penalties,
particularly TV, remain underdeveloped.
Meanwhile, the semi-discrete OT setting, where one marginal is continuous and the other discrete, has gained prominence applications like autoencoders [ 63 and GAN training 44. Semi-discrete UOT further integrates this structure with mass imbalance, and has proven effective in tasks like quantization (15) and mode regularization in GANs [64]. In parallel, weak OT formulations generalize classical couplings by evaluating cost over disintegration of transport plans, allowing each source point to be matched with a probability distribution over the target space (2 19 22]. This added
flexibility enhances robustness to sampling noise and is particularly advantageous in settings where
empirical distributions render classical couplings unstable g 29
In this paper, motivated by spatial resource allocation problems, we study a new class of unbalanced weak OT problems with total variation penalties. Unlike smoother, superlinear divergences studied in existing theory. TV-based penalties are piecewise linear and less smooth, posing substantial analytical challenges. Our work advances the theory of OT by developing a rigorous framework for this more general and practically motivated setting.
Our Contributions.
A novel UOT formulation. We propose the first formulation of semi-discrete, unbalanced weak optimal transport with total variation penalties, integrating weak couplings, mass imbalance, and non-superlinear regularization. This formulation motivated by practical applications and introduces new mathematical structures.
Comprehensive theoretical results for TV-penalized UOT. We establish the existence of optimal solutions and derive a dual formulation in the general setting. In the semi discreee case, we develop a tessellation-bass problem to a finiteddimenional one, enabling explicit optimality conditions via Laguerre cell partitioning. Building on this, we further address an associated quantization problem. These results significantly extend and generalize classical regroay-regulariied transport frameworks to the non-smooth, TV-penalized regime.
reformulation that reduces the infiniteddimensional
Practical significance. Our theoretical framework captures key features of real-world problems, including semi-discrete geometry, mass imbalance, TV-type regularization, and probabilistic routing. In the semi-discrete regime, the induced tusl-tessslllttonn structure and explicit gradient expressions enable efficient optimization, which we demonstrate through two illustrative applications: supply area division and spatial resource allocation.
Related Work.
From a theoretical standpoint, recent work has significantly advanced the understanding of OT
under classical assumptions and various extensions 112
25
26
31
36
44
47 56). Among these,
Pooladian et al. (55) investigate the semi-discrete OT problem with entropic regularization, followed by Agarwal et al. M. which develops combinatorial algorithm for the same setting. Theoretical analysis of UOT has also emerged, although much of the focus has been on algorithmic convergence and scalability rather than fundamental properties of the UOT problem itself [14] 24 52 60, 66).
A notable exception is the work of Bourne et al. [15], which addresses semi-discrete UOT with smooth entropy- penalties. Besides, weak OT has received growing attention
p 38). Chung
and Trinh (22] develop a general duality theory for weak optimal entropy transport under superlinear convex penalties. Most recently, Beiglböck et al. (II) extend strong duality results to weak OT with nonlinear cost functions, establishing a fundamental theorem for weak OT.
An unbalanced weak optimal total variation transport problem
2.1 Background on optimal transport and its generalizations
Rooted in the seminal work of Monge and Kantorovich, the classical OT problem seeks the most cost-efficient plan to transport mass from source distribution μn on X1 to target distribution μ2 on

---

X2 under a prescribed cost function c(21,22) Formally, it solves
/ c(21, 22) 22)d
min xell(pr.fe) X, xX2
where I( (2a) denotes the set of couplings with marginals μn and μ22 To better accommodate various practical needs, several generalizations of OT have been proposed. Two important directions include weak OT, which relaxes the requirement of exact larget marginal matching, and entropy- regularized UOT, which allows for mass variation while promoting smoother solutions. These extensions have proven particularly valuable in real-world applications, where strict mass conservation or exact marginal fidelity is either infeasible or undesirable.
Weak OT. The weak OT framework replaces the hard constraint of matching the target distribu- tion exactly with a more relaxed, aggregate matching condition, typically through expectations or barycentric projections. A representative formulation is:
{ C( Tax (o)))((dx)))
min (El
Jx1
where (Tzz exyex x2 denotes the disintegration of the coupling π with respect to its first margin. Here, the cost function changes to C X1 x P(X2) + R U {+ where P(X) represents the space of probability measures on X. Notably, the classical OT formulation is recovered as a special case Weak OT approach proves particularly useful when the target measure μ2 is only partially observed or known with uncertainty, common situation in learning systems built finite data. Compared to the rigid structure of classical OT, the weak formulation enhances stability and robustness in the learned transport plan. Furthermore, with suitable convexity properties, weak OT problems remain computationally tractable and well-suited for integration into learning pipelines.
when P(x,p) c(zz, y)dp(y) for a base point-to-point cost 2
& 32
Entropy-Regularizee UOT. Another prominent extension is entropy-regularizzd UOT, which com- bines the benefits of entropic smoothing with the ability to handle measures of unequal total mass. This variant modifies the classical formulation by relaxing marginal constraints and penalizing deviations using divergence terms. A typical formulation, following [43]. is
Fililm) + S
inf 7EM(XIxXa)
XXIXX cx (eg, 12)dd
where M(X) denotes the space of nonnegative finite Borel measures, and Vt is the margin of the transport plan on X; In contrast to classical OT, the plan 7 is not constrained to be a coupling. and the input measures μl and #2 need not have equal total mass. The functions F, typically encode divergences such as the KL divergence, thereby penalizing deviation from the prescribed marginals. Intuitively, although perfect mass preservation is inherently unattainable in the unbalanced setting, the resulting formulation aims to strike a balance between minimizing transport cost and permitting controlled deviations from marginal consistency. The entropic terms enhance smoothness and yield strongly convex objectives, enabling fast convergence of iterative solvers such as generalized Sinkhorn algorithms 20 52]. Notably, the classical OT problem is recovered as a limiting case when both input measures are probability distributions and the penalization for any deviation is infinite.
2.2 Our considered problem
In many decision-centric tasks, particularly those arising in operational and resourcee-constrained environments, the cost of deviating from a desired distribution cannot be adequately captured by standard divergence-based penalties. Although statistical divergences such as the KI. divergence are inherently asymmetric, their asymmetry does not generally reflect the directional economic or operational significance observed in real-world applications. For example, under-supplying a resource (c.g., understocking inventory or under-allocating service capacity) typically incurs substantially higher costs than over-supplying, due to lost sales, service failures, or unmet demand. More importantly, classical divergence measures quantify statistical dissimilarity without conveying explicit physical meaning cost implications, limiting their interpretability in applied settings such as supply-demant demand matching and resource allocation.
To address this gap, we propose an unbalanced weak optimal total variation transport problem that replaces statistical divergence penalties with newsvendor-type loss function, a cost model well-
established in inventory management and economics 34 37 50 The newsvendor loss offers
3

---

parsimonious yet expressive way of modeling asymmetric penalties by assigning distinct weights to overestimation and underestimation. Its piecewise linear form directly reflects the real-world mismatch level, providing a physically meaningful and interpretable objective that aligns with the goals of many resouree allocation problems [33 67]. We consider the following optimization problem: for nonnegative vectors L (01,b,) and K2 = (a2, b2), f1 E MM(X)) MM2)), and y E MM x X2).
inf & ck (11, xeM(XxxXa)
FT (711
(1)
where
ET k2 (ylm,, H2) aail(m - - bil(m m1) + + 21 + b2 - 12)*11
+ / C(ai, To, (
with y1 and Y/2 denoting the marginals of y, and (Yx; Jarex, being the disintegration of r with respect to its first marginal. Here, for a scalar or measurable function we set 9 := max [g. 0}, while for signed measure v, we take v+ be the positive variation the Jordan decomposition v == - V with w+ 2 0, -ー > 0, and u+ 1 v When interpreted through the lens of supply-demand matching, the objective function offers clear economic interpretation. The first two terms penalize supply-side mismatches: shortages are penalized at rate 61, while excess supply incurs cost d1. The next two terms represent demand-side penalties: lost demand due to undersupply is penalized at rate ag. whereas overprovision relative to demand incurs cost 62. When all weights are set to one, the objective corresponds to the TV distance between marginals and has been applied in prior work, such as [68].
Following the introduction in Section 2. I the considered weak formulation can reduce to normal case by choosing p) = k [x. c(11, x2 dp(x2)) for some point-to- co-tttt- function c: Xg x X2 >
(-o0, +oo]. This choice leads to a special case of entropy-reee regropp-regulrrized UOT studied in 43
gk. (H1 =
inf xeM(Xixx,)
ka. (T|m1,
(2)
where
ETk ==)1(m - + bil(% - m1) +1) a2l(uz - -22) +1) +1 b2l(72 - +1
/ Xx c(21, 22) (x1
+
where the nonnegative constant ht serves rescale the transportation cost, reflecting the relative importance between transport and mismatch costs. While technically it can be absorbed into the definition of the cost function c, keeping it explicit highlights the application-dependen trade-off.
Definition 2.1. We say that the problem (resp. ( is feasible if there exists transport plan M(Xi x X2) such that ETKE (yl41, (22) < x (resp. ETk,, k2.k (Tk,,,))*())
< oo).
While our primary focus application is on resource allocation, we anticipate that the proposed unbalanced weak OT framework holds significant potential across broader spectrum of applications. As discussed earlier, this setting represents one of the most expressive and versatile generalizations in OT theory. In particular, the weak formulation enables to push the theory to its limits and includes classical OT as a special case. Beyond its generality, the weak formulation has shown promising practical advantages: by relaxing the coupling constraints, it enhances robustness to sampling noise and stability in empirical settings where exact couplings may not exist or may be sensitive to perturbations (see, e.g., 8 (2]). In this work, our objective is to establish a rigorous theoretical foundation for this framework, paving the way for its application in diverse decision- making and learning contexts.
Example 2.1 (Order dispatching in ride-sourcing platforms). 168 considers an order dispatching problem in ride-sone sourcing platforms, where the objective is to assign idle vehicles meet customer demand across different locations. To simultaneously account for transportation cost and supply- demand mismutches, both of which directly affect platform efficiency and profitability, the authors propose formulation that can be viewed special instance of the model in (2). In their context, problem-specte constraints are imposed to reflect practical considerations, such as a fixed supply- side marginal to represent the limited number of available drivers.
4

---

Remark 2.1. Recasting resource allocation problems as an unbalanced weak OT framework provides several theoretical and practical advantages. First, the OI formulation geometrically expressive. By embedding the problem in metric space, it naturally captures spatial relationships through structures such as Laguerre and Voronoi ciaselaatios-ffaturre that are difficult to obtain from purely algebraic linear programming (LP) models. This geometric perspective is not only mathematically elegant but also supports practical applications, such as service-area partitioning for facilities like fire stations or warehouses. Second, OT allows natural treatment of imbalance through TV penalties, which directly quantify the cost of mass creation or deletion. This yields an explicit trade-off between transportation and mismatch costs, avoiding artificial slack variables often used in LP formulations. The magnitude of the TV term provides an intuitive measure of over- or under-supply. Third, the continuous formulation greatly enhances scalability, particularly in semi semi- dincidiscrtt formulation, as it avoids high-ding high-dimensional LP formulations by reducing the optimization to a weight vector whose size matches the number of facilities. Overall, the OTF-hased approach offers a geometrically faithful, imbalance aawar,, and efficient modeling framework. While LP methods remain convenient for direct implementation, we believe the structure, interpretability, and flexibility of the Of perspective provide substantial benefits.
3 Main theoretical results
In this section, we present our main theoretical contributions, which are organized into three key components. First, in Section 3.1 we derive a dual formulation for the unbalanced weak optimal total variation transport problem (T) This dual characterization serves as foundational tool for establishing optimality conditions and facilitates both analysis and computation. We then turn our attention to the semi-discrete setting in Sections 3.2 and 3.3 where marginal is a discrete measure and the other is absolutely continuous with respect to the Lebesgue measure. This setting is motivated by practical applications in spatial resource allocation, including (1) service area partitioning, where one seeks to determine the optimal service regions of facilities such as medical stations or schools, and (2) facility location problems, such as the placement of battery swap stations or e-commerce warehouses. Specifically, Section [3.2 establisss optimality conditions for the semi-discrete transport problem, while Section 3.3 addresssss a quantization problem in which both the weights and locations of the discrete marginal are jointly optimized to minimize the total transport cost.
3.1 A dual formulation of weak optimal total variation transport
We first introduce some technical notations. For metric space X, we denote by Cx(X) and B(X) the space of bounded continuous real functions and Borel real functions on X, respectively. A metric space X is Polish if is complete and separable.
Definition 3.1. We say that measurable map C:: x:X1xPII x(x2) + (-00, +oo] has property (T) ffr every M >> and every sequence {T"") JNEN C. (M x X2) such that Jx, C(Z1, 22, ddy (z1) $ M for all n E N, the sequence {><) Jeen is tight.
Let X1, X₂ be Polish metric spaces, and let C: X, P(X2) + (-00, +oo] be a lower semicon- tinuous function that is bounded from below and satisfies property (T) as defined in Definition 3.1 These assumptions on are nearly minimal and encompass commonly used cost functions as special cases. Assume further that (b, + b2)/2 + inf C > O. Before proceeding to duality and optimality conditions, it is essential to establish that the unbalanced weak OT problem admits a solution. The following theorem guarantees the existence of an optimal transport plan under these mild conditions.
Theorem 3.1 (Existence of optimal solutions). Let μs E M(X.), for i = 2 and suppose that problem ① feasible. Then the problem (I) has least one optimal plan.
We now proceed to derive the dual formulation of the primal problem (T). which, as previously noted, constitutes critical intermediate step in our theoretical development. To elucidate the geometric role of the TV penalty in the weak formulation, we begin by introducing family of auxiliary functions T, and J; for i = 1,2, along with the corresponding admissible function classes 4 and & J. These constructions will be used in the strong duality result presented in Theorem 3.2
5

---

For each i = 1, 2, we define the functions 1, R - (-oc, too
[(()) inf ssp + a1 +) + bbi 1)t) a1 (0>01) ( (00
+20
12(x) :- inf + az - -)* + ba(s 1)t) 02 (+>02) + + - +20
-01(p<<b)))
(3)
Likewise, we define the conjugate-type -tpe functions J J - (-00, too
Ji(Ø) sup (1 8)+ - b1(s 1)+
(d201) (-biosal) (
+>0
8
a2(1 8) - bb(s- - -1)+ +o0l + (- (2c
J2(Ø) sup
=>0
Using these functions, we define two sets of admissible test functions:
p == ((111112))111111 e (x()) Cx(X2) -b I (1()), (aoz))-ba -b I (2((2)) for every x; E X 1,2 and (211) + p((2)) - C(z1,)) for every 21 E X1,P E P(X2)}
2 ((P1) E ((()) x (X2) (2())) S 01 (2(22) S ag for every o; E X,, 1,2 and J1 ( ((22(12)) & C(x1,1) for every in E X1,P E P(X2)) +
Theorem 3.2 (Dual representation). Suppose that for every Iı E X1, C(an,) P(X2) 7 (-o0, +o0 is convex. Then for every μi E M(X.), 1,2, we have
ck. k (11, = sup (P1:F2)E
Σ
p:d14= = sup / 1=1 X.
EL I(pp(()))d)a......
Remark 3.1. A similar dual representation has been established in the case where both Xı and X₂ are compact [22] Theorem 2]. Extending this result general (non-compact) spaces, however, is nontrivial, primarily due to the presence of non-superrinear, newsvendor-tye penalties, which are motivated by practical considerations. In this work, we adopt a different proof strategy from that used in (22 Theorem 2] to accommodate these challenges.
Such a dual perspective plays a central role in the modern development and application of OT theory, owing to both its theoretical and practical ad advantages. On the theoretical side, the dual formulation provides essential structural insights, such as the characterization of optimal plans through Kantorovich potentials (491, (P2) and the derivation of necessary and sufficient conditions for optimality. On the practical side, it often leads to more computationally tractable formulations. Notably, the dual representation established in Theorem 3.2 very general, and it partially recovers 43 Corollary 4.12) when C(I1,P) = k c(x) x2 dp and the entropy functions are given by a1 -1 +)+ + b,(s 1)+, 1 1,2, as stated in the following corollary.
Corollary 3.1. Let X1 x X2 + (-o0, +oo] be a lower semicontinuous function that bounded from below and has compact sublevels. Suppose that (b, + b2)/2 /2- + kinf c. > 0. Then, for every Hs &M(X)), 1,2, we have
gki ke ((1,H2))))) = sup (91)2)EE 1=11
pidpy = sup (9IWo))Ed i=] X.
Σ
/ [(P((=))d)(x.)),
X.
where the admissible sets A, and A₁ respectively defined as A, {(p1, (22 Ca(X1) x
Cx(X2)= (x1( < a1, (2(22) < 02, Ji + (2((2((22) < k c(11, for every 21 E X1, x2 and As = (()1,)22)
C((Xi)xxs((X) (22(22) < k ((x1, for every E X1,42 E X2).
(x((x) 2 (21,22(22) 2 b2, 1p (x1)+
In what follows, rather than deriving the optimality conditions directly under the general framework of Theorem 3.2 which is straightforward but offers limited intuitive insight, we shift our focus to more practically relevant semi-discrete settings. This allows for clearer theoretical development and facilitates meaningful applications, particularly in the context of spatial resource allocation.

---

3.2 Semi-discrete unbalanced total variation transport
Here, we consider semi-discrete scenario under the problem formulation ( where the first marginal is continuous and the second marginal is discrete. Specifically, we let μr E {M(1) be absolutely continuous with respect the Lebesgue measure, and define μ22 Σ i=1 m;dy, E M((2) for some given integer M > O, where 6y, denotes the Dirac measure centered at yi- Examples arising in spatial resource allocation, such as the placement of e-commerce warehouses or public facilities like schools, naturally fit within this framework. In such settings, the discrete points represent service stations (i.e., supply locations), while the continuous measure models the spatial distribution of service demand across the region. We first introduce several new notations or concepts that will be used later. For any a, b IR, we denote a 6 max a. b}. Let
M
be any given integer. and let X1 and X₂ be subsets of IR.. Assume that (b1 + b2)/2 + k inf e >> O and has compact sublevels. In both Sections 3.2 and 3.3 we further assume that e radial according to the following definition (see also (15]).
Definition 3.2. A function e: X1 x X2 - (-x;, +oo is radial if it can be written as c(r, = g(d(z, v)) with a continuous, strictly increasing function g [0, + + [0, +oo] satisfying g(0)
Beyond its practical significance, the semi-discrete setting is of theoretical interest due to the special geometric structure of its solutions. In particular, the optimal transport plan induces a cell decomposition of the domain, which is both mathematically elegant and operationally interpretable.
Definition 3.3 (Generalized Laguerre cells, (15). Given transportation cost X1 x X2 - (-oo, +o0] and y1, .UM E X2, we define the generalized Laguerre cells corresponding to the weight vector w E IR as follows: for i E {1....,M}
Ci(w) = fx X1 c(x, ys) < +00, c(x, Vs) The residual set, denoted by R, is defined as R {x E X1 c( ys) - +20
S c(I, w for all E MM,...,M).. (4)
The next theorem recasts the dual functional from Theorem 3.2 as
optimization
over the weight vector w associated with the cell division, thereby reducing the original infinite-
dimensional problem over Kantorovich potentials to more tractable finiteddimensional setting.
Theorem 3.3 (Dual tessellation formulation). Suppose that problem is feasible. Then
kk (11, (22 = sup {g(w)]w- = (WI,..., E b2, M)
(5)
where
M /
M 12(w)) m
((w) Σ
I1(bi v c(.c - w:))dui (2) + aaai +
i=1 C((w)
1=1
- =1( S 11(c"
M (I) Σ l2(w:)m
(6)
with c X2 + (-o0, +oo defined by et (x) [= -b V min (k c(x, v.) - w. (=I....M
Equation (6 reveals that the reformulated dual objective G admits an explicit and tractable dependence on the weight vector w, facilitating algorithm design for identifying the optimal weights. Building on Theorem 3.3, we now proceed to establish the corresponding optimality condition.
Theorem 3.4 (Optimality conditions). Suppose that X₂ [y),.... yMM) } and problem Let y M(X, X2) be an optimizer for problem 2 and w (W1, .M)) E
2 is feasible. [- + be
an optimizer for problem ( Then y admits the form y EE nN @ 8y, for t E M(Xi),
dr
1 1,..., M. The Lebesgue decomposition of with respect to in is n = Ei Ti dun Mn + 7
Define S := {i E (1....M} m, + 0} and S2 = ii E {1, M} m, 0). Then the following conditions hold:
M
T/ = (w) every i = 1,, I,...,M M (i.e.,
== Σ
MLC,(w) 8 6,
(7)
where (LC)(w) denotes the restriction of to the cell C:(w), and
d11 d')(x) (x) = 1.for aie x E R, d (x) = forpuraeeee.mm I E R,
(8)
du1
du
7

---

mal m, for all E St, (² - for for d.e. I ZE R.
(9)
Wi = bb for every E S2.
(10)
Conversely, if and w satisfy
10
then they are optimal solutions to and 5 respectively.
The first marginal of the optimal transport plan comprises two components: an absolutely continuous part with respect to the input marginal J4i, and singular part that arises due the piecewise-linear TV penalty, which differs from [15. In particular, the optimality conditions established in Theorem 3.4 enable efficient recovery of the optimal transport plan the optimal weight vector w² has been determined. The latter can be computed using gradient- gradient-based based methods, as the exact (sub-) )gradier of the dual objective ((w) with respect to each wy is explicitly available and presented below.
Proposition 3.1 (Gradient dual tessellation formulation). G defined in (6) from Theorem 3.3 buu--Jdiferrentiale with respect to each wi and
(w) n x k- c(2, yi) #1 (C
wi [bb a1 x cx. yk) wi bi. a1
+ ma.
E (-b2, 02), wy E {az), E (a2, +00).
gw:9(w)
[0, m.],
(
x
k-
cl Mc) w; b-b,,000 an
Remark 3.2. It is clear that ((w) decreasing in wi over (az, +o0). Therefore, for fixed values of (w)))46 the maximizer of (5) with respect to w, must lie within the interval (-b2, 02].
3.3 Optimal spatial resource allocation
In the previous subsection, both the locations and masses of the discrete measure were fixed, and the objectíve determine a service area partition. We advance the analysis by formulating quantization problem in which the locations and masses are jointly optimized to minimize the overall transport cost. This extension naturally connects practical applications such as facility location and resource allocation. Specifically, we adopt a sequential optimization strategy: we first optimize the mass vector while holding the locations fixed, leveraging the optimality conditions established in Theorem 3.4, and subsequently update the locations to further reduce the aggregate loss.
Theorem 3.5 (Optimal masses given locations). Given fixed cardinality M and fixed support points y1.-.- UM X2, define
Q ... .MM) = min gky ( 122
M
m&g my mm > o0. (11)
where Eki Sk..k..& P2) is defined in with 7 runs over M(Xi x (yi...., yy5)) )). Assume that (0)) > for every 1,..., M. where O is the M M-dimensional zero vector. Then the satisfying m = (C((())) > 0 for every = I...,,.. M.
minimizer of (TT is Moreover, we have
M 1 V - Σ I c.(0)
Qu ,UM)
yM)
aipi (R).
(12)
To complete the quantization procedure, it remains to optimize over the locations of support points. Based on Theorem 3.5 this amounts to solving the following location optimization problem:
min (Q(11. .UM) y1. yM X2),
where Q yM) ) is defined in This optimization can be carried out efficiently using gradient-based methods 33
as the necessary gradients are derived and provided below.
Proposition 3.2 (Gradient of quantization objective function). Assume the cost function e X, x X2 - (-oo, +oo) is differentiable with respect to its second argument, and denote its gradient by V ,,c(x, 1)- Assume that (O)) > ffror every I,..., M. Then, for each = I.... M, the gradient of the quantization objective Q(y yar) with respect to Yi is given by
V, Quv, .UM) =k
V clz, (x).
8

---

4 Numerical examples and illustrative applications
Given our primary foeus establishing rigorous theoretical framework and the space limitations, we illustrate the practical relevance of our results through two representative application scenarios with numerical examples, Further exploration of additional applications is left for future research.
4.1 Supply area division
We demonstrate the application of Section 3.2 through a spatial supply-area division problem. An urban planner must allocate m= 4 fixed emergency depots Y {y: j==1 C [0, 1] to serve incident locations distributed continuously over X c 00 1J2 with density μr. The total incident mass is normalized to M₁ = 1, while the available standby capacity is limited to M, 0.7, represented by the discrete measure V = m vidy,, with >, 142 = 0.7. Travel cost is set to the Euclidean distance.
Semi-discrete. The demand distribution μ is continuous, while supply is concentrated at finitely many depots (v). The tessellation-baal based dual formulation thus applies directly.
Unbalanced. Since Mp * My, only fraction of incidents can be served. The optimization identifies where to allocate supply and where forgo service. We set j be uniform and initialize i randomly.
TV penalty. Asymmetric newsvendor parameters are set to 01 = 1, bj = 0.5, and 02 b2 = 0, penalizing undersupply at rate by and oversupply at rate d1- We further let k = 1.
Proposition 3.1 provides the sub-gradient g(()) = clip - u(C((w))), which we use in gradient descent algorithms with decaying step size 04 = o + 1) decuy, where og = 0.05 and decay 0.6. The algorithm stops after 1000 iterations in 0.9 seconds. The final supply-area partition, determined by the optimized weights {m=]]__]- is shown in Figure [ This example highlights the practicality of the dual formulation and subgradient structure from Section 3.2 in addressing semi-discrete, unbalanced, and asymmetrically penalized transport problems.
1.0
6.02
Vases dfiua potoriida Mi
(0C),
Mas5 minratee Enit -
2.8
6:52
0.42
0.4
2.42
0.2
0.25
0:35
30
0:30
0.
250
350
1300
530
Discwte
heraabore
(a) Laguerre cells
(b) Values of
(c) Gradient convergence
(d) Mass mismatch
Figure 1: Fig. (a) displays the resulting supply-are area partition, with black crosses indicating depot locations. Fig. (b) presents the learned dual weights wy E [-1, 1]. Figs. (c) plot the l norm of the gradient and the total mass mismatch Σ, (C(C. - 1/sl
4.2 Spatial resource allocation
This experiment extends the previous example by endogenously selecting the depots, echoing
Section 3.3 Specifically, we now optimize the positions Y ) C [0, 1 along with the dual weights W;, and the optimal mass allocation is determined by Theorem 3.5 Each point
assigned to the depot minimizing the effective cost =(x, = c(x, v1) wi If the minimal cost exceeds the threshold d1, this point is assigned to the residual set R, incurring a penalty of a (R)). a cell (.(w) = {ar : i(x, < =(x,j), Vj} becomes empty, the corresponding weight is set to Wi = bbg effectively deactivating the facility. The resulting outer objective, Q(y) = E.Scrww z(x, i) du((x) + (R), matches the form addressed in Theorem 3.5
Setting. We sample N = 2000 incident locations from a two-component Gaussian mixture with means (0.3, 0.3) and (0.7, 0.7), and covariance 0.02Iz. Samples are clipped to [0. 1 and rescaled to ensure M,, = 1. The number of depots is fixed at m = 4, with initial positions drawn i.i.d. from
the uniform distribution on (0, 1j2. Newsvendor parameters are set to 01 0.3, d2 = 1, by = 0.1, and b2 0.2. The choice of smaller aj encourages visible residual mass, while the ordering

---

b1 <b² a1 conforms to the structure of the folded loss I1 A decaying step size 0.3/ + t)0.6 is used. The CPU running time 2.6 s, and the results shown in Figure souureeconfmm that the outer-inner decomposition prescribed by Proposition yields an effective gradient-based solver.
Partion
Hadical Hiad di:
0.10
2.00
1000
2002
3500
5.2
0.
12 0.
06
0.3
5.3
5.8
15
Seratons
(a) Convergence results
(b) Trajectories y/
(c) Initial partition
(d) Final partition
Figure 2: Fig. (a) plots the objective (vy (blue) and the residual mass μa( Rt) (orange), which stabilizes around 0.05, indicating that approximately 5% of demand is optimally left unserved due to excessive transport cost. Fig. (b) illustrates the trajectories of the four depots: arrows trace movement from random initial positions toward demand clusters. In Fig. (c), the initial location of depots (black "x") and the nearby demands partition the entire area into several distinct parts (in different colors), which resembles a Laguerre diagram. In this partition, the demands within each Laguerre cell are serviced by the depot of the same color. However, there still areas with high-density demands (gray" "x") falling into the residual set R. After optimization, Fig. (d) shows four depots concentrating near high-density regions, while low-demand areas are absorbed into R, reflecting TV-induced saturation.
Conclusion and future work
This paper presents comprehensive theoretical framework for unbalanced weak OT problems with total-variation penalties. We establish general dual formulation that encompasses many existing models as special cases. We then focus on the semi-discrete setting, motivated by spatial resource allocation applications, and show that the problem admits Laguerre tessellation structure. This allows for explicit optimality conditions and next-level tractable quantization procedure. While our primary emphasis is on theoretical development, we include preliminary numerical examples demonstrate the framework's applicability. We anticipate that this foundation will support future extensions in both theory and practice.
Acknowledgments and Disclosure of Funding
Nhan-Phu Chung funded by University of Economics Ho Chi Minh City, Vietnam. Jinhui Han is supported in part by the National Natural Science Foundation of China (Project "Data-Driven Operations Analytics Methods") and "The Fundamental Research Funds for the Central Universities, Peking University". The authors thank the anonymous reviewers for their comments.
References
[1] Pankaj Agarwal, Sharath Raghvendra, Pouyan Shirzadian, and Keegan Yao. A combinatorial algorithm for the semi-discrete optimal transport problem. Advances Neural Information Processing Systems, 37:25857-25887. 2024.
[2] J.-J. Alibert and Champion G. Bouchitté. A new class of costs for optimal transport planning. European Journal of Applied Mathematics, 30: 1229 1263, 2019.
[3] Jason M Altschuler, Jonathan Weed, and Austin J Stromme. Asymptotics for semidiscrete entropic optimal transport. SIAM Journal on Mathematical Analysis, 54(2):1718-174) 2022.
[4] Luca Ambrogioni, Umut Gügliü, and Marcel van Gerven. k-gans: Ensemble of generative models with semi-discrete optimal transport. arXiv preprint arXiv: 2019.
[5] Dongsheng An, Yang Guo, Na Lei, Zhongxuan Luo, Shing-Tung Yau, and Xianfeng Gu. AE-OT:
A new generative model based on extended semi-discrete optimal transport. ICLR 2020, 2019.
10

---

[6] Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. International Conference on Machine Learning, pages 214-223. PMLR, 2017.
[7] Julio Backhoff- Backhoff-Veraguas, Mathias Beiglböck, and Gudmun Pammer. Existence, duality, and cyclical monotonicity for weak transport costs. Calculus of Variations and Partial Differential Equations, 58(6))003, 2019.
[8] Julio Backhoff- Backhoff--Veragus and Gudmund Pammer. Applications of weak transport theory. Bernoulli, 28(1):370-394, 2022.
[9] Julio Backhoff- Veraguas and Gudmund Pammer. Stability of martingale optimal transport and weak optimal transport. The Annals of Applied Probability, 32(1):721-752, 2022.
[10] Yogesh Balaji, Rama Chellappa, and Soheil Feizi. Robust optimal transport with applications in generative modeling and domain adaptation. Advances in Neural Information Processing
Systems, 33:12934 12944, 2020.
[11] Mathias Beiglböck, Gudmund Pammer, Lorenz Riess, and Stefan Schrott. The fundamental theorem of weak optimal transport. arXiv preprint vrXiv22511.16316 2025.
[12] Mathieu Blondel, Vivien Seguy, and Antoine Rolet. Smooth and sparse optimal transport, 2018.
[13] Vladimir Igorevich Bogachev. Measure Theory, volume 2. Springer, 2007.
[14] Clément Bonet, Kimia Nadjahi, Thibault Sejourne, Kilian Fatras, and Nicolas Courty. Slicing unbalanced optimal transport. Transactions on Machine Learning Research, 2024.
[15] David P Bourne, Bernhard Schmitzer, and Benedikt Wirth. Semi-discrete unbalanced optimal
transport and quantization. arXiv:1808.011 01088.0962,,. 2018.
[16] Wanxing Chang, Ye Shi, Hoang Tuan, and Jingya Wang. Unified optimal transport framework for universal domain adaptation. Advances in Neural Information Processing Systems, 35:295 12- 29524. 2022.
[17] Laetitia Chapel, Rémi Flamary, Haoran Wu, Cédric Févotte, and Gilles Gasso. Unbalanced opti- mal transport through non-negative penalized linear regression. Advances in Neural Information Processing Systems, 34:23270-2333 23282,, 2021.
[18] Yucheng Chen, Matus Telgarsky, Chao Zhang, Bolton Bailey, Daniel Hsu, and Jian Peng. A gradual, semi-discrete approach to generative network training via explicit wasserstein minimization. In International Conference on Machine Learning, pages 1071-1080. PMLR, 2019.
[19] Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavies Vialard. An interpolat- ing distance between optimal transport and fisher-rao rao metrics. Foundations of Computational Mathematics, 18:1-44, 2018.
[20] Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François Xavier Vialard. Scaling algo- rithms for unbalanced optimal transport problems. Mathematics of Computation, 87(314):2563- 2609, 2018.
[21] Jaemoo Choi, Jaewoong Choi, and Myungjoo Kang. Generative modeling through the semi- dual formulation of unbalanced optimal transport. Advances in Neural Information Processing Systems, 36:42433-42455, 2023.
[22] Nhan-Phu Chung and Thanh- Son Trinh. Weak optimal entropy transport problems. Potential Analysis, 2025 to appear.
[23] Nicolas Courty, Rémi Flamary, Devis Tuia, and Alain Rakotomamoniy. Optimal transport for domain adaptation. IEEE Transactions on Pattern Analysis and Machine Intelligence,
39(9):1853-1860 2016.
[24] Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in Neural Information Processing Systems, 26, 2013.
[25] Nabarun Deb, Promit Ghosal, and Bodhisativa Sen. Rates of estimation of optimal transport maps using plug-in estimators via barycentric projections. Advances in Neural Information Processing Systems, $4:29736-29755 2021.
[26) Vincent Divol, Jonathan Weed, and Aram-Alexandre Pooladian, Optimal transport map estimation in general function spaces. arXiv preprint arXiv:2212.03722, 2022.
11

---

[27] Ivar Ekeland and Roger Témam. Convex analysis and variational problems, corrected reprint of the 1976 english edition. Classics in Applied Mathematic, 28, 1999.
[28] Kilian Fatras, Thibault Séjourné, Rémi Flamary, and Nicolas Courty. Unbalanced minibatch optimal transport, applications to domain adaptation. In International Conference on Machine Learning, pages 3186-3197. PMLR, 2021.
[29] Jean Feydy, Thibault Séjourné, François-Xave Xavier Vialard, Shun-ichi Amari, Alain Trouvé, and Gabriel Peyré. Interpolating between optimal transport and MMD using sinkhorn divergences. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2681-2690. PMLR, 2019.
[30] Aden Forrow, Jan- Chrishitttia Hütter, Mor Nitzan, Philippe Rigollet, Geoffrey Schiebinger, and Jonathan Weed. Statistical optimal transport via factored couplings. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2454 2465. PMLR, 2019.
[31] Promit Ghosal and Bodhisattva Sen, Multivariate ranks and quantiles using optimal transport: Consistency, rates and nonparametric testing. The Annals of Statistics, 50((): 1013::101 2022.
[32] Nathael Gozlan, Cyril Roberto, Paul-Marie Samson, and Prasad Tetali. Kantorovich duality for general transport costs and applications. Journal of Functional Analysis, 273(11))3327-3405 2017.
[33] Jinhui Han, Xiaolong Li, Suresh P Sethi, Chi Chung Siu, and Sheung Chi Phillip Yam. Produc- tion management with general demands and lost sales. Operations Research, 12(5):15511174,, 2024.
[34] Jinhui Han, Suresh Sethi, and Tingjin Yan. Production and risk hedging with cointegration analytics. Available at SSRN 52/9499, 2025.
[35] Nhat Ho, XuanLong Nguyen, Mikhail Yurochkin, Hung Hai Bui, Viet Huynh, and Dinh Phung. Multilevel clustering via wasserstein means. In International Conference on Machine Leurning, pages 1501-1509. PMLR, 2017.
[36]
lan-Christian Hütter and Philippe Rigollet. Minimax estimation of smooth optimal transport maps. The Annals of Statistics, 49(2), 2021.
[37] Jinyang Jiang, Jinhui Han, Yijie Peng, and Ying Zhang. Closing the loop: Coordinating inventory and recommendation via deep reinforcement learning on multiple timescales. arXiv preprint arXiv22510.04272, 2025.
[38] Michael Kupper, Max Nendel, and Alessandro Sgarabottolo. Risk measures based on weak optimal transport. Quantitative Finance, 25(2):163- 2025.
[39] Harold J Kushner and G George Yin. Stochastic approximation and recursive algorithms and applications. Springer, 2003.
[40] Zehao Li and Yijie Peng. Eliminating ratio bias for gradient-based simulated parameter estimation. arXiv preprint arXiv:2411.12995 2024.
[41] Zehao Li and Yijie Peng. A new stochastic approximation method for gradient-based based simulated parameter estimation. arXiv preprint arXiv:2503.18319 2025.
[42] Matthias Liero, Alexander Mielke, and Giuseppe Savaré. Optimal transport in competition with reaction: The Bellineer-kattroovie distance and geodesic curves. SIAM Journal on Mathematical Analysis, 48(4):2869 2911, 2016
[43] Matthias Liero, Alexander Mielke, and Giuseppe Savaré. Optimal entropy-transport problems and new hellinger-kantorovich distance between positive measures. Inventiones Mathematicae, 21 ((3):969-1117) 2018.
[44] Tudor Manole, Sivaraman Balakrishnan, Jonathan Niles-Weed and Larry Wasserman. Plugin estimation of smooth optimal transport maps. The Annals of Statistics, 52(3):666-998 2024.
[45] Debarghya Mukherjee, Aritra Guha, Justin M Solomon, Yuekai Sun, and Mikhail Yurochkin. Outlier-robust optimal transport. In International Conference on Machine Learning, pages 7850-7860. PMLR, 2021.
[46] Boris Muzellec and Marco Cuturi. Generalizing point embeddings using the wasserstein space of elliptical distributions. Advances in Neural Information Processing Systems, 31, 2018.
12

---

[47] Boris Muzellec, Adrien Vacher, Francis Bach, François- Pranvois-Xavier Xavier Vialard, and Alessandro Rudi. Near-optimal estimation of smooth transport maps with kemel sums-of squarss...... SIAM Journal on Mathematics of Data Science, 2024.
[48] Kalyanapuram Rangachari Parthasarathy. Probability Measures on Metric Spaces, volume 352.
American Mathematical Soc., 2005.
[49] Michaël Perrot, Nicolas Courty, Rémi Flamary, and Amaury Habrard. Mapping estimation for discrete optimal transport. Advances in Neural Information Processing Systems, 29, 2016.
[50] Nicholas C Petruzzi and Maqbool Dada. Pricing and the newsvendor problem: A review with extensions. Operations research, 47(2):183-194, 1999.
[51] Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends in Machine Learning, 1 11(-6))355-6077, 2019.
[52] Khiem Pham, Khang Le, Nhat Ho, Tung Pham, and Hung Bui. On unbalanced optimal transport:
An analysis of sinkhorn algorithm. In International Conference on Machine Learning, pages 7673-7682. PMLR, 2020.
[53] Benedetto Piccoli and Francesco Rossi. Generalized wasserstein distance and its application to transport equations with source. Archive for Rational Mechanics and Analysis, 21 1:335-335,, 2014.
[54] Benedetto Piccoli and Francesco Rossi. On properties of the generalized wasserstein distance. Archive for Rational Mechanics and Analysis, 222: 1339-13-,,,,, 2016.
[55] Aram-Alexandre Pooladian, Vincent Divol, and Jonathan Niles-Weed. Minimax estimation of discontinuous optimal transport maps: The semi-discrete case. In International Conference on Machine Learning. pages 18128-281555 PMLR, 2023.
[56] Aram-Alexandre Pooladian and Jonathan Viles-Weed. Entropic estimation of optimal transport maps. arXiv preprint arXiv:2109. 22004, 2021.
[57] Meyer Scetbon, Michal Klein, Giovanni Palla, and Marco Cuturi. Unbalanced low-rank optimal transport solvers. Advances in Neural Information Processing Systems, 36:52312-5220 52325, 2023.
[58] Thibault Séjourné, Gabriel Peyré, and François-Xavier Vialard. Unbalanced optimal transport, from theory to numerics. Handbook of Numerical Analysis, 24:407-471, 2023.
[59] Justin Solomon, Fernando De Goes, Gabriel Peyré, Marco Cuturi, Adrian Butscher, Andy Nguyen, Tao Du, and Leonidas Guibas. Convolutional wasserstein distances: Efficient optimal transportation on geometric domains. ACM Transactions on Graphics (ToG), 34(4):1-11, 2015.
[60] Adrien Vacher and François-Xavia Vialard. Semi-dual unbalanced quadratic optimal transport: fast statistical rates and convergent algorithm. In International Conference on Machine Learning, pages 347744-44778.. PMLR, 2023.
[61] VS Varadarajan. Measures topological spaces. Matematicheskii Sbornik. 1961, vol. 55, pp 35-100 (in Russian). American Mathematical Society Translations: Series 2, 48:1611-28 1965.
[62] Tomas Vaskevicius and Lénaic Chizat. Computational guarantees for doubly entropic wasser- stein barycenters. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 12388-12388. Curran Associates, Inc., 2023.
[63] Jun Wang, Bohan Lei, Xiaoyin Xu, Yueting Zhuang, and Min Zhang. A novel conditional medical image generation gan with latent space optimal transport. In 2023 IEEE International Conference on Medical Artificial Intelligence (MedAl), pages 453-458. IEEE, 2023.
[64] Chang Xiao, Peilin Zhong, and Changxi Zheng. Bourgan: Generative networks with metric embeddings. Advances in Neural Information Processing Systems, 31, 2018.
[65] Karren D Yang and Caroline Uhler. Scalable unbalanced optimal transport using generative adversarial networks. arXiv preprint arXiv:1810.11447. 2018.
[66] Zhenyi Zhang, Tiejun Li, and Peijie Zhou. Learning stochastic dynamics from snapshots through regularized unbalanced optimal transport. arXiv preprins 14X00:2410.008444, 2024.
[67] Yi Zheng, Zehao Li, Peng Jiang, and Yijie Peng. Dual-agent deep reinforcement learning for dynamic pricing and replenishment. arXiv preprint arXiv:2410.21100 2024.
13

---

[68] Fan Zhou, Shikai Luo, Xiaohu Qie, Jieping Ye, and Hongtu Zhu. Graph- braph-based equilibrium metrics for dynamic supply-demand systems with applications ride-soureing platforms. Journal of the American Statistical Association, 1688536)):88881666 2021.
A Proofs of assertions in Section 3
A.1 Auxiliary lemmas
Lemma A.1. Let X be metric space and M2, M(X). Then
1(42 v2) 1002 22) [(12 μ2 1/2 112++1
Proof. The results follow from that
- (m)- + (#2 - 12)
[4] - vi + 1/2 - U2 + ln + 122 U2
2
2 2
141 + P/2 (n1 + v2) + in + 12 - (01 + v2)
(M1 + μ2 (vi + +z2)
Lemma A.2. Let X be a metric space and μ,, v E MM)). Then
1(u - +)+ 2 (n(X) - v(X))*
Proof. Let = Sp + wt be the Lebesgue decomposition of with respect to p. Then
(44 - 2 = (((1 - f) f
/ f)
2 / (11 - 1-1+1- S)dp
1
2 (1. (1 (1- + + (1 (1 f)df)
1
(J (1 (1- -ddy (1-dd))
= (m(X) *(
Lemma A.3. Let eı and 02 be non-negative numbers. We define the map J R (-o0, +00 by
C1 8)+ -2(8 1)+
too
if c1
J(p) sup 2>0
④
if - o S C1,
-02
otherwise.
Then for every v, P E M(X) we have that
allu~vソ+ 02 (v / pdp / H(())d,,
for every ip E B(X) satisfying that suprex (xxx== cI.
Proof. The statement is true for the case μ are the null measure. Therefore, we can assume
that (n + (X)
Let be the Lebesgue density of with respect to / + u. We define V = 1 e X < h(x) 1}, Vp = {o X h(x)) 0} and V, {I X h(x) 1}. Then
14

---

(V, n: V2) is Borel partition of X. We define the Borel functions f on X by f := h
1- on V.
and f = 0 on X \ V. Then V = fp + v² v (X Vo) - ((V2) = Then
- (1(1-~)+
- - ffpp + + c2l1(f - -1)
=c1 J (1 (1- [xIve -5-1)
1) dp (V))
XXV
xiv,
By the definition of J we get that c1(1 -)+ + c2(s - 1)+ + -J(()) - -p 2 0. Hence for every
4 (() with supxex fox) ci we have that
allu w)t +2llu- 1 / sdlu + / J(D)du
29 / (1- (1= [ dul c0z [[ [/u0 (1-1) + Jrc do-t d sodu + S., sody
(J(D)du [e. ((s)dutt)
/ (q(11 - fJ+ + czlf 1)+ + fJ(()) - +d)du+ + / (ar - sddp + / (c2 + ((1)))
20.
A.2 Proof of Theorem 3.1
Before proving Theorem 3.1 let us provide examples of the function C X, x P(X2)
(-o0, +oo] having property (T) (see Definition 3.T). Recall that for a metric space X, {v") JUEN C
M(X) is tight if for every e 0, there exists compact subset K₂ of X such that v ""X Ke) <e for every n E N.
Example A.1. Lete: X1 x X2 + (-o0, +oo be measurable function. Assume that e has compact
sublevels, i.e. for every L I. the subset {(11, 22) X1 x X2 c(11, L} of X1 x X2 is compact. We define the map
-0,0, by C(x1,)) Ixg x2)p((2) for every iı E X1, and p P(X2). Given M > 0 and let heN C MM x X2) such that Jx, C(a th (d)) S M, for every n E For every L> 0, the set
C: X1 P(22)
Al ((01, E X1 X X2 :(()) S
is compact. Since
1 Jx (2,, (11, = J/ (11, (22)d = / C(ai, (d)
for every L > 0, we have
Sxixx, odyy
Jx, C( (aj (dy
M
((X, X2) Ar) S
S L
L
M
For every E > O, choose > such that Therefore, the map C has property (T).
< e, then 7" ((X1 x X2) \ AL) < E, for every n E N.
L
Example A.2. IfC(#1,)) a .x, c(21, (2)1xx))d((x))) for every 2ı X,, P
E P(X2) for some
non-decreasing function (o0, + (-20, t20), and has compact sublevels, then C has property (T))
Example A.3. If X1 and X2 are compact, then every measurable map C X1 x P(X2) 4 (-o0, +oo] has property (T).
15

---

Proof of Theorem
3.7 Let
InEN C M(X1 x X2) such that Ec(u1, M2)
limm-2o0 220
ETc
11 p2).
First, we will prove that {rr) is bounded. Choose to 2 0 such
that Fi(()
b and
(2(s)
b2
for every to, where F.(s) a;(1 -)+ bi(s 1)+ Now
2
we will show that
2 M
(X1 X2) S
FT
(T for all yh with (X1 X2) 2 max (an p2 (x2));
(13)
d1 +
b2
where M ==
+
inf Cnf > 0. Let 7" with (X, x X2) 2 to max M2))
2
2
M2 = then Fi Fi(77
> 0 then by the choice of to and Lemma A.2 = (x)) If (1
get that
F(()8())) 011(11 + -
2 aalui( (X1) - (x bi ( (x)
m((i a1 (1 (XL)
+ b1 (x())) -1
+7
]
141 (Xi)
(i(())
-Xi( (X11
(xx)
mi (X1)
2 >xi) b
z/2
(Xi x X2) bi
Therefore, (1(1
for all 7"h with yx(X1 X2) 2
bz for all H2 and
to ma (X1), P2 P2 (X2)}. Similarly, Fo(72 u2)
2 ("(,, x X2)
y" with (X1 X2) 2 to max(21(X1)) 22 (X2)). Then for all 7 with ("1 x X2) Z to max( (2(()))))))))) we have that
ET k2 (> (11, u2) = Fi(Tf(m)) + F2(1)lu2) + f ((z1.
Xx1
bi
by + inf C). in..).
2 (Xi x Xa)(
2 2
Hence we get that (>r) JeEN is bounded.
2 ("( x X²) < ("TT))""4, for all yhs with (X x X2) 2 to max(fr (2
M
(14)
Now we will prove that (Yn JYnn is tight. There exists K > 0 such that ET& ( (n" M22 < K and hence Jx, C(#1, 72, )dh,' (21) S K for every n. Since C' has property (T), we get that {> is tight. As (>") is tight and bounded, there exists 70 E MMXi x X2) and subsequence of {>/} which is still denoted by {r"} such that 7nh converges weakly to y² From (42 Corollary 2.9] and (22 Lemma 4] we get that the map 7 + (2)) lower semicontinuous. Therefore, 70 an optimal plan of problem (..
Remark A.1. IfC nonnegative, we can prove the boundedness of {Tr) easier as follows. Choose < M for every N. First, we will prove that {rr" } is bounded.
M > 0 such that ETah (Mml|
As C' is nonnegative we get that ai an](p1 7 + bil(7"" p1 S M for every n E N. Then
h (X)( = [#1 - + + (71 - +1 is bounded. Hence Af (X1) is bounded. Therefore
(r)) ") bounded.
A.3 Proof of Theorem
3.2
Lemma A.4. We have
sup Σ (p1P)))E4) ==1 x;
/ pi (x;)dd((()))= sup
2 Σ I(
(15)
(e i=1
X,
16

---

Proof. For any (41. (2) E P.. we have -h I J1((11(1)) I a1 -by I (((2((22)) S d2 and (1 (z1) (()2((22) S C(T,,)) for every In E XI,P E P(X2). Since J1 and J2 are continuous on (0 01 and (-00, 02), respectively, one has (2((21), E 4y Therefore,
2
Σ / (i(x;)d(;(T.) -
Σ)
/
x;
1=1
Σ
/
I o (i((((())))
Σ / [((0((.))ddx()))
sup
(01.0)) i=1 X.
On the other hand, for any (p1, E 1, we have bi S (((((((1))
12(2((12))
0g and hence J1 I (191(11)) + p(J2 o [2(22)) ) S C(a,,)) p) for every ø1 E X1,pE P(X2). Since I and I2 are continuous on [-b1. 00) and b22 00), respectively, one has (Ii(P)), E Jy. Hence,
2 Σ / 2=1 x,
2
sup (E1) i=1 X (((x))dp((z))
Σ
/
We obtain the result.
Given metric space X, for every μ M(X), the map Tμ Cx(X) + R. defined by f fdu, is a bounded linear operator, i.e., it belongs to (Cx()))*. We define the functional ET (Co(X)))** (Cx(X2))) > [-00, +oo] as follows.
ET (Ti,T2) = { Ec(un
if (Ti, T2) (Tri Tr2), otherwise,
to0
Given v E MM().. =du== fidu for every f E Cx(X) then one gets μ 5.9, page 39]. Therefore, for every metric space we can consider M(X) as subset of (Cx()))* Hence, the map ka.kk is well defined.
48 Theorem
For convenience, we will write ETK (p1, (11, (2) for KT. Tu2) for every (1i, M(X)) x M(X2). The weak topology M(X) is the smallest topology such that for each E Cx(X), the map μ + Jx fdu is continuous, i.c sequence {un)ner C (M(X) converges weakly to j E M(X) if and only lim,-+oo fx fdum = fx fdu for every f f C&(X).
Lemma A.S. Let X1, X2 be Polish metric spaces. Then
1. the functional kT (()a(X))) x (Cx(X2))* + (-00, +o0 is convex and positively homogeneous, i.e. ET (XT,, AET (Ti,T2) for every X O,
(C,((x))** T2 E (X2)))
2. Assume that e has compact sublevels in X1 x X2. Then the function ETki ke is lower vemicontinuous under the weak topology.
Proof. Claim 1: Using the convention that 0 (+o0) = 0. it is clear that kT k2 (0, 0) = 0 and ET (XT,, XT2) = XETk, ku (Tı, T2) for every À 2 0. (Ti,T2) & M(Xx) x M(x2). Hence, to check E ka is positively one homogeneous it is sufficient to check k (XT,,, f1: XTwa) = AE k2 (T 1 Tap) for every À > 0, (2) E M((x) M(X2). Given M(Xi x X2) and
17

---

À > O. We have that
ETk,, (NT xTa)) -ETki,k (Tyus (up2) cky, (Ap)
-inf(ET (k ( : 7 E M(X, x X2))
inf (Arl ApI Av2) :< E M(X, x X2))
inf((al(>vu 1 + bil(A Am1) + a2l(A12 112)
+22((An 1 + / [x1 (d)1)))))))))))) :E EMM( x X2))
=Xinf fail(a 11 bıl(2 ++) (101()2-22)) -12)*
+ bbll(72 - -22)+1+ + / 1(21,7
M(X, x X2))
X2
=XET ko (111
= k2 (T :
By the homogeneity property of (Tkkikk, k2, to show that ETK, ku is convex, we onlyneed to check that
ET (mi, 122 + (T(U,, u2) 2 ET (m + v1, + v2) for every Pis Us E &M(X),, = 1, 2.
We will consider (HI, M2), U2) E M(Xi) x M(X2) such that ETki, (2) < oo and (11, D2) < oo (the other cases are trivial). Let M(X, x X2) such that ETK, ke (21, = lim ET (y" and ETK, ks (v1, U2) =
{T"]REN C
lim ET ETk (<"""1)) v2).
As (dnf//(71' + Ti)) + / + +
is the disintegration of y" + +5 with
E, respect to 7²' -7 and C(x1,-) is convex on P(X₂) for every 21 E X1, we obtain that / X,
S/ X1 (( (x1) +
C(s1, + )d)) + (z)) / X1
((T
Combining with Lemma A.I we have that
kT (4), 12) + ET ka (p), 12)
a ail(m -7) + by |67 a2 - -2)* + b21(72 - =2)+1++ / Clai, (ah
= lim n-000
(1)1112277)1++100)) b2 12)+1+ / C(11, Dett (a1)
+ +ail(11
+1 - 11) a2
-
lim n=000
ail(m + - (1" + イ)) + b + 71 (w) + + + (>i + +
+ bal(?" + 7 (mn un) ) 1 / C(a,,(1 ((on,(("**")),)))) )d() +17)(a))
>ET (i) + V1, + v2).
Therefore, ET is convex.
Claim 2: For i 2, let { C M(X)) such that n="" weakly converges to μu as -+ 00.
To prove k is lower semicontinuous, we need to show that
lim inf ET (u (²) > ET .e (MI, H2).
We only need to check it for the case lim inf ET (JTP: n1) < co. We can choose a subse-
quence (nyleeN such that lim inf ,k (u (u(T)))) = lim k1 (u no , ). For every
j E N, applying Theorem 3.1 there exists y MM(x x X2) such that
ET k. K2 (M N4 H22 ET k2 (7 1
ny 222 for every j E N.
18

---

(7 Then there exists K > 0 such that ETKi,kayy (77"3 114 .122) I K for every j. Hence
Jx, C(21, (a Yai ddy' no (x1) S K for every j. Since C' has property (T) we get that {>") } is tight.
Now we will prove that } is bounded. Choose to 2 0 such that Ei()) for every $ z to. Now we will show that
b and
(2(s) b2
2
2
ymh (X1 x X2) - M
ET k2 (7 "1"","")) for all yns with (X, x X2) 2 to max (X1), (X2)),
(16)
where M = bj + > 0. Let with 7 (X1 X2) 2 tu max max 22 (X2)). If
(X1) = 0 then Fi(m1 " (u = b (X1) If 14 (X1) > then by the choice of to and Lemma
A.2 we get that
Fi 14
= 01
-
(77 - -1
2 a1 (4) (X1) - 11 (xi)) by (1 (X1) - (x))+
1 11- (((((1))
11 (X1) -1) ]
71' (X1)
2 Mi 2y (X1)
+
14 (X1)
N (X1)
(2 (X1) 1 (X1)
= = (x1)
(X))
(x1) bj 2
2 21
b1 2
Therefore, (1 1 (1
(Xi x X2) for all 14 and nn with (Xi X2) 2
P/2 14 (X2)). Similarly, Fe(12 13 (x22) 2 (X1 X2) be to max(u?" (X1),
for all 12 and
2
ynt with 7n (X1 X2) 2 to max (X1), 2 (X2)). Then for all yn with ymh (X1 X2) 2 to max(u] 13 (X1), P1z (X2)) we have that
+ / C(Ll, (x1)
ET k2 (5 |44 p22) = F1 ((") + F2(12"
X,
b1
b
>X1 x X2
+
+ C')
2
2
Hence, we get (6)). On the other hand, far (X₂ (i)}ee JeE and (41² (X2)) are bounded as 14 weakly converges to μ4 for i 1,2. Therefore fy JeeN is bounded. As {-²) byes is also tight, applying Prokhorov's 's theorem there exists a subsequence (7 byeN, still denoted by (7") JeN, and a 27 E M(X, X2) such that yn: weakly converges to 7. Applying [B] Theorem 8.4.7] [6]
Part 2, Theorem 3] we get that
inf 14" 1+x
n nss ((x)) 2 |P1 (x)())
Hence
1
lim infinnll (14) - - = lim inf 5
|n - >xx)(())) + (1T - -27
2
2 |01 - -n1(X)) + (#1 - (x)
= 1(m 71
Similarly, we have
inf (125' - 2/ ) 2 1122 - 72) 3
lim inf (6 - + 2 1 m1)+1
inf [622 - x 2 1(72 #1)+1
19

---

Then
lim inf ET k2 u2)
-lim inf ks (> (7") 112)
n=+00
n=000
lim inf n=
ail(4i n4 71 ) + bil(77 - -17)) + a21(4z" - -
+ bbll( n3 - 112))*+ + / C(zi, ( t4 (m1)
201((u1 -1))+1 bil(n unt + t2ll(u2 - x2
+ b2ll(92 12)+1 + I x2
(h ( (T1)
> ke (1))
Proof of Theorem 3.2 We denote by (E) the Fenchel conjugate of ET i.c.
(ET ( V1 M
(x.)) ET (v1, 12)) }
sup
for every 9i E C,(X), 1.2. By Lemma A.5 we get that
(ET = {
if (12), E EEE +oo otherwise,
0
where
$g = { (121)P2) E (x(i)) Ox(X2): Σ
/ p((x,)du((z;) ke (2) xx
for every (21, E M(X1) x M(X2)
We now check that 4, gg. Let any (2)) E 25. Let is E M(X)), i 1, If cki, (2) = too then it is clear that Ei= Jx, (I,)))du(()) S ET (UI, v2). Thus, we only consider Ek: ka (2) < t00. Applying Theorem 3.1 there exists y MMX,, X2) such that ex ke (2) = (y/p,, Then, applying Lemma A.3 we get that
k (v1, 122)
=a1((11 71) +1 + b1l(11 u1) + t0ll12 - +1 + bel(72 -2))++ + / ((a1))))dd(
2 { vidu - -/8 Ji(l))dm / Podua - / J2((2))))2 + / [J1(p1((11) t (Jd(P)))
Xi
x2
x.
= -/e sides - / J((()))d / podus / J2(122) + / J((()))d)
+
(22)dd((()))
Xi Xx
pidui + /
p2du2 - / J2((22)d12 + / )2((2(())))d2((0))
Xi
X2
= -1n sidni + f 42du2.
x,
Therefore (411. (22) C Dg. Hence Tb C $g.
Now, let (p1,)92) ØF. We will show that (2)) E Φ,,. Denote by n the null measure on Xi X2. As (1I1, v2) E &r. for every (u1, v2) E M(X)) x M((2) one has
((()))des(a)) s k. k2 (11,22) s Ek kk (nlpi, u2) = a |P|| + 12).
20

---

For every E X1, setting := 6₂ and V2 is the null measure on X2, we obtain that 4p (2((2) S a1 Similarly, we also have (p2 I a2 on X2.
Let 21 E 1 and E P(x2). Now we will prove that Ji (21)) + p(]2(122) & C(ai,p) For every r 0, put us = Sr, and y = rdz, @ p. Then for every v2 (M2))) we have
(p(())) + /
podlu = Σ}
Pides
X2
Aml
ET (2)
3 gki k2 (7| 122
= 01(1 - r)+ + b1(r 1)+ + -12) + 62l(12 - 12) r((zi.)))
Hence for all M2 E M(xx)) we have
I (I))(=))) - (1 - -)+ - b,(r 1)t1 = 021(12 - -2) b2l(12 - 122+1
Φ2du3 + C(r,,))
X2
We define A == -1 ([ (1-bb,,,0 azl) and B == P2 (-00, -b2) = X2 \.A A, and the Borel bounded function / X2 - [0. 1] by
1
if E A.
f(x)
0
otherwise.
Put 1/2 = fn2. As (2((2(()) = (2(2))
i A,
we get that
b2
if B,
0zl(12 - -2) 62l(72 12)+1 /
(1- --ffdr2- - f Sxa= p2fdr
p2dus =b2
X2
S. spad7e
b2
d72
{ X2
-Jel(22)d12
Hence for every we have
(e((2)) - a1(1 - (1= b1(r - - / J2((2)d(12 + C(r1,) Xa = =C(11, - p(J2(122))
Therefore, for every E X1, E P(X2), we get
(1((1)) a1 (1 (1=
bi 11) C(z1,)) - p(J2(122).
(1(p)(z1)) sup sup r>0
r
This implies that 0g J.. Hence &g $
Now we are ready to prove our duality formula. Moreover, by Lemma A.5 one has k is convex and lower semi-continuous. Hence, applying (27 Proposition 3.1, page 14 and Proposition 4.1, page 18] we get that (k) ET Therefore, applying Lemma A.4 we get
ET ETk..k k2 (21)
(i(xs)dp;(a;) - (ET kz ( (
sup (OXX))))
sup Σ (i(xi)d(((a)) ((1))2)) i=1
sup Σ
2
L (i(x;)dp((z.)
(4 i=l Sx,
sup Σ / (0 ==1 X,
I((p((x)))d
21

---

A.4 Proof of Corollary 3.1
Proof of Corollary 3.1 We define C X1 P(X2) -,,,+oo) by C(r1,P) p)
k xx,
C(T1, 22
[dp(22)) 22 for every E X1, E P(X2). Then C' is bounded from below,
by b inf C O, and C(I,,)) is convex for every E X1. Applying Lemma 14),
2 2
we get that C' is lower semicontinuous. From Example A.I A.3 we also have that C has property
(T).
Now we prove that Φ = Ay. For every (f1, E 11, 21 E X2 E X2 we have
ii (x1) + (2((22) (1( 82, (192)
(01(01) + (2(y))d80zzz)
X2
S k c(1,, (v)
X2
k. kkcl(z1 x2).
Hence 4 C A,. On the other hand, for every (fI, (22 E A1 E X1,P E P(X2), we have
/
(x()) + p((22)
Xx,
$ | k c(2 d)pp(
X2
C).
Hence A, C y, and therefore 4 Ar. Similarly, we also have 4, As. Applying Theorem 3.2 we get the result.
A.5 Proof of Theorem
Proof of Theorem
3.3 Applying Corollary 3.1 we have
gki (21, = sup 1 [(()(())))1(()++ + / [29 : E Cx(,),
(i(x) -b,, 92(1) 2 (12, S k- c(x,) Vo X
As u2 = EM midy. we get that
(k sup { (((((()))d(x)) + Σ m,l(ww;) P1 C.(()) -b1,
w 2 (1)) wi le (r. X1, = 1,.... M)
As e is lower semicontinuous and satisfies radial property (see Definition 3. with respect to (1, we obtain that (w), (m()) R3 measuraalee partition X1- Given n N and w (wi...., WM) E +oc) we define the map e2 X1 + (-00, +oo] by cf (a) min(n.c cz())) As e measurable, so are e and c Since {ch) JEE increases, con-
verges pointwise to c² 11 continuous and increasing on [-b1, +oo), and lim (s)) ai, get that
M Σ
lim lim (1) 20000 X1
(())()))d)1())++ + [I("(()))
n=000
C.ww)
M Σ
[1-b v k c(x, - (z) + (R).
km C.ww)
22

---

Therefore,
gki Ka. (11: P2) = sup ((w) w w== (wi.... wx) b- to0) As
L
A.6 Proof of Theorem 3.4
Proof of Theorem
M. Then {B, : = l,..., M) is measurable partition of X1 x X2 and hence we can write 7 = Ei= T @ by for 1J E (M i=
3.4 Put B, X1 x Pvot.e 1,...,M,
d'11
As (y, H2) oo get JxIXX, cdyy co and hence n1 [t) = 0. Therefore JR fdjm = 0, ie., f(x) = for p1-ae. x E R. The Lebesgue decomposition
1..... M. Put f
dup
of 12 T with respect #g is 72 Eies, 1a16,, + 72', where 72 E.es, m Here
T refers to the ith marginal of y. We have
f
cki.ka.k (1),1,)")7((111 =k
cdry +
[01(1 - f(x))* + b1(())) - (d))
Xi (an
Xi
Ind
Imall
-1)
+ +bm (X1)
+
1
+ b2
my + b2 Σ ml
mi
m
EE
SE80
M
cl, (d)d(()))) +
[1 -f(x))) + bb
- (1) (x))
i=1
+
|7: - :)
+ (apu(R) + (X,)
Σ
02
1
+ d2
my + 02 Σ
Imdl-
mi
m;
iES,
On the other hand, for = 1,2, we have
80;
if ai, if - b, 4 S as.
a:(1 - 5)+ b:(s 1 2
sip
20
otherwise.
Hence a,1 (4(1-s)t + (: 1)+ [1p)= 2 ssp for all s. The inequality is equality if and only -b; & 4 and = 1. Therefore, we get that
M
Eki,ko. 2 ((w)= =k
(d + 62
Σ Ind
X1\R
iES2
+
a1 - (1x)) + b1(((xx)-11) - 1)+ 1 -1(ce du)(z)
X1\R
-1) +
+
Σ
a2
+ b2
12(w;) mi
mi
mi
iES,
(x,v:)dd. bint (Xi) + b2 Σ Iml
1=1
XIXR
ve.2
J XXIRR
(=)))((()()))
Σ Ime lu
FES,
M
ko(z, (1) wi c((())
( dmi(t)) +
. jxiR
(x)))(t(xx
XI\R
+ bi
(X1
R Σ
melles + by Σ 1mT
vESa
M
Σ
ko(x,
wi - c (x)) (n) + f/( (c" + bb)ddtt(())
,x,i
Cc(ar)
1=1
23

---

+ Σ
mal(us + b2)
SE82
20.
dn (x) = f(x) = for P1-ae. x E X1 R and duz
The first inequality an equality if and only
Iml 1 for all E S1. The second inequality becomes equality if and only if supp?/ C((w) and my
hence 7/: -ww for i ...... M, c² (a) -b for - X1 R. and ti; -by for every i E S2. Therefore, get that k2 (ylui, (ww) 0 if and only if conditions 7 10 hold.
A.7 Proof of Proposition 3.1
Proof of Proposition 3.1 By Definition
3.3 we have (x) = +oc for any I R. By 3 for any
R, we have 4 (c"((z)) 11 (+00)) a.uuss (1 Jn
Combining
this result with (6). we obtain
((w)= / (=)ddx)) + Σ Iz I2(w:)
By definition in 3 11 differentiable on (-b1, ai (a,, +o0), such that 0,11(x) = on (-b1, a1) and 0, (x) 0 on (a1, +oo). Thus, for any E Ci(w), it holds 1 (ce 1i((-b) Vk cxz, M4) - we), and we can derive the derivatives
0,
k- c(x, - wy E 1-x,
1,,
k: c(,,0
wy E {b),
Bw (z)
k c(x,0)) - wy E (-b1,a1),
[1,0],
k c(x, my E {a1).
0,
c-
E (a1, too).
On the other hand, for any E (u(w), have Oe, ((c"(()) 0, for any j í. Therefore, by Lemma 3.8 of [13], radial property (see Definition 3.2) of cost function c, and the absolutely continuity of μr with respect to Lebesgue measure, then
Sw, (=))dd))) (M((C( fo k c(x,0)) we E (bb,,a1)))
(17)
Similarly, by definition in 3 know
1.
wi (-b2, a2).
0m. (2((w)
[0, 1}, 0,
w; E (a2),
wy (a2, +00).
Then the (sub-)gradient can be obtained as presented.
A.8 Proof of Theorem 3.5
Equations 7 10 show that continuous mass rearranges only within Laguerre cells, while the residual mass collapses into the remainder set R. This insight later underpins our quantization and pruning strategies. Plugging the optimality conditions of Theorem 3.4 back yields the following explicit primal form, facilitating comparison with classical semi-discrete OT.
Corollary A.1 (Primal tessellation formulation). there exists optimizers for 2 and 5 then
kkik (2) min
(()) ail(p1 -
+1+
Ci(w)
(18)
17d m
17
Σ VES:
02
+
bz(
1
m; +
b2 Σ
w E [- M M e M(Xi),, muR= m
mi
m
ie.9
24

---

where Ni = C 1.....=i........... .M. y and w are optimizers for ( and (5), then the first margin
Tn and w are optimizers for (18). Conversely, in and w are optimizers for (18), then y defined by is the optimizer for 2
Proof. For any choice of w E 1-b2,+00) 71 E M(Xi), and 7IR O, define Y Ei= mi C((w) @ by, E M(X, x X2). The right-hand side of (18) can be written in the same form 2 where the admissible set for y is restricted to subset such that y takes the form Y - (L) & by. Therefore, the right-hand side of (18) no less than 2ki,ka.**ua U2).
On the other hand, by Theorem 3.4 if Y = Ei ? @ óy. and w E 1-bb, +o0) are taken to be the optimizers for ( and (). respectively, then they should satisfy 7 which leads to -
1, 1, .., and 7LR R = O, where 7 is the first margin of Y In this case, the
right-hand side of (18) equals gki çkk.ka.k Ka (21, and vÿ and w" are the optimizers for (88)
Conversely, if 7 and w are optimizers for 18 then defined by 7 in terms of 7Î and w" is the optimizer for (2.
Proof of Theorem 3.5 Consider any fixed (" war C X2. For any constant E R. let C.(a) == Ca, .a)), where (a. is an M-dimensional vector. For every w E
[-b2, too) M, we define
mM) SAYR
((w, mw.. .........))).........
(1) + Σ 12(w:)m;
==1
where e"c X1 - (-oc, too] is defined by (x) min o(r, w; : 1,,,..,,}}
M)V -b.
From Theorem 3.3 we get that
k2. (11, H2) 2 0(0, mi mm).
As [2) = 0 we get that G(0, m1. mi....,aal mar) = -X J (z))d) (11( =: G(0) does not depend on mı. m
Let pz = ΣM m 5y. We define the measurable map f X1 + R, defined by f(x) = for
ar- E X1 \ R and f(x) for a1-a.e R. Define 17" := fp1 E M(X1), nf := 7 (O. and 72 = =E (() @ 5y,- Then the Lebesgue decomposition of 7f with respect to μ4 is Vi =Em 1h fur. Optimality conditions (IO) is fulfilled. By Theorem 3.4 it holds that (al m5) = =(O)). Hence Q yyM) -())) i.e.
gai (Ni,
M 11-bi v k (:)dn + ampi (R).
Qu .UM) Σ
/ C.(0)
A.9
Proof of Proposition 3.2
Proof of Proposition
3.2 Note that
Qu1 .. "at."..,,aal .ur)) = / (=)
Xx
By definition in we know
1, # (-b,,a1);
(x
[0. 1].
r {a1)
0.
x too.
Fix x E C,(O), we have (c)((x))) = T,(( ((-bb, V k c(x, v.),, and its derivative is obtained by chain rule,
0,
k k c(z, mi) E (-o0, b1), k c v1) E a1); t c W² E +00))
V (c)
A n. c(c, w))
0,
25

---

Besides. (x)((()))) = for any j # i. Therefore,
[ J.,00
V y/ Qvi,, (MM)
kV 21 o,, Wew.es (x)
=k
b.o0nssskecsss)erbb.....)) V c(2,,))))4 (2).
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract outlines our study of an unbalanced weak optimal transport problem with total variation penalties and highlights the key contributions relative existing literature. The introduction further elaborates on the scope and significance of our work through clearly structured bullet points, providing a detailed overview of the theoretical and practical adancemennss.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Given the paper's primary focus on developing rigorous theoretical frame- work and the associated space constraints, we clearly state at the beginning of Section that the numerical examples are preliminary and illustrative nature. While our general framework has broad potential for real-world applications, more extensive exploration of specific use cases left for future work.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
27

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All assumptions are stated explicitly at the beginning of Section 3 and reiterated in the statements of each theorem when necessary. Given the density of theoretical results, we present only the theorem statements in the main text for clarity, while full proofs are provided the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
The experimental details and settings are provided in Subsections 4. and 4.2
well in the supplementary material. All experiments are designed to be easily repro- ducible.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
28

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code is included in the supplementary material and will be made publicly available upon acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
cublic/guides Stte//ooeeuesioioooooooooooooeoa
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Detailed experimental settings and hyperparameters are provided in Sections 4. and 4.2 well as in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
29

---

Answer: [No]
Justification: Our experiments are designed to illustrate the main theoretical results, which are primarily mathematical in nature. All experiment results support the validity of the explicit (sub)gradient formula employed in our optimization algorithm.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Yes, the experiments can be executed CPU with runtime of approximately 2.5 seconds, as reported in Section 5
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
30

---

10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is primarily theoretical work.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
31

---

The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
32

---

Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question:
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our L.LM policy for what should or should not be described.
33


Reviews:
[{"review_id": "W6Vpr6qrJZ", "reviewer": "Reviewer_KBQN", "summary": "The paper develops a semi-discrete formulation of weak optimal transport where the discrepancies between marginal distributions are regularized through a TV term.  And this work proves the existence of an optimal plan and gives a dual characterisation whose variables coincide with the weights that generate Voronoi diagram. They proposed an iterative weight–update algorithm for the case of a continuous demand distribution and finitely many depots.  They applied their methods on two small two dimensional demos to shows how the method allocates spatial resources.", "questions": "Could you position your algorithm more explicitly against the approaches of Agarwal et al.?  Do you have either theoretical bounds or empirical results on the convergence rate and scalability of the weight–update scheme?  Why was total variation selected over other divergences commonly used in OT?  Would you clarify the distinction you intend between weak and unbalanced OT, and explain whether your formulation is essentially the standard one–sided unbalanced model?", "limitations": "na", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The theoretical proof is good, optimal existence and duality are established, the notation is clear and consistence, and the link between the dual weights and Laguerre tessellations is well explained.  But the bridge to Laguerre diagrams is not novel, having been analysed in detail in recent work about semi-OT by Agarwal et al. (SODA 2024, NeurIPS 2024), so the main incremental value appears to be the introduction of a total\\-variation penalty within the semi-OT framework. The manuscript lists four extensions—weak transport cost, unbalanced marginal constraints, total\\-variation regularisation and semi\\-discrete geometry—but their joint motivation is not so clear, kind confusing why all four are needed together. And, the terminology \"weak OT\" and \"one–sided unbalanced OT\" are sometimes conflates, which may confuse readers. Empirical support is limited to small toy instances, with no complexity analysis, convergence guarantee or sensitivity study.\n\n- Agarwal, Pankaj K., et al. \"Fast and accurate approximations of the optimal transport in semi-discrete and discrete settings.\" Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 2024.\n- Agarwal, Pankaj, et al. \"A combinatorial algorithm for the semi-discrete optimal transport problem.\" Advances in Neural Information Processing Systems 37 (2024): 25857-25887.", "was_revised": true, "final_justification": "I have reviewed and acknowledged the the authors' response. I think the authors made responses to each of the concerns. After reviewed the discussion with the other reviewers I will keep my initial justification. Thanks!", "rebuttal": "We have carefully reviewed and summarized your comments and questions into five main points below. While they may not appear in the exact order presented, we have addressed each of them in turn. Thanks for your thoughtful and constructive feedback.\n\n**[1]** The bridge to Laguerre diagrams is not novel, having been analyzed in recent work about semi-OT. Could you position your algorithm more explicitly against the approaches of Agarwal et al.?\n\n## R1\nThank you for this insightful comment. We fully agree that the use of Laguerre diagrams in semi-discrete OT problems is not our novelty, but rather a natural tool in analyzing such problems (see e.g., [1]). The main contribution of our paper lies in the development of a comprehensive theoretical framework for a new class of unbalanced weak OT problems incorporating total variation (TV) penalties, along with an illustration of its applicability to spatial resource allocation. Building on the work [4], we take one step forward, and to the best of our knowledge, this is the first theoretical study to address weak OT problems with TV penalties in the unbalanced setting. Importantly, the introduction of TV penalties is not only technically motivated by the need to handle mismatched masses, but also practically justified as real-world problems often involve supply-demand imbalance, making such a formulation both reasonable and necessary (see also [5]).\n\nWe are glad to clarify our contribution with the recent work of Agarwal et al. (SODA’24, NeurIPS’24). While their studies focus on the balanced semi-discrete OT setting, where the source $\\mu$ and target $\\nu$ are probability measures with equal total mass, our work advances the framework in two key directions. First, we consider a more general unbalanced setting in which the source and target measures may have unequal total mass. This naturally introduces a mismatch, for which we introduce TV penalties to regularize the deviation. This extension is not only mathematically nontrivial but also grounded in practical scenarios where supply rarely matches demand exactly. Second, within this generalized model, we develop a complete duality theory that lays the foundation for further analysis and a range of potential applications. For example, we derive explicit sub-gradients for the dual variables, enabling the construction of transport plans through simple gradient-based algorithms. Additionally, we propose a method that jointly optimizes both the cell weights and facility locations.\n\nIn summary, as a theory track paper, we believe our submission offers a substantial theoretical contribution that generalizes classical results to the unbalanced and practically motivated setting, supported by a rigorous dual framework. We hope these clarifications help better position our work within the growing body of research on OT.\n\n**[2]** The manuscript lists four extensions—weak OT, unbalanced marginal constraints, total-variation regularization, and semi-discrete geometry—but their joint motivation is not so clear.\n\n## R2\nThanks for your comment, and we would like to make the following clarifications. \n\n(1) As replied in R1, we consider the unbalanced OT setting, which is motivated by many practical scenarios involving mismatched supply and demand, e.g., the aggregate number of available taxis may exceed the number of potential customers. In such cases, introducing regularization is essential to penalize deviations on either the source (supply) or target (demand) side; otherwise, the problem may not be well-posed. We adopt total-variation regularization which is also motivated by practical relevance: TV loss is intuitive and proportional to the count of unsatisfied or excessive units. In contrast to entropy regularization (commonly used for numerical convenience, see [4]), TV regularization is more interpretable and operationally grounded, yet remains underexplored in the theoretical OT literature. Thus, our incorporation of unbalanced marginal constraints and TV penalties is both natural and meaningful.\n\n(2) We indeed solve the general OT problem dealing with general source $\\mu$ and target $\\nu$ in the main part (see Section 3.1). We subsequently specialize to the semi-discrete case in Section 3.2, primarily due to its favorable and interpretable geometric structure, which facilitates further analysis and insights (see Section 3.2). This semi-discrete geometry is not simply an extension, but rather a natural and illustrative special case within our broader framework that warrants deeper investigation.\n\n(3) Finally, from a theoretical standpoint, our goal is to develop as general a framework as possible. The weak formulation enables us to push the theory to its limits and includes classical OT as a special case. Beyond its generality, the weak formulation has shown promising practical advantages: by relaxing the coupling constraints, it enhances robustness to sampling noise and stability in empirical settings where exact couplings may not exist or may be sensitive to perturbations (see, e.g., [2,3]). \n\n**[3]** The terminology “weak OT” and “one–sided unbalanced OT” are sometimes conflated. Would you clarify the distinction you intend between weak and unbalanced OT, and explain whether your formulation is essentially the standard one–sided unbalanced model?\n\n## R3\nWe appreciate the chance to clarify the terminology. Weak OT and unbalanced OT address two distinct and orthogonal modeling dimensions. Weak OT modifies how transport cost is evaluated.  Rather than paying for every point-to-point flow, it allows each source point to distribute its mass as a probability measure over the target space. The cost is then computed based on the barycenter of this distribution. This formulation preserves total mass but introduces stochastic routing, which can enhance robustness and flexibility. In contrast, unbalanced OT retains the classical point-to-point transport cost but relaxes marginal constraints, permitting mass surplus or deficit on one or both sides. Such discrepancies are penalized via total variation (TV) in our paper. For example, in a ride-hailing scenario, the platform may only control the supply (taxis), not the demand (customers). This leads to a one-sided, unbalanced setting, where the supply distribution is fixed, and deviations in meeting demand are penalized. Since these two generalizations pertain to different aspects: the former to cost structure and the latter to marginal feasibility, they are complementary to model practical situations and can be combined, resulting in what we refer to as “weak and unbalanced OT.” We hope this distinction helps clarify the modeling choices in our framework.\n\n**[4]** Do you have either theoretical bounds or empirical results on the convergence rate and scalability of the weight–update scheme?\n\n## R4\nThanks for your comment. As a theory-track submission, the primary contribution of our work lies in the development of a comprehensive theoretical framework for a new class of unbalanced weak OT problems incorporating total variation (TV) penalties. The optimization routine presented in the (special) semi-discrete setting is therefore intended not as the main focus, but rather as an illustrative application of the proposed framework. That said, we appreciate your suggestion to incorporate complexity analysis, convergence guarantees, and sensitivity studies. While these are certainly valuable directions, we have opted to leave them for future work for two reasons: (i) to maintain clarity and focus on the general theoretical framework, and (ii) due to space limitations. Nonetheless, we note that the use of explicit gradients in our setting should allow for relatively straightforward extensions of standard convergence analyses in the semi-discrete case.\n\nWe also appreciate your concern regarding scalability. As an illustration, we extend the depot-location experiment in Section 4.2 to five larger scales, increasing the dimensionality of the optimization variable. The CPU time is acceptable. Although this scalability assessment is not the focus of our paper, we believe it demonstrates the practical potential of our theoretical findings and provides a promising direction for future investigation. Since we are unable to upload images or PDF files, we present the results in tabular form.\n| scale (m,d) | (4,1) | (8,2) |(16,3) | (32,3) |(64,4)|\n|-|-|-|-|-|-|\n| numbers of parameter | 12 | 24 | 48 | 96 |192|\n|CPU time |4.9s|7.5s|15.2s|29.6s|65.9s|\n\n\n**[5]** Why was TV selected over other divergences commonly used in OT?\n\n## R5\nThanks for raising this important point. As replied in R2, we chose the TV penalty primarily because it offers a clear and intuitive economic interpretation, closely aligned with the well-known newsvendor loss function commonly used in operations management and economics. This form of penalty is also adopted in practice, e.g., by DiDi, a major ride-sourcing platform (see [5]). Specifically, it penalizes the mismatches from both sides: If supply exceeds demand, a proportional overage cost is incurred, reflecting the cost of excess supply (e.g., idle resources, inventory holding); When demand exceeds supply, a shortage cost is applied, corresponding to the opportunity loss from unmet demand, such as forgone revenue. This structure allows the penalty to directly reflect economic losses in a way that is both intuitive and interpretable. Given our focus on practical resource allocation problems as highlighted in the paper’s title, we intentionally adopted the TV regularization instead of entropy-based penalties, which are less straightforward to interpret in economic terms.\n\n[1] Aurenhammer, Klein, Lee. ... World Scientific Publishing Company, 2013.\n\n[2] Backhoff-Veraguas and Pammer. …. Bernoulli, 2022.\n\n[3] Feydy, Séjourné, Vialard, Amari, Trouvé, Peyré. ... AISTATS, 2019.\n\n[4] Liero, Mielke, Savaré. ... Inventiones Mathematicae, 2018.\n\n[5] Zhou, Luo, Qie, Ye, Zhu. ... JASA, 2021."}, {"review_id": "aIxR3bfX7B", "reviewer": "Reviewer_ZhcG", "summary": "The paper presents a new family of unbalanced weak optimal transport with weighted total variation penalties with a focus on the semi-discrete setting. They present a comprehensive theoretical analysis that yields (1) the dual formulation for the general problem, and in the special semi-discrete cases (2) a finite-dimensional tessellation reformulation (corresponding to service area partition) that can be solved via gradient methods, and (3) a sequential optimization strategy for optimal spatial resource allocation. Illustrative numerical examples well showcase the motivations of the OT problem as well as its numerical tractability.", "questions": "My questions are mostly related to numerical convergence. \n1. You set a decaying step size in Section 4, which is pretty understandable for the piecewise nonsmooth objective. However, I am concerned that if you scale up the problem size, such decaying step design may converge only suboptimally.  Did you try different problem sizes? How bad is the condition number of the problem as we scale it up?\n2. While the sequential or alternating method looks viable in Sec 3.3, no convergence analysis is provided. I don’t see this finite-dimensional problem still preserving convexity with respect to both locations and masses. Can you comment on this a bit? I would imagine its performance resembles the EM algorithm for gaussian mixtures. \n\nThe last question is a bit more general.\n\n3. Can you comment on the significance of recasting these familiar problems including resource allocation commonly appears in operations research literature into an optimal transport formulation? What are the key pros and cons compared to a classical linear program approach?", "limitations": "Yes, the authors acknowledged insufficiency of additional applications and discussed future work in the last two sections.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n1. The paper is easy to follow. It is very well motivated and self-contained, with a clear structure, mathematical rigor, and accompanied by intuitive interpretations of abstract concepts.\n2. The proposed OT problem looks important and can serve a unified framework for several important real-world problems. \n3. The theory is comprehensive and elegant with clear citations showing connections with related literature. They look correct, though detailed proofs are not checked with confidence as the reviewer has insufficient knowledge of deep theories. Provided gradient derivations are helpful to develop quick algorithms. \n\n**Weaknesses**\n1. The experiments are relatively toy level, though I agree that the paper’s focus is more theoretical. It would be interesting to see how scaling up the problem size affects the efficiency of the presented gradient methods. \n2. The applications considered are relatively restricted. The example presented in Example 2.1 is not too different from the field of the motivating resource allocation problems. It would definitely be interesting to see if applications in other fields may be casted to the considered OT problem.", "was_revised": true, "final_justification": "I generally recommend the acceptance for their clear motivations, complete theoretical framework, as well as certain level of guidance on algorithm design. I think the paper also writes clearly and is thus suitable for circulation of ideas in the current venue. \n\nOn the other hand, I am not sufficiently sure of the theoretical novelty. The empirical evidence and algorithmic contribution is also not too strong as noted by most reviewers, yet I am fine with this.", "rebuttal": "We sincerely appreciate your positive feedback on our work, as well as your thoughtful and constructive comments. Please find our detailed responses to each of your questions below.\n\n**[1]** I am concerned that if you scale up the problem size, such a decaying step design may converge only suboptimally. Did you try different problem sizes? How bad is the condition number of the problem as we scale it up?\n## R1\nThanks for your insightful comments. We fully agree that for less smooth objectives, gradient descent methods may face challenges in performance and convergence to the optimal solution. Nevertheless, our derivation of explicit gradient expressions enables us to experiment with gradient-based methods, and we appreciate your understanding that this section serves primarily as an illustrative application of our theoretical findings. We believe the application domain, including the one you mentioned, contains many interesting directions that warrant deeper exploration in future work.\n\nIn response to your suggestion, we have conducted preliminary experiments to assess scalability and examine the impact of the condition number. We apologize that these experiments remain preliminary due to time constraints and page limit, but we are committed to pursuing a more thorough investigation in future research.\n\nSpecifically, in terms of step size, we note that the decaying rate and initial value can be easily adjusted if convergence appears insufficient. As an initial scalability study, we repeated the depot-location experiment from Section 4.2 at five progressively larger scales, increasing the dimensionality of the optimization variable. We sample locations from a two‑component Gaussian mixture with means $(0.3d,0.3d)$ and $(0.7d,0.7d)$. The number of depots is $m$ and the decaying step size of $0.3/(1+t)^{0.6}$ is used.\n\nThe table below shows that while the empirical condition number of the smoothed Hessian does increase from approximately $9$ to over $7000$ as the number of optimization parameters grows from $12$ to $192$. Despite this, the CPU time scaled roughly linearly, remaining within a practically acceptable range. While these results are not central to our main contributions, we believe they suggest that our theoretical findings could scale reasonably well and support potential use for larger-scale problem instances. We thank the reviewer again for prompting this analysis and look forward to exploring these aspects in more detail in future work.\n| scale (m,d) | (4,1) | (8,2) |(16,3) | (32,3) |(64,4)|\n|-|-|-|-|-|-|\n| numbers of parameter | 12 | 24 | 48 | 96 |192|\n| condition number | 8.8 | 9.5 | 117.7| 885.6 |7437|\n|CPU time |4.9s|7.5s|15.2s|29.6s|65.9s|\n\n\n**[2]** While the sequential or alternating method looks viable in Sec 3.3, no convergence analysis is provided. I don’t see this finite-dimensional problem still preserving convexity to both locations and masses. Can you comment on this a bit? I would imagine its performance resembles the EM algorithm for Gaussian mixtures.\n## R2\nWe sincerely thank the reviewer for the insightful and professional remark. You are absolutely right in observing that, since the outer objective is not jointly convex in $(Y,w)$, our alternating scheme (similar in spirit to the EM algorithm for Gaussian mixtures) may only have convergence to a stationary point, which may be a local rather than global optimum. This limitation is indeed inherent to first-order methods in non-convex settings. Nonetheless, the explicit gradient expressions we derive offer significant computational convenience and enable practical implementation of the algorithm.\n\nWhile a full convergence analysis lies outside the scope of our main theoretical contribution, we believe that the availability of explicit gradient expressions makes it relatively straightforward to extend standard convergence guarantees, such as convergence to stationary points under mild assumptions, to our setting. Of course, in the special case where the objective is convex, convergence to the unique global optimum would follow. However, this is not the case for the general formulation considered in our work. In general, when we apply gradient descent, the algorithm can converge to the stationary set of the ODE constructed by the gradient flow, see [1,2] for details. Furthermore, when some respective convexity conditions hold, the method fits the gradient block‑coordinate descent setting studied by [3,4]. Specifically, alternating updating methods can also achieve convergence because we have explicit gradients, and the analysis is quite standard [5,6], so we omit it here.\n\nIn summary, although global optimality cannot be guaranteed due to non-convexity, our algorithm provides a tractable and theoretically grounded method for identifying stationary solutions, which can serve as useful approximations in practical spatial resource allocation tasks.\n\n**[3]** Can you comment on the significance of recasting these familiar problems including resource allocation commonly appears in operations research literature into an optimal transport formulation? What are the key pros and cons compared to a classical linear program approach?\n## R3\nWe thank the reviewer for this thought-provoking question. Recasting classical resource allocation problems as an unbalanced, weak optimal transport (OT) problem offers several distinct advantages from both theoretical and practical perspectives. We elaborate on the key benefits below: \n\n(1) Geometric expressiveness. OT is inherently grounded in a metric structure, allowing the concept of “distance” in spatial resource allocation to be represented and leveraged more naturally. In particular, the semi-discrete OT setting enables the use of Laguerre/Voronoi tessellations and other geometry-aware algorithms that would be difficult to derive from purely algebraic linear programming (LP) formulations. Importantly, this geometric perspective is not only more theoretically elegant but also enhances practical decision-making, e.g., in partitioning service areas for facilities like fireboat stations or inventory warehouses.\n\n(2) Natural treatment of imbalance. Through the inclusion of a total variation (TV) penalty, the unbalanced OT formulation directly models the cost of mass creation or deletion. This provides an explicit and tunable trade-off between transport cost and supply-demand mismatch, expressed in the same units. In contrast, LP models typically rely on artificial slack variables and large-penalty terms. The magnitude of the TV penalty offers a clear and quantitative measure of over- or under-supply severity.\n\n(3) Semi‑discrete realism. Many spatial allocation problems involve a continuous customer distribution and a finite set of candidate facilities, a structure that the semi-discrete OT framework captures precisely. This allows one to integrate over the continuous domain (analytically or via Monte Carlo methods), while keeping the facility variables finite-dimensional and interpretable. While in practice customers may be discrete, modeling them as a density field enables cleaner structural insights and facilitates scalable approximations without sacrificing realism. \n\n(4) Scalability and Structural Efficiency. A standard approach in continuous domains is to discretize space and solve the resulting high-dimensional discrete OT problem via LP. However, this quickly becomes computationally infeasible as the dimension grows or finer resolution is desired. By contrast, the OT formulation, particularly in the semi-discrete case, allows us to reduce the problem to a low-dimensional weight vector, with the same size as the number of facilities. This drastically improves scalability compared to large LPs, especially in high dimensions.\n\nTogether, these features make the OT-based framework a geometrically faithful, imbalance-aware, and practically aligned modeling language for spatial resource allocation, offering a clear advantage over traditional LP formulations.\n\nThat said, we acknowledge that the OT approach is not without limitations. LP models, for instance, offer immediate implementability and require little structural analysis; they can yield a solution (good or bad) with minimal modeling and theoretical analysis effort, especially after discretization. Furthermore, beyond the semi-discrete setting, the theoretical results in the general OT framework may be more abstract and harder to interpret for direct application. Nevertheless, we believe the enhanced structure, interpretability, and flexibility afforded by the OT perspective provide compelling benefits in many settings.\n\n\nFinally, we acknowledge the insufficiency of additional applications because we want to focus more on our theoretical framework in this theory-track paper. In future work, we will follow your inspiring suggestions to explore more applications based on the foundation we have established; indeed, some of the potential extensions or applications have been discussed in the last two sections.\n\n\nThank you once again for your insightful and constructive feedback on our manuscript. We hope you find our revision satisfactory.\n\n[1] Borkar, Vivek S., and Vivek S. Borkar. Stochastic approximation: a dynamical systems viewpoint. Vol. 100. Cambridge: Cambridge University Press, 2008.\n\n[2] Kushner, Harold J., and G. George Yin. Stochastic approximation and recursive algorithms and applications. New York, NY: Springer New York, 2003.\n\n[3] Tseng, Paul. \"Convergence of a block coordinate descent method for nondifferentiable minimization.\" JOTA 109.3 (2001): 475-494.\n\n[4] Beck, Amir, and Luba Tetruashvili. \"On the convergence of block coordinate descent type methods.\" SIOpt 23.4 (2013): 2037-2060.\n\n[5] Wright, Stephen J. \"Coordinate descent algorithms.\" MP 151.1 (2015): 3-34.\n\n[6] Lin, Tianyi, Chi Jin, and Michael I. Jordan. \"Two-timescale gradient descent ascent algorithms for nonconvex minimax optimization.\" JMLR 26.11 (2025): 1-45."}, {"review_id": "VRCTYb81RV", "reviewer": "Reviewer_ZGLs", "summary": "This paper introduces a formulation of unbalanced weak optimal transport incorporating total variation (TV) penalties. Motivated by resource allocation problems with asymmetric over- and under-supply/demand costs, the authors develop a general theoretical framework encompassing existence results and dual formulation. Focusing on the semi-discrete setting—where demand is modeled as a continuous measure and supply as a finite set of discrete locations—the authors develop a tessellation-based reformulation. This yields a dual optimization problem defined over generalized Laguerre cells. They also extend the framework to a quantization problem in which the locations and weights of the discrete supply points are jointly optimized. \nThe paper presents illustrative examples demonstrating the method’s ability to produce spatially meaningful solutions for simple supply area division and spatial ressource allocation problems.", "questions": "- When using a TV penalty in a discrete UOT formulation, it is unclear how mass creation can appear (it is always cheaper to remove mass than adding some mass). Could you give an example for which it happens in your formulation (eq. 1 and 2)?\n- How does your method compares to other semi-discrete unbalanced OT methods in the application scenario you have considered?\n- How does the setting in section 4.2, where the continuous formulation is sampled, is a semi-discrete problem?\n\n\nOther comments:\n- l123-125: could you provide a reference?\n- symbol $^+$ should be defined\n- l140: $k$ should be defined\n- l233: $d$ should be defined", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n- The unification of weak OT and unbalanced OT under a TV penalty is original and well-motivated.\n- The paper is clearly written, with proofs and intuitive explanations that make the technical contributions accessible.\n- The application to spatial allocation and facility location is convincing to some extent\n\nWeaknesses:\n- experimental validation: while the examples are illustrative, the empirical evaluation could be expanded. For instance, comparisons with existing entropy-regularized unbalanced OT or standard quantization approaches would strengthen the claims of practical benefit. In addition, the computational complexity of the optimization procedures, especially in higher dimensions or with large discrete supports, could be more thoroughly analyzed\n- motivation: while the use of a semi-discrete formulation with mass relaxation makes sense in the application that are described in the spatial ressource allocation problem, the motivation and advantage of instroducing weak OT into the formulation is unsufficiently discussed.\n- some formulations and results differ from the standard UOT with TV penalty setting, which is not discussed (see questions below)", "was_revised": true, "final_justification": "I have carefully read the authors response and the discussions with other reviewers. While I found some drawbacks to the paper (mainly insufficient motivation — but should be fixable in the camera ready version— and lack of validation in challenging setups different that ressource allocation pbs), I still leaning toward acceptance as it provides sound new developments about weak and unbalanced OT.", "rebuttal": "We sincerely appreciate your positive feedback on our work, as well as your thoughtful and constructive comments. Please find our detailed responses to each of your questions below.\n\n**[1]** When using a TV penalty in a discrete UOT formulation, it is unclear how mass creation can appear (it is always cheaper to remove mass than adding some mass). Could you give an example for which it happens in your formulation (eq. 1 and 2)?\n\n## R1\nWe are glad to answer this question. In the unbalanced setting we consider, the two marginal distributions, $\\mu_1$ (supply) and $\\mu_2$ (demand), are fixed and determined by the specific application scenario. When the total available supply $|\\mu_1|$ is strictly less than the total demand $|\\mu_2|$, simply redistributing the existing mass may not be sufficient to meet the demand. In such cases, mass must be created in order to satisfy $\\mu_2$, which, in real-world terms, corresponds to a supply shortage. To account for this, we introduce a penalty term that quantifies the cost of mass imbalance, allowing the transport plan to create or delete mass where needed. This formulation enables us to minimize the combined transport and mismatch cost in a principled way. On one hand, the resulting transport plan offers insight into how much additional supply would need to be supplemented, or how much existing supply might be in excess. On the other hand, our framework naturally encompasses the classical balanced setting as a special case, in which exact matching between supply and demand is enforced on both sides.\n\nA simple one-dimensional example helps to illustrate this point. Let $X=[0,1]$, with a continuous supply distribution $\\mu_1(dx) =0.3dx$ (total mass 0.3), and a discrete demand $\\mu_2=0.5\\delta_{0.5}$ (total mass 0.5). Suppose the transport cost is zero, and let the mismatch penalties satisfy $a_1=b_1=0, a_2, b_2>0$. Then the transport plan $\\gamma(dx,dy)=0.5dx\\ \\delta_{0.5}(dy)$ ships all available mass to $y=0.5$ and creates an additional $0.2$ units of mass to fully meet the demand. This plan is in fact optimal, as the OT loss is zero (transportation cost is zero, no penalty on the supply side since $a_1=b_1=0$, and the mismatch penalty on the demand side is also zero).\n\nThis example demonstrates that the model flexibly allows for mass creation, mass deletion, and transport, depending on the cost structure and penalty parameters. Such flexibility is critical for capturing real-world resource allocation problems where perfect balance between supply and demand is often unattainable.\n\n\n**[2]** How does your method compare to other semi-discrete unbalanced OT methods in the application scenario you have considered?\n\n## R2\nThank you for this insightful question. To the best of our knowledge, there is currently no existing work on semi-discrete unbalanced OT that optimizes a total variation (TV)-regularized objective. The algorithms cited in the literature cannot be adapted by simply replacing the divergence function, as their convergence guarantees critically depend on the strong convexity and smoothness properties of the entropic regularization.\n\nIn contrast, we adopt TV regularization, motivated not only by theoretical interest but also by practical relevance. TV loss is intuitive, interpretable, and directly proportional to the number of unsatisfied or excessive units. For example, DiDi, a major ride-sourcing platform in China, has used TV-based metrics to evaluate loss resulting from idle supply or unmet demand (see [9]). While entropy-based regularization (commonly used for computational reasons, see [1,2,3,4,8]) is widespread, it is often less interpretable in practice. In this regard, TV-based regularization remains underexplored in the theoretical OT literature, despite its operational appeal. We believe our incorporation of unbalanced marginal constraints with TV penalties offers a natural and meaningful modeling alternative.\n\nIn fact, the main contribution of our paper lies in the development of a comprehensive theoretical framework for a new class of unbalanced weak OT problems incorporating TV penalties, together with an illustration of its applicability to spatial resource allocation. Building on the foundational work in [8], our study takes a significant step forward. To the best of our knowledge, this is the first theoretical treatment of weak OT problems with TV penalties in the unbalanced setting. From a methodological standpoint, the techniques developed in prior works based on entropic regularization are not directly applicable to our setting. This is because the TV penalty exhibits linear growth, in contrast to the smooth and strongly convex structure induced by entropy. As a result, we develop new theoretical tools and analysis techniques to address the challenges posed by the TV-regularized formulation and establish the corresponding duality and optimality conditions in parallel.\n\n**[3]** How is the setting in section 4.2, where the continuous formulation is sampled, a semi-discrete problem?\n\n## R3\nThank you for your careful reading and thoughtful question. A semi-discrete optimal transport problem refers to a setting where one marginal measure is absolutely continuous, and the other is discrete. The sampling step we introduce does not alter the mathematical nature of the problem, it simply replaces the continuous integral in the outer objective $$Q(y)=\\sum_{i}\\int_{C_i(w^{\\star})} z(x,i)\\,d\\mu(x)+a_1\\mu(R),$$ with an unbiased empirical estimate, enabling more efficient gradient evaluation. We adopt this sampling-based approximation for computational convenience, particularly since the number of samples is large enough to ensure high accuracy in practice.\n\nWe acknowledge that, in a strictly formal sense, this empirical approximation introduces some difference from the idealized formulation. However, based on our numerical experiments, we find that the approximation is highly accurate, and the resulting ot solutions are very close to those obtained via exact integration. Thus, the stochastic estimate merely facilitates efficient gradient computation, allowing the outer–inner optimization framework (Theorem 3.5 & Proposition 3.2) to converge effectively in practice.\n\n**[4]** Other comments:（1）l123-125: could you provide a reference?（2）symbol $^+$ should be defined（3）l140: $k$ should be defined（4）l233: $d$ should be defined\n\n## R4\nWe thank the reviewer for the careful reading and detailed, point-by-point comments. We will revise the manuscript accordingly. Below are our responses and clarifications: \n\n(1) The newsvendor loss function is commonly used in operations management and economics to measure the supply-demand mismatch (see, e.g., [5,6,7]). This form of penalty has also been adopted in practice, e.g., by DiDi, a major ride-sourcing platform (see [9]). Specifically, it penalizes the mismatches from both sides: If supply exceeds demand, a proportional overage cost is incurred, reflecting the cost of excess supply (e.g., idle resources, inventory holding); When demand exceeds supply, a shortage cost is applied, corresponding to the opportunity loss from unmet demand, such as forgone revenue. This structure allows the penalty to directly reflect economic losses in a way that is both intuitive and interpretable. \n\n(2) For any signed object, the superscript “+” denotes its positive part. Specifically, for a scalar or measurable function $g$ we set $g^+=\\max\\{g,0\\}$, while for a signed measure $\\nu$ on $(X,\\mathcal{F})$, we take $\\nu^+$ to be the positive variation in the Jordan decomposition $\\nu=\\nu^++\\nu^-$ with $\\nu^+\\ge0$, $\\nu^-\\ge 0$ and $\\nu^+ \\perp\\nu^-$.\n\n(3) The nonnegative constant $k$ serves to rescale the transportation cost, reflecting the relative importance between transport and mismatch costs. While technically it can be absorbed into the definition of the cost function $c$, keeping it explicit highlights the application-dependent trade-off. For instance, in disaster-relief logistics, where delivery costs are secondary to meeting urgent demand, a small $k$ emphasizes mismatch penalties; In ride-sourcing applications, where both costs are typically measured in monetary units, a natural choice is $k=1$.\n\n(4) d(x,y) is the Euclidean distance between $x$ and $y$. \n\n**[5]** Regarding the clarification on our motivations, we kindly ask you to refer to our response to Reviewer KBQN (R2), as we are constrained by the character limit imposed by the conference system. We greatly appreciate your understanding.\n\nThank you once again for your insightful and constructive feedback on our manuscript. We hope you find our revision satisfactory.\n\n\n[1] Chizat, Lenaic, et al. Scaling algorithms for unbalanced optimal transport problems. Mathematics of computation 87.314 (2018): 2563-2609.\n\n[2] Scetbon, Meyer, et al. Unbalanced low-rank optimal transport solvers. NeurIPS 36 (2023): 52312-52325.\n\n[3] Pooladian, Aram-Alexandre, Vincent Divol, and Jonathan Niles-Weed. Minimax estimation of discontinuous optimal transport maps: The semi-discrete case. ICML, 2023.\n\n[4] Bonet, Clément, et al. Slicing Unbalanced Optimal Transport. TMLR (2024).\n\n[5] Petruzzi, Nicholas C., and Maqbool Dada. Pricing and the newsvendor problem: A review with extensions. Operations Research 47.2 (1999): 183-194.\n\n[6] Qin, Yan, et al. The newsvendor problem: Review and directions for future research. EJOR 213.2 (2011): 361-374.\n\n[7] Khouja, Moutaz. The single-period (news-vendor) problem: literature review and suggestions for future research. omega 27.5 (1999): 537-553.\n\n[8] Matthias Liero, Alexander Mielke, and Giuseppe Savaré. Optimal entropy-transport problems and a new Hellinger–Kantorovich distance between positive measures. Inventiones Mathematicae, 211(3):969–1117, 2018.\n\n[9] Fan Zhou, Shikai Luo, Xiaohu Qie, Jieping Ye, and Hongtu Zhu. Graph-based equilibrium metrics for dynamic supply–demand systems with applications to ride-sourcing platforms. JASA, 116(536):1688–1699, 2021."}, {"review_id": "ThKubu6qRy", "reviewer": "Reviewer_z3hw", "summary": "The paper proposes a novel semi-discrete, unbalanced weak optimal transport model with total variation penalties for spatial resource allocation problems. It provides theoretical analysis and extends classical transport frameworks to non-smooth, TV-regularized settings. Experiments demonstrate promising results on small-scale problems, but scalability and hyperparameter sensitivity warrant further investigation.", "questions": "1. The experimental evaluation is limited to small-scale applications. Have the authors considered testing their method on larger-scale datasets or more complex scenarios to further assess its scalability, performance, and convergence properties?\n2. The paper involves several hyperparameters in the proposed method. Could the authors elaborate on the process of hyperparameter selection and provide an analysis of how sensitive the algorithm's performance is to these choices?", "limitations": "yes", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength**\n\n1. The authors model a novel semi-discrete, unbalanced weak optimal transport problem with total variation penalties, motivated by practical spatial resource allocation problems.\n2. For this problem, the authors conduct theoretical analyses on the existence of optimal solutions and tessellation-based reformulations, and extend classical entropy-regularized transport frameworks to the non-smooth, TV-penalized setting.\n\n**Weakness**\n\n1. The experiments are conducted only on small-scale applications. Although the results are promising, the performance and convergence on larger-scale problems remain to be verified.\n2. Based on my previous research experience, I have often found that theoretically sound methods may have limited practical effectiveness, and may require careful tuning of hyperparameters to ensure convergence and satisfactory performance. The experiments in this paper also involve various hyperparameters; more discussion is needed regarding how they are selected and their impact on performance.", "was_revised": true, "final_justification": "I remain positive on the paper, including the writing, the method and the theoretical results. The submission is not in my area, so I have lowest confidence about my score.", "rebuttal": "We sincerely appreciate your positive feedback on our work, as well as your thoughtful and constructive comments. Please find our detailed responses to each of your questions below.\n\n**[1]** The experimental evaluation is limited to small-scale applications. Have the authors considered testing their method on larger-scale datasets or more complex scenarios to further assess its scalability, performance, and convergence properties?\n\n## R1\nThanks for your comment. As a theory-track submission, the primary contribution of our work lies in the development of a comprehensive theoretical framework for a new class of unbalanced weak OT problems incorporating total variation (TV) penalties. The optimization routine presented in the (special) semi-discrete setting is therefore intended not as the main focus, but rather as an illustrative application of the proposed framework. That said, we appreciate your suggestion to incorporate more experiments on larger-scale datasets or more complex scenarios to further assess its scalability, performance, and convergence properties. While these are certainly valuable and interesting directions, we have opted to leave them for future work for two reasons: (i) to maintain clarity and focus on the general theoretical framework, and (ii) due to space limitations. \n\nIn particular, we also appreciate your concern regarding scalability. As an illustration, we extended the depot-location experiment in Section 4.2 to five larger scales, increasing the number of facilities $m$ and the dimensionality of the optimization variable (from 12 to 192 parameters). We sample \\(N=2000\\) incident locations from a two‑component Gaussian mixture with means $(0.3d,0.3d)$ and $(0.7d,0.7d)$, and covariance $0.02I_2$. Samples are clipped to $[0,d]^2$ and rescaled to ensure $M_\\mu=1$.The number of depots is $m$, with initial positions drawn i.i.d. from the uniform distribution over $[0,d]^2$. TV parameters are set as $a_1=0.3$, $a_2=1$, $b_1=0.1$, and $b_2=0.2$. A decaying step size $0.3/(1+t)^{0.6}$ is used.\n\nWe reran the spatial‑allocation test with progressively larger depot sets. The CPU time rises almost linearly, within an acceptable speed. Although this scalability assessment is not the focus of our paper, we believe it demonstrates the practical potential of our theoretical findings and provides a promising direction for future investigation. Since we are unable to upload images or PDF files, we present the results in tabular form.\n| scale (m,d) | (4,1) | (8,2) |(16,3) | (32,3) |(64,4)|\n|-|-|-|-|-|-|\n| numbers of parameter | 12 | 24 | 48 | 96 |192|\n|CPU time |4.9s|7.5s|15.2s|29.6s|65.9s|\n\n\n**[2}** The paper involves several hyperparameters in the proposed method. Could the authors elaborate on the process of hyperparameter selection and provide an analysis of how sensitive the algorithm's performance is to these choices?\n\n## R2\nThanks for your insightful question. While our model does involve several parameters, each of them reflects practical considerations and carries clear interpretability in real-world applications. For instance, if we interpret $\\mu_1$ as the supply distribution and $\\mu_2$ as the demand distribution, the parameters in the cost objective (Equation (2)) have the following meanings: $a_1$ measures the unit cost excess supply (e.g., idle resources); $b_1$ measures the unit penalty for insufficient supply; $a_2$ measures the unit penalty of being unable to meet the demand; $b_2$ measures the unit overage cost; and the nonnegative constant $k$ serves to rescale the transportation cost, reflecting the relative importance between transport and mismatch costs. These parameters are application-dependent and can be pre-defined accordingly. For instance, in disaster-relief logistics, where delivery costs are secondary to meeting urgent demand, a small $k$ emphasizes mismatch penalties; In ride-sourcing applications, where both costs are typically measured in monetary units, a natural choice is $k=1$.\n\nOn the theoretical side, our framework is general and flexible, and the full analysis applies across the entire range of model parameters. In particular, classical optimal transport under balanced settings emerges as a special case within our formulation. The optimization algorithm we present is tailored to a special semi-discrete case, and it is included as proof-of-concept application of our theoretical findings rather than a central contribution of the paper. Notably, it involves minimal hyperparameter tuning: thanks to our analytical derivations, explicit gradients are available, allowing for direct use of standard gradient descent methods. In practice, step size is the only parameter that typically requires adjustment, an issue that is well-understood and extensively studied in the optimization literature. We appreciate the reviewer’s suggestion to elaborate further on implementation details, but we have opted not to include them in the main manuscript for two reasons: (1) to keep the focus on the core theoretical contributions, and (2) to stay within the page limit constraints. We hope this clarifies our design choices and appreciate your understanding.\n\n\nThank you once again for your insightful and constructive feedback on our manuscript. We hope you find our revision satisfactory."}, {"review_id": "HJ78f10rCS", "reviewer": "Reviewer_8tzK", "summary": "The paper investigates an unbalanced, barycentric (i.e., weak), total variation-regularized optimal transport formulation. The authors show the existence of a solution for the considered problem and derive its dual form. They then discuss the corresponding semi-discrete setting, showing that it is equivalent to an optimization problem on Laguerre diagrams and providing its optimality conditions. They further extend this setting into optimizing over the space of discrete measures (i.e., weights and support points), which is inspired by the problem of spatial resource allocation, and provide an alternating scheme for solving it. Experimental results regarding those semi-discrete settings are carried out on synthetic data.", "questions": "- What is the importance of considering weak optimal transport in the proposed problem? I do not see its relevance to the allocation problem. Is it for the technicality of TV regularizers?\n- The paper mentions entropic regularization several times in Section 2, but the problem of interest is not entropy-regularized, as well as the formulation written in Line 101.\n- Typo: $\\phi$ instead of $\\varphi$ in Line 191", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper is well-written and well-presented.\n- The proposed problem is new, and so are the relevant results.\n\nWeaknesses:\n- The motivation and the final problem of the paper aim at the practical problem of spatial resource allocation, but there is little discussion about the related work on this topic, as well as the experiment results are only on synthetic data and without comparison to any other method.\n- The alternating scheme might converge only to a local minima, as the loss seems to be non-convex.", "was_revised": true, "final_justification": "I maintain my score of 4, indicating a slight lean toward acceptance, based on the following:\n\nPros: The paper presents a well-rounded contribution. The formulation is novel, supported by sufficient theoretical results and practical algorithms, and further validated through a real-world application.\n\nCons: The theoretical and algorithmic techniques show limited novelty, and the empirical evaluation remains insufficiently thorough.\n\nIn their response, the authors provided additional details on the resource allocation problem, which I believe will improve the paper’s overall quality. Comments on the use of the weak OT formulation (which is also noted by other reviewers) would further strengthen its clarity. However, the primary concerns regarding novelty and empirical depth remain.", "rebuttal": "We sincerely appreciate your positive feedback on our work, as well as your thoughtful and constructive comments. Please find our detailed responses to each of your comments and questions below.\n\n**[1]** What is the importance of considering weak optimal transport in the proposed problem?\n\n## R1\nThank you for giving us the chance to clarify. Weak OT (WOT) is a genuine generalization of classical OT. In classical OT, each source point $x$ is coupled with a Dirac measure at a single target point, i.e., the coupling $\\pi(\\cdot\\mid x)$ is deterministic. In contrast, WOT allows $\\pi(\\cdot\\mid x)$ to be any probability measure, enabling stochastic transport from each source location. As a result, the classical OT feasible set is a strict subset of the WOT feasible set. When the cost function $c(x,\\cdot)$ is convex, WOT serves as a relaxation of the classical problem and can only decrease the objective value. \n\nFrom a theoretical perspective, particularly for a theory-track paper, our aim is to develop as general a framework as possible and push the theory to the limit of our method. The weak formulation allows us to extend the theory to its broadest scope while naturally including classical OT as a special case.\n\nBeyond its theoretical generality, the weak formulation offers practical advantages and has attracted independent interest in several areas. By changing the coupling constraints, WOT improves robustness to sampling noise and enhances stability in empirical settings where exact couplings may not exist or may be unstable due to data perturbations (see, e.g., [1,2]). While a detailed exploration of such applications is beyond the current scope and left for future work, we believe that the inclusion of the weak formulation is not merely a technical generalization, but rather reflects the theoretical flexibility and broader potential of our proposed approach.\n\n**[2]** The paper mentions entropic regularization several times in Section 2, but the problem of interest is not entropy-regularized, as well as the formulation written in Line 101.\n\n## R2\nThanks for your clarification question. The references to entropic regularization in Section 2 are included solely to position our work within the existing semi-discrete unbalanced OT literature, where Kullback–Leibler or other entropy-based penalties are commonly used. \n\nThe main contribution of our paper lies in the development of a comprehensive theoretical framework for a new class of unbalanced weak OT problems incorporating total variation (TV) penalties, along with an illustration of its applicability to spatial resource allocation. Building on the work [3], we take one step forward, and to the best of our knowledge, this is the first theoretical study to address weak OT problems with TV penalties in the unbalanced setting. Importantly, the motivation for incorporating TV penalties is both technical and practical. Technically, TV regularization is well-suited to settings with mismatched masses, a common feature in real-world problems where supply–demand imbalance is the norm. Practically, the TV penalty is directly interpretable: If supply exceeds demand, a proportional overage cost is incurred, reflecting the cost of excess supply (e.g., idle resources, inventory holding); When demand exceeds supply, a shortage cost is applied, corresponding to the opportunity loss from unmet demand, such as forgone revenue. This structure provides an intuitive and economically meaningful way to quantify mismatch costs, particularly relevant for our focus on resource allocation applications, as emphasized in the paper's title. In contrast, entropy-based regularization, while analytically convenient, offers less interpretability in such contexts. \n\nAdopting a TV regularization term fundamentally changes the problem and raises new challenges: the objective becomes less smooth, loses the strong convexity enjoyed by entropic formulations, and thus precludes the direct use of prior methods developed under those assumptions (e.g., [3]). So we develop totally different theoretical analysis (compared to [3]). As a result, we develop new theoretical tools tailored to this setting. This is precisely why the entropic framework is cited only for contextual comparison and is not employed in our formulation.\n\n\n**[3]** Typo: $\\phi$ instead of $\\varphi$ in Line 191.\n## R3\nThank you very much for your careful reading and for diligently pointing out this typo. We have corrected it in the revised version of the manuscript.\n\n\n**[4]** The final problem of the paper aims at the practical problem of spatial resource allocation, but there is little discussion about the related work on this topic, and the experiment results are only on synthetic data and without comparison to any other method.\n## R4\nThank you for your thoughtful comment. To the best of our knowledge, there is currently no existing work on semi-discrete unbalanced OT that optimizes a TV-regularized objective. Existing algorithms in the literature are typically built around entropic (e.g., KL-divergence) regularization, and their convergence guarantees rely heavily on the strong convexity and smoothness properties specific to that setting. As such, these methods are not directly adaptable to the TV-penalized formulation we consider.\n\nIn contrast, our work introduces a TV-based regularization, motivated by both theoretical considerations and practical relevance. The TV penalty is intuitive and interpretable, directly measuring the number of unmet or excessive units in a supply–demand setting. For instance, DiDi—a leading ride-sourcing platform in China—has employed TV-style loss metrics to evaluate operational inefficiencies due to idle supply or unmet demand (see [4]). While entropy-based regularization is widely used for computational convenience (see [1–4,14]), it lacks the same level of interpretability in operational contexts. Despite its practical appeal, TV regularization remains underexplored in the theoretical OT literature, making our proposed framework a natural and meaningful extension. \n\nFrom an application standpoint, several works relate to the broader theme of resource allocation with imbalance (see [5–11]). Among them, the most relevant is [11], which addresses order dispatching in ride-sourcing platforms. That model can be viewed as a special case of our framework, incorporating application-specific constraints such as fixed supply-side marginals to represent limited driver availability.\n\nRegarding experimental results: as noted above, there is currently no available algorithm for semi-discrete unbalanced OT with TV regularization. The closest prior work (e.g., [12–15]) incorporates imbalance through entropic penalties, not TV. Hence, direct numerical comparisons are not meaningful, as existing methods do not address the same problem formulation.\n\nFinally, we emphasize that this is a theory-track submission, and our main contribution is the development of a general theoretical framework. The optimization algorithm included in the semi-discrete case is intended as an illustrative application, rather than the central focus. Including extensive algorithmic benchmarks would shift the emphasis away from the core theoretical contributions and exceed the page limits. We appreciate your understanding on this point.\n\n\n**[5]** The alternating scheme might converge only to a local minima, as the loss seems to be non-convex.\n\n## R5\nRegarding the convergence of our algorithm, we kindly ask you to refer to our response to Reviewer ZhcG (R2), as we are constrained by the character limit imposed by the conference system. We greatly appreciate your understanding.\n\n\nThank you once again for your insightful and constructive feedback on our manuscript. We hope you find our revision satisfactory.\n\n[1] Julio Backhoff-Veraguas and Gudmund Pammer. Applications of weak transport theory. Bernoulli, 28(1):370–394, 2022.\n \n[2] Jean Feydy, Thibault Séjourné, François-Xavier Vialard, Shun-ichi Amari, Alain Trouvé, and Gabriel Peyré. Interpolating between optimal transport and mmd using sinkhorn divergences. AISTATS, pages 2681–2690. PMLR, 2019.\n\n[3] Matthias Liero, Alexander Mielke, and Giuseppe Savaré. Optimal entropy-transport problems and a new hellinger–kantorovich distance between positive measures. Inventiones Mathematicae, 211(3):969–1117, 2018.\n\n[4] Fan Zhou, Shikai Luo, Xiaohu Qie, Jieping Ye, and Hongtu Zhu. Graph-based equilibrium metrics for dynamic supply–demand systems with applications to ride-sourcing platforms. JASA, 116(536):1688–1699, 2021.\n\n[5] Benjaafar, Saif, et al. Dynamic inventory repositioning in on-demand rental networks. MS 68.11 (2022): 7861-7878.\n\n[6] Besbes, Omar, Francisco Castro, and Ilan Lobel. Surge pricing and its spatial supply response. MS 67.3 (2021): 1350-1367.\n\n[7] Besbes, Omar, Francisco Castro, and Ilan Lobel. Spatial capacity planning. OR 70.2 (2022): 1271-1291.\n\n[8] Bimpikis, Kostas, Ozan Candogan, and Daniela Saban. Spatial pricing in ride-sharing networks. OR 67.3 (2019): 744-769.\n\n[9] Hosseini, Mahsa, Joseph Milner, and Gonzalo Romero. Dynamic relocations in car-sharing networks. OR 73.4 (2025): 2010-2025.\n\n[10] Gunnar Carlsson, John, Xiaoshan Peng, and Ilya O. Ryzhov. Demand equilibria in spatial service systems. MSOM 26.6 (2024): 2305-2321.\n\n[11] Zhou, Fan, et al. Graph-based equilibrium metrics for dynamic supply–demand systems with applications to ride-sourcing platforms. JASA 116.536 (2021): 1688-1699.\n\n[12] Chizat, Lenaic, et al. Scaling algorithms for unbalanced optimal transport problems. Mathematics of computation 87.314 (2018): 2563-2609.\n\n[13] Scetbon, Meyer, et al. Unbalanced low-rank optimal transport solvers. NeurIPS 36 (2023): 52312-52325.\n\n[14] Pooladian, Aram-Alexandre, Vincent Divol, and Jonathan Niles-Weed. Minimax estimation of discontinuous optimal transport maps: The semi-discrete case. ICML, 2023.\n\n[15] Bonet, Clément, et al. Slicing Unbalanced Optimal Transport. TMLR (2024)."}]

Author rebuttal:

Meta-review: This paper introduces and analyzes a new class of unbalanced weak optimal transport problems with total variation penalties, motivated by spatial resource allocation tasks such as facility placement or service area partitioning. All reviewers agree that this is a strong paper and should be accepted.

The reviewers highlighted that the paper makes interesting and valuable contributions. The unification of weak OT and unbalanced OT under a TV penalty is both novel and well-motivated, and the authors provide a thorough theoretical treatment. The tessellation-based structure is elegant and leads to explicit gradient expressions that support practical algorithmic developments. The paper is clearly written, with careful proofs and intuitive explanations, and the application to spatial allocation and facility location problems adds further relevance and clarity.

Some weaknesses were also noted. The experiments, while illustrative, are limited to small-scale examples and do not include comparisons to alternative methods, and the computational complexity of the optimization procedures is not fully explored. Moreover, although the spatial allocation motivation is clear, the specific role and advantages of introducing weak OT into the formulation could be elaborated further, as could connections to related applied work. The authors provided useful clarifications on these points in their rebuttal and committed to addressing them in the final version, which should strengthen the paper further.

In summary, this is a well-written and rigorous work that introduces a novel and well-founded framework with solid theoretical contributions and meaningful practical motivation. I recommend acceptance.
Decision: Accept (poster)