Multiplicative Assignment with Upgrades

Armbruster, Alexander; Rohwedder, Lars; Weltge, Stefan; Wiese, Andreas; Zhang, Ruilong

doi:10.4230/LIPIcs.ICALP.2026.13

Multiplicative Assignment with Upgrades

Alexander Armbruster

Technical University of Munich, Germany Lars Rohwedder

University of Southern Denmark, Odense, Denmark Stefan Weltge

Technical University of Munich, Germany Andreas Wiese

Technical University of Munich, Germany Ruilong Zhang

City University of Hong Kong (Dongguan), China

Abstract

We study a problem related to submodular function optimization and the exact matching problem for which we show a rather peculiar status: its natural LP-relaxation can have fractional optimal vertices, but there is always also an optimal integral vertex, which we can also compute in polynomial time.

More specifically, we consider the multiplicative assignment problem with upgrades in which we are given a set of customers and suppliers and we seek to assign each customer to a different supplier. Each customer has a demand and each supplier has a regular and an upgraded cost for each unit demand provided to the respective assigned client. Our goal is to upgrade at most $k$ suppliers and to compute an assignment in order to minimize the total resulting cost. This can be cast as the problem to compute an optimal matching in a bipartite graph with the additional constraint that we must select $k$ edges from a certain group of edges, similar to selecting $k$ red edges in the exact matching problem. Also, selecting the suppliers to be upgraded corresponds to maximizing a submodular set function under a cardinality constraint.

Our result yields an efficient LP-based algorithm to solve our problem optimally. In addition, we also provide a purely strongly polynomial-time algorithm for it. As an application, we obtain exact algorithms for the upgrading variant of the problem to schedule jobs on identical or uniformly related machines in order to minimize their sum of completion times, i.e., where we may upgrade up to $k$ jobs to reduce their respective processing times.

Keywords and phrases:

Scheduling, Bipartite Matching, LP-based Algorithm, Combinatorial Optimization, Resource Allocation

Category:

Track A: Algorithms, Complexity and Games

Funding:

Alexander Armbruster: Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – project 551896423.

Lars Rohwedder: Dutch Research Council (NWO) project “The Twilight Zone of Efficiency: Optimality of Quasi-Polynomial Time Algorithms” [grant number OCEN.W.21.268].

Andreas Wiese: Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – project 551896423.

Ruilong Zhang: The start-up funding of City University of Hong Kong (Dongguan) with the number R002026G0030.

Copyright and License:

© Alexander Armbruster, Lars Rohwedder, Stefan Weltge, Andreas Wiese, and
Ruilong Zhang; licensed under Creative Commons License CC-BY 4.0

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Approximation algorithms analysis

Related Version:

Full Version: https://arxiv.org/abs/2504.07663 [3]

Acknowledgements:

The authors would like to thank Thomas Rothvoss, Laura Sanita, and Robert Weismantel for organizing the 2024 Oberwolfach Workshop on Combinatorial Optimization (2446), where initial results of this work were discussed.

DOI:

10.4230/LIPIcs.ICALP.2026.13

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Consider a supply network with some given suppliers $I$ and customers $J$ satisfying $|I|\geq|J|$ where each customer must be assigned to exactly one supplier and we can assign at most one customer to each supplier. All suppliers produce the same good, each supplier $i\in I$ at an individual cost $c_{i}\geq 0$ per unit, and each customer $j\in J$ has a given demand $d_{j}\geq 0$ . The multiplicative assignment problem asks for finding an assignment $\pi:J\to I$ of minimum total cost $\sum_{j\in J}d_{j}\cdot c_{\pi(j)}$ . Finding such an optimal assignment is easy: Sort the suppliers by cost in non-decreasing order, sort the customers by demand in non-increasing order, and match them accordingly.

We consider the following extension of the problem, which we call the multiplicative assignment problem with upgrades. For each supplier $i\in I$ we are given in addition an improved cost $b_{i}\in[0,c_{i}]$ that becomes effective if we decide to upgrade supplier $i$ , e.g., modelling to improve the production processes or facilities of $i$ to make production more cost-efficient. Given a number $k\in\mathbb{Z}_{\geq 0}$ , our task is to find a subset of $k$ suppliers to upgrade that results in an assignment of minimum cost.

For each selected set $X\subseteq I$ of suppliers to be upgraded, we denote by $\operatorname{cost}(X)$ the cost of the resulting optimal assignment. We will show that the function $\operatorname{cost}(X)$ is supermodular, and hence our problem is equivalent to maximizing a submodular function subject to a cardinality constraint. While for some classes of submodular functions this problem is known to be polynomially solvable, e.g., for gross substitute functions via a greedy algorithm [17], to the best of our knowledge $\operatorname{cost}(X)$ does not belong to any of them. In particular, we show that the greedy algorithm may fail to compute an optimal solution.

Maybe unexpectedly, a special case of our problem is the upgrade-variant of the classical problem of scheduling jobs non-preemptively to minimize their average completion time, either on a single machine, on identical machines, or on uniformly related machines (see Section 5.1). Here, each job has a regular processing time and an upgraded (smaller) processing time, and we are allowed to choose $k$ jobs to be upgraded. This is motivated by assigning highly skilled personnel, improvement of equipment, or by subcontracting certain tasks, and it is also referred to as crashing a job in the project management literature, see e.g. [12]. In the scheduling literature, this has also been studied under the notion of testing a job [6] (often even in the stochastic setting where the upgraded processing times are not known a priori). Recently, Damerius, Kling, Li, Xu, and Zhang [6] gave a PTAS for the upgrade-variant of minimizing the job’s average completion time on a single machine, but they leave open whether the problem can be solved in polynomial time¹¹1We remark that the PTAS works even in the weighted setting, which the authors show to be NP-hard [6].. A detailed discussion can be found in Section 5.1.

We consider now the setting where $|I|=|J|$ which we may assume w.l.o.g. by adding customers with zero demand. In this case, our problem can be also described using the notion of bipartite perfect matchings. We introduce a node for each supplier $i\in I$ and a node for each customer $j\in J$ . For each pair $(i,j)$ there are two edges: one blue edge with cost $c_{i}\cdot d_{j}$ corresponding to assigning $j$ to $i$ without upgrading $i$ , and one red edge with cost $b_{i}\cdot d_{j}$ corresponding to this assignment with upgrading $i$ , see Figure 1. Hence, an optimal solution corresponds to a perfect matching that has exactly $k$ red edges. Therefore, our problem is related to the exact bipartite perfect matching problem in which we are given a bipartite graph with red and blue edges and an integer $k$ and need to decide whether there is a perfect matching with exactly $k$ red edges. This problem has the intriguing status that it admits a beautiful polynomial time randomized algorithm due to Mulmuley, Vazirani, and Vazirani [20], but despite several attempts, no deterministic polynomial-time algorithm has been found so far. In contrast to the general case of that problem, our bipartite graphs are complete. However, for us it is not sufficient to compute any perfect matching with exactly $k$ red edges, but we seek such a perfect matching that optimizes our objective function. For this variant only a randomized pseudopolynomial algorithm is known, see Section 5.1, which also leads to a randomized pseudopolynomial time algorithm for the multiplicative assignment problem with upgrades.

Figure 1: Instance of the multiplicative assignment problem with upgrades with

|I|=|J|=3

and

k=1

, viewed as a perfect matching problem in a bipartite graph with red and blue edges. The right matching corresponds to upgrading supplier

3

and assigning customer

1

to supplier

3

, customer

2

to supplier

1

, and customer

3

to supplier

2

, resulting in a cost

b_{3}d_{1}+c_{1}d_{2}+c_{2}d_{3}

.

The usual bipartite matching problem can be formulated by a straight-forward linear program (LP). It is well-known that its constraint matrix is totally unimodular and, hence, all vertices of the corresponding polytope are integral. If we require that at most $k$ red edges are chosen, this adds “only” one single constraint to the LP. However, then the resulting polytope is no longer integral. One could hope to strengthen this LP formulation with additional constraints and variables in order to describe exactly the convex hull of all integral points. However, no simple characterization of the convex hull is known and Jia, Svensson, and Yuan [13] showed that (for some $k$ ) any such extended formulation has exponential size. This makes it challenging to apply LP methods to solve this problem. Nevertheless, LP techniques such as the ellipsoid method remain applicable in principle when a separation oracle can be provided.

1.1 Our contribution

First, we consider the natural LP formulation of the multiplicative assignment problem. Similar to the exact bipartite matching problem, the resulting polytope is identical to the polytope of the corresponding bipartite matching instance with the additional constraint that at most $k$ red edges are chosen. We show that non-integral vertices may be even optimal LP solutions for our cost function. However, we show that in this case there is always an optimal integral vertex as well! Moreover, we show how to compute such an optimal integral vertex in polynomial time.

The fact that there is always an optimal integral vertex while there may also exist other optimal non-integral vertices contrasts many other optimization problems in which either all (optimal) vertices of the corresponding LP are integral (e.g., shortest path, minimum cost flow, or other problems for which the constraint matrix is totally unimodular) or there are instances in which none of the optimal vertices are integral (e.g., TSP, knapsack, vertex cover, etc.). Therefore, the status we prove for the multiplicative assignment problem with upgrades is rather uncommon for combinatorial optimization problems.

The feasible region of our LP relaxation is the bipartite matching polytope with one single additional constraint. Therefore, if an optimal vertex of our LP relaxation is not integral, then it must be a convex combination of two vertices in the bipartite matching polytope corresponding to integral matchings. One of these two matchings upgrades a set $A$ of strictly less than $k$ suppliers and the other matching upgrades a set $B$ of strictly more than $k$ suppliers. One key insight is to view each such supplier $i\in A\cup B$ as the interval $[b_{i},c_{i}]$ , i.e., the interval defined by its improved cost $b_{i}$ and its usual cost $c_{i}$ . We prove that if we consider only the suppliers in which $A$ and $B$ differ, i.e., the suppliers in the symmetric difference $A\,\Delta\,B$ , no two of their intervals pairwise contain each other! Using this, we derive a procedure that computes two new sets $A^{\prime}$ and $B^{\prime}$ that are “more balanced” than $A$ and $B$ : we assign the suppliers in $A\,\Delta\,B$ alternatingly to $A^{\prime}$ and $B^{\prime}$ . Then, we show that from $A,B,A^{\prime}$ , and $B^{\prime}$ we can form a new pair having again the properties of $A, B$ mentioned above (in particular that a convex combination of their corresponding optimal matchings is an optimal LP-solution) but such that the number of upgraded suppliers differ less than for the pair $A, B$ . We prove that this “balancing” process terminates with an integral optimal matching after a linear number of iterations. If for an instance the suppliers’ costs are pairwise distinct and the customer’s demands are also pairwise distinct, we prove that then even all optimal vertices are integral. However, also in that case the polytope of the LP-relaxation can still have fractional (sub-optimal) vertices since the mentioned conditions affect only the objective function but not the polytope.

Let us denote by $h(k^{\prime})$ the cost of an optimal (integral) solution that upgrades exactly $k^{\prime}$ suppliers, for each $k^{\prime}\in\mathbb{N}$ . Our proof above implies that the linear interpolation of $h$ is convex. From this property, we also derive a purely combinatorial, strongly polynomial-time algorithm for the multiplicative assignment problem with upgrades, which reduces the problem to at most $|I|$ instances of weighted bipartite matching without any additional (upgrading) constraint. In each iteration, we start with one (integral) solution $S_{1}$ that is optimal for upgrading a certain number $k_{1}<k$ suppliers, and another solution $S_{2}$ that is optimal for upgrading $k_{2}>k$ suppliers. Given these solutions, we solve a Lagrangian relaxation of the multiplicative assignment problem in which the constraint for choosing $k$ red edges is moved to the objective function, penalizing red edges. This penalty is chosen such that $S_{1}$ and $S_{2}$ are still optimal for the resulting cost function. If the computed solution is strictly better than $S_{1}$ and $S_{2}$ (for the new cost function) then this yields a new integral solution $S^{\prime}$ that is optimal for updating a certain number $k^{\prime}$ of suppliers with $k_{1}<k^{\prime}<k_{2}$ ; we replace $S_{1}$ or $S_{2}$ by $S^{\prime}$ and continue with the next iteration. Otherwise, we compute an optimal integral solution with the same method we used above to balance the sets $A$ and $B$ iteratively.

As a consequence, we obtain an exact strongly polynomial-time algorithm for the aforementioned upgrade-variants of scheduling jobs on $m$ identical or uniformly related parallel machines to minimize their average completion time, which hence extends the work of [6]. A natural question is whether our results still hold in a more general setting, for example, when the given bipartite graph is not complete, if we can reduce the demand of some given number of customers (similar to upgrading the costs of the suppliers), or if the suppliers are partitioned into subsets such that we can upgrade a certain number from each of them (similar to a partition matroid). However, for all these cases we prove that the resulting LP-relaxation might not have optimal integral vertices and, hence, our results do not extend to them.

1.2 Other related work

Scheduling with Testing or Resources.

Scheduling with testing under explorable uncertainty to bridge online and robust optimization was introduced by [7] and extended to various scheduling models [2, 4, 8]. These problems were initially motivated by code optimization, where jobs (programs) are either executed directly or pre-processed to reduce running time. [6] studied single-machine total completion time minimization in four settings (online/offline, uniform/general testing), proposing a PTAS for general testing offline but leaving open the complexity of uniform testing offline. Our work resolves this and extends the results to the setting of multiple machines. Scheduling with Resource Allocation [10, 15] dynamically adjusts job processing times via renewable resources (e.g., computational power) while respecting budget constraints. These problems also share some similarities with our problem. Unlike our testing-based model (fixed post-testing runtimes), resource allocation allows runtime adjustments, creating a fundamental distinction.

Budget Constrained Matching.

Budget-constrained combinatorial optimization is well-studied [1, 5, 9, 22]. The closest work is budget-constrained bipartite matching [5, 9], where given a bipartite graph with edges that have a weight and multiple costs, we seek a minimum weight perfect matching such that all cost dimensions satisfy the budget limit. The problem is clearly NP-hard and generalizes our problem. A PTAS via iterative rounding is shown in [5, 9].

Submodular Maximization.

Since $\operatorname{cost}(X)$ is supermodular (see Appendix A), our problem reduces to maximizing a submodular function under a cardinality constraint. For general non-negative, monotone, submodular functions, a $(1-1/e)$ -approximation is achievable, but improving this requires super-polynomially many queries [21]. For matroid rank and gross substitutes functions, exact optimal solutions can be computed in polynomial time using the greedy algorithm [17]. However, our problem is not captured by these settings; indeed, we show that the greedy algorithm might fail to compute an optimal solution for our problem (the counterexample of the greedy algorithm can be found in the full version [3]).

2 Basic definitions and LP-formulation

We first define our problem formally and introduce some basic concepts, including the LP-formulation we will work with. We are given a set of suppliers $I$ and a set of customers $J$ where we assume that $|I|\geq|J|$ . For each supplier $i\in I$ we are given costs $b_{i}$ and $c_{i}$ such that $0\leq b_{i}\leq c_{i}$ , for each customer $j\in J$ we are given a demand $d_{j}\geq 0$ , and in addition we are given a value $k\in\{0,\dots,|I|\}$ . Our goal is to compute a subset $A\subseteq I$ with $|A|\leq k$ (corresponding to the suppliers we upgrade) and a one-to-one map $\pi:J\to I$ (corresponding of the assignment of customers to suppliers); our objective is to minimize

\sum_{j\in J:\pi(j)\in A}b_{\pi(j)}d_{j}+\sum_{j\in J:\pi(j)\in I\setminus A}c% _{\pi(j)}d_{j}.

(1)

For any fixed set $A\subseteq I$ , it is easy to determine an assignment $\pi$ that minimizes (1): Simply sort the suppliers by their effective cost ( $b_{i}$ if $i\in A$ and $c_{i}$ if $i\notin A$ ) in non-decreasing order, sort the customers by demand in non-increasing order, and match them accordingly. Note that this works independently of the cardinality of $A$ , so even if $|A|>k$ . Hence, we have:

Lemma 1.

Given a set $A\subseteq I$ , in polynomial time we can compute a one-to-one map $\pi:J\to I$ that minimizes $\sum_{j\in J:\pi(j)\in A}b_{\pi(j)}d_{j}+\sum_{j\in J:\pi(j)\in I\setminus A}c% _{\pi(j)}d_{j}.$

For the sake of completeness, we give a formal proof in the full version [3]. Given a set $A\subseteq I$ , we denote by $\operatorname{cost}(A)$ the cost of the optimal assignment according to Lemma 1. Note that the notation $\operatorname{cost}(A)$ is exactly equal to the LP objective value after we upgrade $A$ . Hence, we want to compute a set $A\subseteq I$ with $|A|\leq k$ that minimizes $\operatorname{cost}(A)$ . While $\pi$ can be computed by a greedy algorithm once $A$ is fixed, we cannot simply use a greedy algorithm to compute an optimal set $A$ (see the full version [3] for a counterexample). Therefore, we need a more sophisticated approach to solve our problem.

In the remainder of this paper, we will assume that $|I|=|J|$ , which we can ensure by adding dummy customers with zero demand. Note that then $\pi$ is a bijection.

Bipartite matching

Since $|I|=|J|$ it is convenient to study our problem using the notion of perfect matchings. To this end, we fix $G$ to be the bipartite (multi-)graph with vertices $V=I\dot{\cup}J$ where each pair $i\in I$ and $j\in J$ are connected by a blue edge with cost $c_{i}\cdot d_{j}$ corresponding to assigning $j$ to $i$ without upgrading $i$ , and a red edge with cost $b_{i}\cdot d_{j}$ corresponding to this assignment with upgrading $i$ . With this terminology, our problem asks for finding a minimum-cost perfect matching in $G$ that contains at most $k$ red edges.

Linear program

We will study the following natural linear programming formulation of our problem:

$\displaystyle\min$		$\displaystyle\sum\nolimits_{(i,j)\in I\times J}\left(b_{i}d_{j}x_{i,j}+c_{i}d_% {j}y_{i,j}\right)$		$\displaystyle\forall j\in J$	(2)
$\displaystyle\mathrm{s.t.}$		$\displaystyle\sum\nolimits_{i\in I}\left(x_{i,j}+y_{i,j}\right)$	$\displaystyle=1$	$\displaystyle\forall j\in J$	(3)
$\displaystyle\sum\nolimits_{j\in J}\left(x_{i,j}+y_{i,j}\right)$	$\displaystyle=1$		$\displaystyle\forall i\in I$		(4)
$\displaystyle\sum\nolimits_{(i,j)\in I\times J}x_{i,j}$	$\displaystyle\leq k$				(5)
$\displaystyle x_{i,j}$	$\displaystyle\geq 0$		$\displaystyle\forall(i,j)\in I\times J$		(6)
$\displaystyle y_{i,j}$	$\displaystyle\geq 0$		$\displaystyle\forall(i,j)\in I\times J.$		(7)

Setting $x_{i,j}=1$ corresponds to assigning customer $j$ to supplier $i$ with upgraded cost (i.e., via a red edge) and $y_{i,j}=1$ corresponds to assigning customer $j$ to supplier $i$ without upgrading its cost (i.e., via a blue edge). For a given instance, denote by $P(k)$ the feasible region of our LP. Without Constraint (5), by the Birkhoff–von Neumann theorem (see, e.g. [23, Thm. 18.1]), this set would be identical to the perfect matching polytope of $G$ , i.e., the convex hull of all integral vectors $(x,y)$ corresponding to perfect matchings in $G$ , and thus each vertex would be integral. We remark that it is equivalent to replace the inequality in (5) with equality. We use inequality here to simplify some proofs later.

However, due to the additional Constraint (5) the polytope $P(k)$ may have a fractional vertex that might even be optimal for our objective function. Consider for example the instance defined by $I=J=\{1,2\}$ , $(b_{1},c_{1})=(0,1)$ , $(b_{2},c_{2})=(2,3)$ , $d_{1}=d_{2}=1$ and $k=1$ , see Figure 2. For this instance, the optimal solution value of our LP is $3$ , see the full version [3] for details. The resulting polytope $P(1)$ has the fractional vertex $(x^{*},y^{*})$ defined by $x_{1,2}^{*}=x_{2,1}^{*}=y_{1,1}^{*}=y_{2,2}^{*}=\frac{1}{2}$ and setting all other variables to 0. The objective function value of $(x^{*},y^{*})$ is $3$ , and hence it is optimal.

On the other hand there is also the integral vertex $(\bar{x},\bar{y})$ of our LP defined by $\bar{x}_{1,1}=1$ , $\bar{y}_{2,2}=1$ , and setting all other variables to 0, whose objective function value is also 3. Hence, for this instance, the polytope $P(1)$ has an optimal vertex that is integral. In the next section, we show that this is true for any instance, even if the corresponding polytope $P(k)$ has also fractional optimal vertices.

Figure 2: Instance with an optimal integral vertex shown in (b) and an optimal fractional vertex shown in (c). One can easily verify that both solutions (b) and (c) are vertex solutions by the Rank lemma (e.g., [16, Lemma 2.1.3]).

3 Integral optimal vertices

In this section, we prove that for any instance of our problem, the corresponding polytope $P(k)$ admits an optimal vertex that is integral. Our proof is constructive, yielding a polynomial-time algorithm that computes an optimal integral vertex of $P(k)$ .

Theorem 2.

For any instance of the multiplicative assignment problem, the corresponding polytope $P(k)$ admits an optimal vertex that is integral. Moreover, we can compute such a vertex in polynomial time.

Notice that the definition of $P(k)$ is independent of the costs and demands. Since in general $P(k)$ does not coincide with the convex hull of its integer points, it may still have fractional vertices that are optimal with respect to other objective functions (not corresponding to our problem). We also provide a sufficient conditions under which all optimal vertex solutions are integral.

Theorem 3.

If in an instance of the multiplicative assignment problem all values $(b_{i})_{i\in I}$ and $(c_{i})_{i\in I}$ are pairwise different and also all values $(d_{j})_{j\in J}$ are pairwise different, then every optimal vertex of $P(k)$ is integral.

This implies, that one can compute an optimal solution for any instance of the multiplicative assignment problem by optimally solving the LP w.r.t. a perturbed objective function.

Here, we focus on the proof of Theorem 2; the proof of Theorem 3 can be found in the full version [3]. Assume we are given an instance of the multiplicative assignment problem. First, we compute a vertex solution $(\mathbf{x},\mathbf{y})$ of $P(k)$ . If $(\mathbf{x},\mathbf{y})$ is integral, we are done. Assume that this is not the case. Let $P$ denote the polytope we obtain by omitting the constraint $\sum\nolimits_{(i,j)\in I\times J}x_{i,j}\leq k$ from our LP, i.e., omitting Constraint (5). Hence, $P$ is the convex hull of all (integral) vectors corresponding to perfect matchings. Therefore, $(\mathbf{x},\mathbf{y})$ is not a vertex of $P$ . However, since $P(k)$ can be obtained from $P$ by adding only one inequality, one can show that for $(\mathbf{x},\mathbf{y})$ this inequality is tight and that $(\mathbf{x},\mathbf{y})$ lies on an edge of $P$ . Thus, it is a convex combination of two vertices of $P$ which correspond to two perfect matchings, one upgrading less than $k$ suppliers and one upgrading more than $k$ suppliers. We compute these points and matchings using the following lemma. Formally, for any set $X\subseteq I$ we denote by $M_{X}$ the optimal perfect matching that upgrades a set $X\subseteq I$ , i.e., such that $X$ equals the set of suppliers that are incident to some red edge in $M$ (if there is more than one such optimal matching we break ties arbitrarily). Also, for any perfect matching $M$ we denote by $\chi(M)$ its corresponding vertex of $P$ . All missing proofs in this section can be found in the full version [3].

Lemma 4.

Given a vertex $(\mathbf{x},\mathbf{y})$ of $P(k)$ , in polynomial time we can compute two sets $A,B\subseteq I$ with $|A|<k<|B|$ , their corresponding optimal perfect matchings $M_{A}$ and $M_{B}$ , and a value $\lambda\in(0,1)$ such that $(\mathbf{x},\mathbf{y})=\lambda\cdot\chi(M_{A})+(1-\lambda)\cdot\chi(M_{B})$ .

Proof.

For a red edge $e$ , let $(\mathbf{x},\mathbf{y})_{e}:=x_{e}$ be the LP value corresponding to the edge $e$ . Similarly, for a blue edge $e$ we set $(\mathbf{x},\mathbf{y})_{e}:=y_{e}$ . Let $C\coloneqq\{e\in E:0<(\mathbf{x},\mathbf{y})_{e}<1\}$ be the set of all edges with fractional coordinates in $(\mathbf{x},\mathbf{y})$ . The point $(\mathbf{x},\mathbf{y})$ cannot be in the relative interior of a face of $P$ of dimension at least $2$ , as this would imply that it lies in the relative interior of a face of dimension at least $1$ when the single Constraint (5) is added. And this contradicts that $(\mathbf{x},\mathbf{y})$ is a vertex of $P(k)$ . So as $(\mathbf{x},\mathbf{y})$ is not a vertex of $P$ by assumption, it lies on an edge of $P$ . As shown in e.g. [23, Thm. 18.4], the set $C$ is a unique cycle. Let $C=\{e_{1},\dots,e_{\ell}\}$ such that $e_{i}$ and $e_{i+1}$ are adjacent for all $i\in[\ell]$ (where we use the notation $e_{\ell+1}\coloneqq e_{1}$ ). As the graph is bipartite, $\ell$ is even. Let $A^{\prime}=\{e_{2i}:i\in[\ell/2]\}$ and $B^{\prime}=\{e_{2i-1}:i\in[\ell/2]\}$ . Due to Constraints (3) and (4) we have $(\mathbf{x},\mathbf{y})_{e_{i}}+(\mathbf{x},\mathbf{y})_{e_{i+1}}=1$ for all $i\in[\ell]$ . This implies $(\mathbf{x},\mathbf{y})_{e_{i}}=(\mathbf{x},\mathbf{y})_{e_{2}}$ for $e_{i}\in A^{\prime}$ and $(\mathbf{x},\mathbf{y})_{e_{i}}=(\mathbf{x},\mathbf{y})_{e_{1}}$ for $e_{i}\in B^{\prime}$ . Let $M_{\bar{A}}=A^{\prime}\cup\{e\in E:(\mathbf{x},\mathbf{y})_{e}=1\}$ , $M_{\bar{B}}=B^{\prime}\cup\{e\in E:(\mathbf{x},\mathbf{y})_{e}=1\}$ and $\bar{\lambda}\coloneqq(\mathbf{x},\mathbf{y})_{e_{2}}$ . The edge sets $M_{\bar{A}}$ and $M_{\bar{B}}$ are matchings, as no edge $e\in E$ with $(\mathbf{x},\mathbf{y})_{e}=1$ can be adjacent to a node in $C$ . This implies $1-\bar{\lambda}=(\mathbf{x},\mathbf{y})_{e_{1}}$ and $(\mathbf{x},\mathbf{y})=\bar{\lambda}\cdot\chi(M_{\bar{A}})+(1-\bar{\lambda})% \chi(M_{\bar{B}})$ .

The sets $\bar{A}$ and $\bar{B}$ are the nodes in $I$ incident to the red edges in $M_{\bar{A}}$ and $M_{\bar{B}}$ . If $|\bar{A}|\leq|\bar{B}|$ let $A\coloneqq\bar{A}$ , $B\coloneqq\bar{B}$ and $\lambda\coloneqq\bar{\lambda}$ . Otherwise let $A\coloneqq\bar{B}$ , $B\coloneqq\bar{A}$ and $\lambda\coloneqq 1-\bar{\lambda}$ . Then we have $|A|\leq|B|$ and $(\mathbf{x},\mathbf{y})=\lambda\cdot\chi(M_{A})+(1-\lambda)\chi(M_{B})$ . Recall that $(\mathbf{x},\mathbf{y})$ is a vertex of $P(k)$ . As $\chi(M_{A}),\chi(M_{B})\in P$ we have $\chi(M_{A})\in P\setminus P(k)$ or $\chi(M_{B})\in P\setminus P(k)$ . This implies $|A|>k$ or $|B|>k$ which both imply $|B|>k$ . As $\lambda|A|+(1-\lambda)|B|\leq k$ and $\lambda\in(0,1)$ we get $|A|<k$ . This completes the proof. $\hfill\blacktriangleleft$

Note that any pair $A^{\prime},B^{\prime}\subseteq I$ with $|A^{\prime}|<k<|B^{\prime}|$ has a corresponding convex combination that upgrades exactly $k$ supplies. We denote by $f_{A^{\prime},B^{\prime}}(k)$ the objective value of this fractional solution. We call $A^{\prime},B^{\prime}$ an optimal pair if this solution is an optimal fractional solution, see formal definition below. Recall that $\operatorname{cost}(A^{\prime})$ and $\operatorname{cost}(B^{\prime})$ are the values of the LP objective after upgrading $A^{\prime}$ and $B^{\prime}$ , respectively.

Definition 5.

Let $A^{\prime},B^{\prime}\subseteq I$ . The pair $(A^{\prime},B^{\prime})$ is an optimal pair if $|A^{\prime}|<k<|B^{\prime}|$ and the optimal solution value of the LP (2)-(7) equals

f_{A^{\prime},B^{\prime}}(k):=\tfrac{|B^{\prime}|-k}{|B^{\prime}|-|A^{\prime}|% }\operatorname{cost}(A^{\prime})+\tfrac{k-|A^{\prime}|}{|B^{\prime}|-|A^{% \prime}|}\operatorname{cost}(B^{\prime}).

To gain some intuition, if $(\mathbf{x},\mathbf{y})$ upgrades (fractionally) exactly $k$ suppliers, then $(\mathbf{x},\mathbf{y})$ is the mentioned convex combination by construction and it has an objective function value of $f_{A,B}(k)$ . Also, then $f_{A,B}(k)$ equals the optimal solution value of our LP since $(\mathbf{x},\mathbf{y})$ is an optimal LP-solution; hence $(A,B)$ is an optimal pair.

Lemma 6.

Let $A$ and $B$ be two sets computed by Lemma 4. Then, the pair $(A,B)$ is an optimal pair.

Proof.

Let $\alpha$ denote the cost of $M_{A}$ and $\beta$ denote the cost of $M_{B}$ . Since $(\mathbf{x},\mathbf{y})=\tfrac{|B|-k}{|B|-|A|}\chi(M_{A})+\tfrac{k-|A|}{|B|-|A% |}\chi(M_{B})$ the optimum value of the LP is indeed equal to

\tfrac{|B|-k}{|B|-|A|}\alpha+\tfrac{k-|A|}{|B|-|A|}\beta=\tfrac{|B|-k}{|B|-|A|% }\operatorname{cost}(A)+\tfrac{k-|A|}{|B|-|A|}\operatorname{cost}(B)=f_{A,B}(k% ).\

$\hfill\blacktriangleleft$

It may happen that in $M_{A}$ (or in $M_{B}$ ) some (upgraded) supplier in $A$ (or in $B$ ) is assigned to a customer with zero demand, contributing a cost of zero to the objective function value. Intuitively, this wastes the upgrade of this supplier since it would contribute a cost of zero in the objective also if it were not upgraded. To avoid certain technical complications, we would like to remove such suppliers from $A$ and $B$ . Formally, we would like $A$ and $B$ to be simple, where we define a set $X\subseteq I$ to be simple if in $M_{X}$ no supplier is assigned to a customer with zero demand. We can easily make $A$ and $B$ simple by just removing iteratively suppliers that are assigned to customers with zero demand. Formally, we apply the following lemma to our set $(A,B)$ obtain a new simple optimal pair or even directly an optimal integral vertex of $P(k)$ (in which case we are done).

Lemma 7.

Let $(\hat{A},\hat{B})$ be an optimal pair. In polynomial time we can compute sets $\hat{A}^{\prime}\subseteq\hat{A}$ and $\hat{B}^{\prime}\subseteq\hat{B}$ that are both simple such that $(\hat{A}^{\prime},\hat{B}^{\prime})$ is an optimal pair or $\chi(M_{\hat{B}^{\prime}})$ is an optimal vertex.

Before we prove Lemma 7, we make use of the following simple observation.

Lemma 8.

If $(A,B)$ is an optimal pair, then $\operatorname{cost}(A)\geq\operatorname{cost}(B)$ .

Proof.

Let $\lambda=\frac{k-|A|}{|B|-|A|}$ . Since $|A|<k$ , the optimum LP value is at most $\operatorname{cost}(A)$ and hence

\operatorname{cost}(A)\geq f_{A,B}(k)=(1-\lambda)\operatorname{cost}(A)+% \lambda\operatorname{cost}(B),

which yields the claim. $\hfill\blacktriangleleft$

Proof of Lemma 7.

By iteratively removing suppliers that are assigned to customers with zero demand, we obtain simple sets $\hat{A}^{\prime}\subseteq\hat{A}$ and $\hat{B}^{\prime}\subseteq\hat{B}$ with $\operatorname{cost}(\hat{A}^{\prime})=\operatorname{cost}(\hat{A})$ and $\operatorname{cost}(\hat{B}^{\prime})=\operatorname{cost}(\hat{B})$ . By Lemma 8, we have $\operatorname{cost}(\hat{A}^{\prime})\geq\operatorname{cost}(\hat{B}^{\prime})$ . If $|\hat{B}^{\prime}|\geq k$ , we thus have

$\displaystyle f_{\hat{A}^{\prime},\hat{B}^{\prime}}(k)$	$\displaystyle=\operatorname{cost}(\hat{B}^{\prime})+\tfrac{\|\hat{B}^{\prime}\|-% k}{\|\hat{B}^{\prime}\|-\|\hat{A}^{\prime}\|}(\operatorname{cost}(\hat{A}^{\prime}% )-\operatorname{cost}(\hat{B}^{\prime}))$
	$\displaystyle=\operatorname{cost}(\hat{B})+\tfrac{\|\hat{B}^{\prime}\|-k}{\|\hat{% B}^{\prime}\|-\|\hat{A}^{\prime}\|}(\operatorname{cost}(\hat{A})-\operatorname{% cost}(\hat{B}))$
	$\displaystyle\leq\operatorname{cost}(\hat{B})+\tfrac{\|\hat{B}^{\prime}\|-k}{\|% \hat{B}^{\prime}\|-\|\hat{A}\|}(\operatorname{cost}(\hat{A})-\operatorname{cost}(% \hat{B}))$
	$\displaystyle=\operatorname{cost}(\hat{A})+\tfrac{k-\|\hat{A}\|}{\|\hat{B}^{% \prime}\|-\|\hat{A}\|}(\operatorname{cost}(\hat{B})-\operatorname{cost}(\hat{A}))$
	$\displaystyle\leq\operatorname{cost}(\hat{A})+\tfrac{k-\|\hat{A}\|}{\|\hat{B}\|-\|% \hat{A}\|}(\operatorname{cost}(\hat{B})-\operatorname{cost}(\hat{A}))=f_{\hat{A% },\hat{B}}(k).$	(8)

If $|\hat{B}^{\prime}|>k$ , this implies that $(\hat{A}^{\prime},\hat{B}^{\prime})$ is also optimal. Otherwise, let $\hat{B}^{\prime}\subseteq\hat{B}^{\prime\prime}\subseteq\hat{B}$ such that $|\hat{B}^{\prime\prime}|=k$ . Since $\operatorname{cost}(\hat{B}^{\prime\prime})=\operatorname{cost}(\hat{B})$ , we may replace $\hat{B}^{\prime}$ by $\hat{B}^{\prime\prime}$ in the above inequalities to obtain

f_{\hat{A},\hat{B}}(k)\geq f_{\hat{A},\hat{B}^{\prime\prime}}(k)=\operatorname% {cost}(\hat{B}^{\prime\prime})=\operatorname{cost}(\hat{B}^{\prime}),

which matches the second case of the claim. $\hfill\blacktriangleleft$

Due to Lemma 7 we can assume that our optimal pair $(A,B)$ is simple. We will show next that this implies that $(A,B)$ is clean, which we define as follows.

Definition 9.

Let $A^{\prime},B^{\prime}\subseteq I$ . The pair $(A^{\prime},B^{\prime})$ is clean if the symmetric difference $A^{\prime}\,\Delta\,B^{\prime}=(A^{\prime}\setminus B^{\prime})\cup(B^{\prime}% \setminus A^{\prime})$ does not contain two suppliers $i,i^{\prime}$ with $b_{i}<b_{i^{\prime}}$ and $c_{i^{\prime}}<c_{i}$ .

Thinking of each supplier $i$ as the interval $[b_{i},c_{i}]$ , this means that a pair $(A^{\prime},B^{\prime})$ is clean if $A^{\prime}\,\Delta\,B^{\prime}$ does not contain an interval that is contained in the interior of another interval from $A^{\prime}\,\Delta\,B^{\prime}$ .

Lemma 10.

If $(A^{\prime},B^{\prime})$ is an optimal pair where both $A^{\prime},B^{\prime}$ are simple, then $(A^{\prime},B^{\prime})$ is clean.

Thus, from now on we may assume that $(A,B)$ is a clean and optimal pair, and we will maintain this property when we adjust $A$ and $B$ in the following. The fact that $(A,B)$ is clean allows us to order the elements (interpreted as intervals) in $A\,\Delta\,B$ : By relabeling the suppliers, we may assume that $A\,\Delta\,B=\{1,\dots,\ell\}\eqqcolon[\ell]$ where $b_{1}\leq b_{2}\leq\dots\leq b_{\ell}$ and $c_{1}\leq c_{2}\leq\dots\leq c_{\ell}$ . Given this ordering, we define two new sets $A^{\prime}$ , $B^{\prime}$ that both contain $A\cap B$ , and we redistribute the suppliers in $A\,\Delta\,B$ alternatively. Formally, we define $A^{\prime}\coloneqq(A\cap B)\cup\{2s:s\in[\lfloor\ell/2\rfloor]\}$ and $B^{\prime}\coloneqq(A\cap B)\cup\{2s-1:s\in[\lceil\ell/2\rceil]\}$ . An example is shown in Figure 3. We call $(A^{\prime},B^{\prime})$ a redistribution of $(A,B)$ . Our main technical contribution is the following lemma which we will prove in Section 3.1.

Figure 3: Illustration for the redistribution. The figure shows only the suppliers in

A\,\Delta\,B

. The dashed and solid rectangles are suppliers in

A

and

B

, respectively. The green and blue rectangles are suppliers in

A^{\prime}

and

B^{\prime}

after redistribution.

Lemma 11 (Redistribution lemma).

Let $(A^{\prime},B^{\prime})$ be a redistribution of a clean optimal pair $(A,B)$ . We have $|A|<|A^{\prime}|\leq|B^{\prime}|<|B|$ and $\operatorname{cost}(A^{\prime})+\operatorname{cost}(B^{\prime})\leq% \operatorname{cost}(A)+\operatorname{cost}(B)$ .

Corollary 12.

Let $(A^{\prime},B^{\prime})$ be a redistribution of a clean optimal pair $(A,B)$ . Then one of the following holds:

a)

$\chi(M_{A^{\prime}})$ or $\chi(M_{B^{\prime}})$ is an optimal (integral) vertex of $P(k)$ or
b)

one of $(A,B^{\prime})$ , $(A,A^{\prime})$ , $(A^{\prime},B)$ , $(B^{\prime},B)$ is a clean optimal pair.

Note that in a) we are done (we can check this by comparing the corresponding costs to the cost of $(\mathbf{x},\mathbf{y})$ ). Otherwise, we replace $(A,B)$ by the new clean optimal pair that we denote by $(\hat{A},\hat{B})$ . Since $|A|<|A^{\prime}|\leq|B^{\prime}|<|B|$ the difference $|\hat{B}|-|\hat{A}|$ is strictly smaller than the difference $|B|-|A|$ . Thus, we can conclude:

Lemma 13.

Given a clean optimal pair $(A,B)$ , in polynomial time we can compute an optimal integral vertex of $P(k)$ or a clean optimal pair $(\hat{A},\hat{B})$ such that $|\hat{B}|-|\hat{A}|<|B|-|A|$ .

Given the initial optimal pair $(A,B)$ , we apply Lemma 13 at most $|I|$ times and eventually obtain an optimal integral vertex of $P(k)$ . This completes the proof of Theorem 2.

Above, we solved the LP to compute the fractional vertex $(\mathbf{x},\mathbf{y})$ and, based on it, the initial optimal pair. In Section 4, we will see that we can instead also compute the initial optimal pair by a combinatorial algorithm, which yields a purely combinatorial algorithm to solve the multiplicative assignment problem.

3.1 Proof of the redistribution lemma

The bounds on $|A^{\prime}|,|B^{\prime}|$ follow immediately from the fact that the redistribution guarantees $|A^{\prime}|\leq|B^{\prime}|\leq|A^{\prime}|+1$ and that $|A|<k<|B|$ .

We start by giving some intuition for the comparison of costs. Instead of directly comparing costs we can equivalently compare the change in cost, i.e., it suffices to prove that

(\operatorname{cost}(A^{\prime})-\operatorname{cost}(\emptyset))+(% \operatorname{cost}(B^{\prime})-\operatorname{cost}(\emptyset))\leq(% \operatorname{cost}(A)-\operatorname{cost}(\emptyset))+(\operatorname{cost}(B)% -\operatorname{cost}(\emptyset)).

(9)

The difficulty comes from the complicated structure of the $\operatorname{cost}(\cdot)$ function. Even the change in cost for upgrading a single supplier $i$ , i.e., $\operatorname{cost}(\{i\})-\operatorname{cost}(\emptyset)$ , is not obvious since the optimal matching may be different depending on whether we upgrade $i$ . On the other hand, in the special case where the open interval $(b_{i},c_{i})$ does not contain any of the cost values $b_{i^{\prime}},c_{i^{\prime}}$ , $i^{\prime}\in I$ , the order of suppliers by cost does not change if we upgrade $i$ and therefore the optimal matching also does not change. Thus, in this case we have the simple identity $\operatorname{cost}(\{i\})-\operatorname{cost}(\emptyset)=(b_{i}-c_{i})\cdot d% _{j}$ where $j\in J$ is the customer that supplier $i$ is matched to. Our proof strategy is to view the cost changes $\operatorname{cost}(A)-\operatorname{cost}(\emptyset)$ , $\operatorname{cost}(B)-\operatorname{cost}(\emptyset)$ , etc. as the sum of step-wise upgrades where each step does not change the optimal matching. Within each step we can then more easily compare the change in costs between the different sets.

Formally, for each $t\geq 0$ , we will consider a “truncated” instance $\Pi_{t}$ in which costs cannot get upgraded below $t$ . More precisely, $\Pi_{t}$ has the same suppliers $I$ , customers $J$ , standard supplier costs $c$ , and customer demands $d$ . For a supplier $i\in I$ , the upgraded cost in $\Pi_{t}$ will be equal to $\min\{t,c_{i}\}$ if $b_{i}\leq t$ , and remains $b_{i}$ otherwise. For suppliers $S\subseteq I$ to upgrade, we define the resulting cost in $\Pi_{t}$ as $\operatorname{cost}(S,t)$ .

Let $\ell:=|\{b_{i}:i\in I\}\cup\{c_{i}:i\in I\}|$ denote the number of different costs and let $t_{1}<t_{2}<\dots<t_{\ell}$ with $\{t_{1},\dots,t_{\ell}\}=\{b_{i}:i\in I\}\cup\{c_{i}:i\in I\}$ . We will show that for every $h\in[\ell-1]$ it holds that

\operatorname{cost}(A^{\prime},t_{h})-\operatorname{cost}(A^{\prime},t_{h+1})+% \operatorname{cost}(B^{\prime},t_{h})-\operatorname{cost}(B^{\prime},t_{h+1})% \\ \leq\operatorname{cost}(A,t_{h})-\operatorname{cost}(A,t_{h+1})+\operatorname{% cost}(B,t_{h})-\operatorname{cost}(B,t_{h+1})

(10)

Summing over all $h\in[\ell-1]$ , we obtain Inequality (9) which yields the lemma’s statement.

Let us fix $h\in[\ell-1]$ . We may assume that $J=[n]$ and $d_{1}\geq d_{2}\geq\dots\geq d_{n}$ . Consider a subset $S\subseteq I$ for which we would like to determine $\operatorname{cost}(S,t_{h})-\operatorname{cost}(S,t_{h+1})$ . To this end, note that for a supplier $i\in I$ we can only have $c_{i}\leq t_{h}$ , $b_{i}\leq t_{h}<t_{h+1}\leq c_{i}$ , or $t_{h+1}\leq b_{i}$ . We denote by $I_{\leq}$ the suppliers of the first type, i.e., $I_{\leq}\coloneqq\{i\in I:c_{i}\leq t_{h}\}$ . By $S_{*}$ we denote the suppliers of the second type that are also contained in $S$ , i.e., $S_{*}\coloneqq\{i\in S:b_{i}\leq t_{h},\,t_{h+1}\leq c_{i}\}$ . By $S_{\geq}\coloneqq I\setminus(I_{\leq}\cup S_{*})$ we denote all remaining suppliers. Note that $S_{\geq}$ depends on $S$ but is not necessarily a subset of $S$ .

Assuming that we only upgrade the suppliers in $S$ , for $t\in\{t_{h},t_{h+1}\}$ let us consider the effective costs of each supplier $i\in I$ in the instance $\Pi_{t}$ , i.e., $\max\{b_{i},\min\{t,c_{i}\}\}$ if $i\in S$ and $c_{i}$ if $i\not\in S$ . The effective cost of any supplier in $I_{\leq}$ is at most $t_{h}$ and independent of whether $t=t_{h}$ or $t=t_{h+1}$ . Similarly, the effective cost of any supplier in $S_{\geq}$ is at least $t_{h+1}$ and again independent of whether $t=t_{h}$ or $t=t_{h+1}$ . The effective cost of any supplier $i\in S_{*}$ is equal to $t$ . In $\Pi_{t}$ , an optimal perfect matching that upgrades exactly the suppliers in $S$ can be constructed by assigning the suppliers in $I_{\leq}$ to the first $|I_{\leq}|$ customers, the suppliers in $S_{\geq}$ to the last $|S_{\geq}|$ customers, and the suppliers in $S_{*}$ to the remaining customers. Note that we may use the same assignment for $t=t_{h}$ and $t=t_{h+1}$ . The costs of two matchings differ by

\operatorname{cost}(S,t_{h})-\operatorname{cost}(S,t_{h+1})=(t_{h}-t_{h+1})% \sum_{j=|I_{\leq}|+1}^{|I_{\leq}|+|S_{*}|}d_{j}.

(11)

This motivates the following statement (see the full version [3] for its proof) where we define $A_{*},A^{\prime}_{*},B_{*}$ and $B^{\prime}_{*}$ correspondingly like $S_{*}$ above.

Lemma 14.

We have

\sum_{j=|I_{\leq}|+1}^{|I_{\leq}|+|A^{\prime}_{*}|}d_{j}+\sum_{j=|I_{\leq}|+1}% ^{|I_{\leq}|+|B^{\prime}_{*}|}d_{j}\geq\sum_{j=|I_{\leq}|+1}^{|I_{\leq}|+|A_{*% }|}d_{j}+\sum_{j=|I_{\leq}|+1}^{|I_{\leq}|+|B_{*}|}d_{j}.

(12)

Moreover, this inequality is strict if $d_{1},\dots,d_{n}$ are pairwise different and $||A_{*}|-|B_{*}||>1$ .

Multiplying the above inequality by $t_{h}-t_{h+1}<0$ and using (11) for the sets $A,B,A^{\prime}$ , $B^{\prime}$ , we obtain (10).

4 Combinatorial algorithm

In Section 3 we have seen that, given an optimal pair $(A,B)$ , we can compute an optimal solution by a purely combinatorial algorithm. In this section, we present a combinatorial algorithm for computing such an optimal pair, so in particular without solving a linear program. This yields a completely combinatorial algorithm for the multiplicative assignment problem with upgrades.

Our algorithm is based on a key structural insight into the problem. Given an instance, we consider the function $h:\{0,\ldots,|I|\}\rightarrow\mathbb{R}_{\geq 0}$ such that for each $k^{\prime}$ the value $h(k^{\prime})$ equals the cost of the optimal solution if we were allowed to upgrade $k^{\prime}$ suppliers, i.e., $h(k^{\prime})=\min\{\operatorname{cost}(X):X\subseteq I,\,|X|=k^{\prime}\}$ . Note that $h(k^{\prime})$ is defined even if $k^{\prime}>k$ where $k$ is the number of suppliers we are allowed to upgrade in the given instance. Clearly, $h$ is non-increasing since allowing more upgrades cannot increase the cost of the optimal solution. A direct consequence of Theorem 2 is that $h$ is also convex.

Lemma 15.

For any instance of the multiplicative assignment problem with upgrades, the (linear interpolation of the) function $h$ is convex.

Proof.

We have to show that $h(k_{B})\leq\frac{k_{C}-k_{B}}{k_{C}-k_{A}}h(k_{A})+\frac{k_{B}-k_{A}}{k_{C}-k% _{A}}h(k_{C})$ holds for all integers $0\leq k_{A}<k_{B}<k_{C}\leq|I|$ . Let $A,C\subseteq I$ be such that $k_{A}=|A|$ , $k_{C}=|C|$ , $\operatorname{cost}(A)=h(k_{A})$ , and $\operatorname{cost}(C)=h(k_{C})$ . Let $\beta$ denote the optimum solution value of our LP for upgrading up to $k_{B}$ suppliers. Recall that $\beta\leq f_{A,C}(k_{B})$ . Moreover, by Theorem 2, we have $h(k_{B})=\beta$ . Thus, we obtain $h(k_{B})\leq f_{A,C}(k_{B})=\frac{k_{C}-k_{B}}{k_{C}-k_{A}}h(k_{A})+\frac{k_{B% }-k_{A}}{k_{C}-k_{A}}h(k_{C})$ . $\hfill\blacktriangleleft$ In our algorithm, we start with a weakly optimal pair $(A,B)$ which we define to be a pair $A,B\subseteq I$ such that $\operatorname{cost}(A)=h(|A|)$ and $\operatorname{cost}(B)=h(|B|)$ , i.e., among all sets $S\subseteq I$ with $|S|=|A|$ the set $A$ has the smallest cost, and among all sets $S^{\prime}\subseteq I$ with $|S^{\prime}|=|B|$ the set $B$ has the optimal cost. We start with the pair $(\emptyset,I)$ which is clearly weakly optimal since $\emptyset$ and $I$ are the only subsets of $I$ with 0 and $|I|$ elements, respectively. Suppose we are given a weakly optimal pair $(A,B)$ . We describe a routine that asserts that $(A,B)$ is even an optimal pair, or directly outputs an optimal integral solution, or computes another weakly optimal pair $(A^{\prime},B^{\prime})$ with $|B^{\prime}|-|A^{\prime}|<|B|-|A|$ . Thus, if we iterate this routine for at most $|I|$ iterations, we eventually find an optimal pair. We define an auxiliary cost function where for each subset $X\subseteq I$ we set $g_{A,B}(X)\coloneqq\operatorname{cost}(X)+\frac{\operatorname{cost}(A)-% \operatorname{cost}(B)}{|B|-|A|}\cdot|X|.$ Intuitively, this cost function is a type of Lagrangian relaxation of our actual cost function where we replace Constraint (5) by the penalty term $\frac{\operatorname{cost}(A)-\operatorname{cost}(B)}{|B|-|A|}\cdot|X|$ in the objective.

Observation 16.

We have that $g_{A,B}(A)=g_{A,B}(B)$ .

To gain some intuition, let us consider a plot of the (unknown) function $h$ and a line $\ell$ that contains the points $(|A|,\operatorname{cost}(A))$ and $(|B|,\operatorname{cost}(B))$ , see Figure 4. Intuitively, $\ell$ contains all points with the same objective function value according to $g_{A,B}$ . Since $(A,B)$ is weakly optimal, we have that $h(|A|)=\operatorname{cost}(A)$ and $h(|B|)=\operatorname{cost}(B)$ . Moreover, since $h$ is convex, one can show that for each value $k^{\prime}$ with $k^{\prime}\leq|A|$ or $k^{\prime}\geq|B|$ the point $(k^{\prime},h(k^{\prime}))$ lies on or above $\ell$ . However, there might be a value $k^{*}$ with $|A|<k^{*}<|B|$ such that $(k^{*},h(k^{*}))$ lies below $\ell$ . If this is the case, then there must be a corresponding set $X^{*}\subseteq I$ with $|X^{*}|=k^{*}$ , $h(k^{*})=\operatorname{cost}(X^{*})$ , and $g_{A,B}(X^{*})<g_{A,B}(A)=g_{A,B}(B)$ ; we call such a set $X^{*}$ an extreme set. It turns out that if there is no extreme set $X^{*}$ , then we are already done.

Lemma 17.

If there is no extreme set $X^{*}\subseteq I$ , then $(A,B)$ is an optimal pair.

Proof.

Let $S\subseteq I$ with $|S|=k$ be any optimal set. Since there is no extreme set, we have $g(A)\leq g(S)$ . By Theorem 2, the optimum value of the LP is equal to

	$\displaystyle\operatorname{cost}(S)=g(S)-\frac{\operatorname{cost}(A)-% \operatorname{cost}(B)}{\|B\|-\|A\|}\cdot k$	$\displaystyle\geq g(X^{*})-\frac{\operatorname{cost}(A)-\operatorname{cost}(B)% }{\|B\|-\|A\|}\cdot k$
		$\displaystyle\geq g(A)-\frac{\operatorname{cost}(A)-\operatorname{cost}(B)}{\|B% \|-\|A\|}\cdot k$
		$\displaystyle=f_{A,B}(k).\$

$\hfill\blacktriangleleft$

Figure 4: Illustration of the combinatorial algorithm.

In fact, we can easily check whether an extreme set $X^{*}$ exists. More formally, we even compute a set $X^{*}$ that optimizes $g_{A,B}(X)$ over all sets $X\subseteq I$ . All we need to do for this is to solve an auxiliary instance of weighted bipartite matching. In this instance, we take the bipartite graph corresponding to our instance as defined in Section 2 and increase the costs of each red edge by $\frac{\operatorname{cost}(A)-\operatorname{cost}(B)}{|B|-|A|}$ . Then, we compute a minimum cost perfect matching for the instance, i.e., without a constraint bounding the number of selected red edges.

Lemma 18.

In polynomial time we can compute a set $X^{*}\subseteq I$ such that $g_{A,B}(X^{*})\leq g_{A,B}(X)$ holds for each set $X\subseteq I$ . If $g_{A,B}(X^{*})<g_{A,B}(A)$ , then $X^{*}$ is an extreme set; otherwise, no extreme set exists.

Thus, if there is no extreme set, then $(A,B)$ is an optimal pair by Lemma 17. Otherwise, let $X^{*}$ the set due to Lemma 18. Note that, once we fix the cardinality of $X$ , the value of $g(X)$ depends only on $\operatorname{cost}(X)$ . This yields the following observation.

Observation 19.

For every $X\subseteq I$ with $|X^{*}|=|X|$ we have $\operatorname{cost}(X^{*})\leq\operatorname{cost}(X)$ .

Recall that since $X^{*}$ is extreme, we have $|A|<|X^{*}|<|B|$ . If $|X^{*}|=k$ , then we are done since the matching $M_{X^{*}}$ is optimal by Observation 19. If $k<X^{*}$ then the pair $(A,X^{*})$ is a weakly optimal pair with $|X^{*}|-|A|<|B|-|A|$ . Similarly, if $k>X^{*}$ then the pair $(X^{*},B)$ is weakly optimal with $|B|-|X^{*}|<|B|-|A|$ .

Thus, if we repeat this procedure for at most $|I|$ iteration, we eventually find an optimal pair $(A,B)$ . Then, we apply Lemma 7 to transform $(A,B)$ to a simple optimal pair, and finally we apply Lemma 13 iteratively until we found an optimal integral solution.

5 Applications and extensions

In this section, we first present details on the connection of multiplicative assignment problems to scheduling. We then explore natural extensions, for which there are randomized pseudopolynomial time algorithms via simple reductions to exact matching and for which the computational complexity with binary encoded costs is open. Finally, we give counter-examples demonstrating that the integrality properties we prove in Section 3 do not generalize to them.

5.1 Scheduling with upgrades

Consider the following scheduling problem: we are given $n$ jobs with processing times $p_{1},p_{2},\dotsc,p_{n}$ as well as upgraded (lower) processing times $q_{1},q_{2},\dotsc,q_{n}$ and a limit $k\in\mathbb{N}$ on the number of jobs to be upgraded. Furthermore, there are $m$ machines with speeds $s_{1},s_{2},\dotsc,s_{m}$ . We have to assign each job to machines, upgrade $k$ of them, and then process them in some order on each machine. Our goal is to minimize the average completion time of the jobs. The variant without upgrades is well known to be reducible to minimum weight perfect matching, see e.g. [18, Chapter 7]. While we present the setting above in the most general form, we note that solving the problem on a single machine does not seem obvious either. This is indeed an open problem posted by Damerius, Kling, Li, Xu, and Zhang [6] recently. In fact, we are not aware of another successful approach than the one presented in this paper.

To model this problem as the multiplicative assignment problem, each job is a supplier. For each machine, we create $n$ ordered slots, which form the $n\cdot m$ customers over all machines. The slots correspond to positions in the schedule on a machine. More precisely, if a job is assigned to the first slot of a machine, this means that it is scheduled last; if it is assigned to the second slot, then it is scheduled second-to-last, etc. The demand for a job is $p_{j}$ , and the upgraded demand is $q_{j}$ . The cost of the $\ell$ th slot of machine $i$ is $\ell/(ns_{i})$ . Here, the rationale is that a job $j$ placed on the $\ell$ th slot will delay $\ell$ many jobs, including itself, by $p_{j}/s_{i}$ (or $q_{j}/s_{i}$ if upgraded). The division of $n$ is to transform the total completion time into average completion time. An example is shown in Figure 5.

Figure 5: Illustration for the scheduling with uniform machines. The figure shows an example consisting of five jobs and four machines. The left and right sides are job and machine nodes, respectively. Each machine node includes five sub-nodes. Each job node connects to each sub-node of each machine.

For an instance of multiplicative assignment, we need at least as many suppliers as customers. Therefore, we remove all slots (i.e., customers) except the $m$ slots with the lowest cost, as there is always an optimal solution that does not use these slots. An optimal solution to the instance of multiplicative assignment will always use a prefix of slots for each machine, since the costs are strictly increasing. It is now straight-forward to transform a solution to the scheduling problem to one with the same cost in the multiplicative assignment problem and vice versa.

5.2 Exact matching and pseudopolynomial time algorithms

Recall that in the exact bipartite perfect matching problem we are given a bipartite graph with edges colored either red or blue and a number $k$ . Our goal is to find a perfect matching that contains exactly $k$ red edges. This problem admits a randomized polynomial time algorithm [20]. More generally, the following problem can be solved in randomized pseudopolynomial time: given a bipartite graph with edge weights $w:E\rightarrow\mathbb{N}$ and a target $t\in\mathbb{N}$ , find a perfect matching of weight exactly $t$ . The weighted variant can be reduced to the red-blue variant by subdividing each edge $2w(e)-1$ times and coloring the path alternatingly with red and blue [11]. In fact, even the variant with $\ell=O(1)$ many weight functions $w_{1},w_{2},\dotsc,w_{\ell}$ and targets $t_{1},t_{2},\dotsc,t_{\ell}$ can be solved in randomized pseudopolynomial time by aggregating the $\ell$ functions into one with appropriate zero-padding, see e.g. [14]. This can be used to derive randomized pseudopolynomial time algorithms for various matching related problems with upgrades.

One can, for example, obtain a pseudopolynomial time randomized algorithm for the multiplicative assignment problem, i.e., whose running time is polynomial in $n$ , $\max_{j\in J}d_{j}$ , and $\max_{i\in I}c_{j}$ . Towards this, we use the natural bipartite graph as described in Section 2, which contains for each $(i,j)\in I\times j$ an upgraded copy (of cost $b_{i}\cdot d_{j}$ ) and a non-upgraded copy (of cost $c_{i}\cdot d_{j}$ ). For each $t\in\{1,2,\dotsc,\sum_{j\in J,i\in I}c_{i}\cdot d_{j}\}$ we check if there is a matching with cost $t$ that selects exactly $k$ upgraded edges and output the lowest $t$ , for which there is. This can be solved using exact bipartite perfect matching with two weight functions.

We note that this is inferior to the main result of this paper, which does not require pseudopolynomial time. However, the approach via exact matching generalizes to more complicated problems. For example, it still applies even if the bipartite graph in multiplicative assignment is not complete, that is, some suppliers cannot be assigned to some customers. Furthermore, more complex cost functions can be implemented, namely, any function in the supplier, customer, and whether the supplier is upgraded. One can even allow both suppliers and customers to be upgraded, either bounding the total number or – using an additional weight function – the number of upgraded supplies and customers individually. Similarly, one may partition the suppliers into a constant number of sets and allow a fixed number of upgrades per set, at the cost of increasing the running time due to more weight functions.

Another variant of exact matching is the following optimization problem, mentioned for example in [19]: given a bipartite graph with red or blue edges, a number $k$ , and a weight function $w:E\rightarrow\mathbb{N}$ , find a minimum weight perfect matching with exactly $k$ red edges. Again, this problem can be solved in pseudopolynomial time by reduction to the previous variants. The problem is not known to be NP-hard for binary encoded weights (which might be exponentially large in the number of suppliers and customers) [19]. If there was a polynomial time algorithm for it, this would solve the multiplicative assignment problem, as well as the extensions mentioned above in polynomial time. As fascinating as this question is, a solution seems out of reach since the only known algorithm for exact matching is via an algebraic framework. It seems illusive to enhance it such that optimizes an objective function (over the set of all matchings with exactly $k$ edges), rather than only computing some matching with exactly $k$ red edges.

5.3 Counter-examples for integrality

Given our positive results in Section 3, one may wonder if they extend to other cases, specifically those mentioned in the previous subsection, for which there are pseudopolynomial time algorithms. Since the computational complexity of the optimization version of exact matching is open (see the previous subsection), none of these cases are known to be NP-hard for binary-encoded costs either.

Non-complete bipartite graph

Let us consider a generalization of the multiplicative assignment problem, where some customers cannot be assigned to some suppliers, that is, the graph as described in Section 2 is not complete. For example, in the instance shown in the subfigure (a) of Figure 6, there is no edge from the third left supplier to the second right customer (the suppliers correspond to the depicted nodes on the left and the customers correspond to the nodes on the right). Suppose we are only allowed to upgrade one supplier (i.e., $k=1$ ). For this case, it is one of the best options to upgrade the top-left supplier, resulting in the optimal matching shown in the subfigure (b) of Figure 6. The matching has cost $0\cdot 3+5\cdot 1+2\cdot 0=5$ .

However, the fractional solution can cheat because the missing edge prevents us from arranging the suppliers increasingly. Consider the fractional solution shown in the subfigure (c) of Figure 6. Here, two upgraded edges and four normal edges each receive a value of $\frac{1}{2}$ . So, the resulting cost is

\frac{1}{2}\cdot\left(0\cdot 3+1\cdot 1+2\cdot 1+5\cdot 0+2\cdot 3+2\cdot 0% \right)=\frac{9}{2}<5.

Figure 6: Illustration of non-complete bipartite graph that breaks the integrality. The input bipartite graph is shown in the subfigure (a). The subfigure (b) is the optimal integral solution. Here, we denote upgraded and normal edges in red and blue, respectively. The subfigure (c) is the optimal fractional solution. Here, each blue/red edge will be taken to a fractional extent of

1/2

. It is easy to verify that such a solution is feasible.

The same instance yields also a counter-example for the following generalization by adding the missing edge and assigning it a cost of $5$ upgraded and not upgraded: The cost of an edge $(i,j)$ is not $c_{i}\cdot d_{j}$ but instead some value $c(i,j)$ , and “upgrading” $i$ changes all incident $c_{i,j}$ ’s to $\Theta_{i}*c_{ij}$ for some $\Theta_{i}<1$ .

Partition of suppliers

Consider now a partition of the suppliers into subsets with the constraint that only a specific number can be upgraded per subset. This is a natural generalization of the cardinality constraint on the set of upgraded suppliers to a partition matroid. We show that the integrality property is lost already for a partition into two sets. The instance is shown in the subfigure (a) of Figure 7: one out of the upper two suppliers and one out of the lower two suppliers are allowed to be upgraded.

Figure 7: Illustration of a partition matroid that breaks the integrality. There are four suppliers, forming two groups. At most one supplier can be upgraded from each group. The subfigure (b) shows an optimal integral solution, where we upgrade the second node from the first group and the first node from the second group. The blue/red edges represent the normal/upgrading edges, respectively. The subfigure (c) shows an optimal fractional solution where each edge is taken to a fractional extent of

1/2

.

Table 1 shows the cost of upgrading each pair of suppliers, and both the last two solutions are optimal integral solutions.

Table 1: All feasible solutions to the instance shown in the subfigure (a) of Figure 7.

upgraded suppliers	cost of the optimal matching
$1,3$	$4\cdot 0.9+3\cdot 2+2\cdot 5+1\cdot 5=24.6$
$1,4$	$4\cdot 0.9+3\cdot 3+2\cdot 3+1\cdot 5=23.6$
$2,3$	$4\cdot 2+3\cdot 2+2\cdot 2+1\cdot 5=23$
$2,4$	$4\cdot 2+3\cdot 2+2\cdot 3+1\cdot 3=23$

Now consider the solution to the LP shown in the subfigure (c) of Figure 7. Here each edge is taken to a fractional extent of $1/2$ . The cost is

\frac{1}{2}\cdot(4\cdot 0.9+3\cdot 2+3\cdot 2+1\cdot 5+4\cdot 2+2\cdot 3+2% \cdot 3+1\cdot 5)=22.8

This is lower than the cost of any of the integral solutions.

Upgrading suppliers and customers

Consider now that not only the suppliers can be upgraded, but also the customers (which decreases their demand). You are allowed to upgrade at most $k$ suppliers and customers in total. The cost of an edge is the (potentially upgraded) demand of the customer multiplied by the (potentially upgraded) cost of the supplier. This is a natural generalization of the cardinality constraint on upgraded suppliers. We show that we do not have an optimal integral solution to the LP. Consider the instance shown in the subfigure (a) of Figure 8.

Figure 8: Illustration of upgrading both suppliers and customers that breaks integrality. The subfigure (a) is the input instance. The subfigure (b) is an optimal integral solution. The red/blue edges are upgrading/normal edges. The subfigure (c) is a fractional solution, where each blue/red edge will be taken to the extent of

1/2

.

For $k=1$ , we can upgrade the third customer, resulting in an optimal matching of cost $7\cdot 8+5\cdot 9+3\cdot 15=146$ . For $k=3$ , we can upgrade the second and third supplier and the first customer, resulting in an optimal matching of cost $7\cdot 4+2\cdot 15+1\cdot 20=78$ . So by taking the convex combination of the characteristic vectors of these two matchings, we obtain an LP solution for $k=2$ with a cost of $\frac{146+78}{2}=112$ . This fractional solution is shown in the subfigure (c) of Figure 8. There is no benefit in upgrading the first supplier or the second customer. For $k=2$ , Table 2 shows the cost of upgrading each remaining pair. An optimal integral solution is shown in the subfigure (b) of Figure 8.

Table 2: All feasible solutions to the instance shown in the subfigure (a) of Figure 8. The table does not involve the first supplier and second customer as upgrading them would not change their respective costs).

upgraded suppliers	upgraded customers	cost of the optimal matching
$2,3$	none	$7\cdot 9+2\cdot 15+1\cdot 20=113$
$2$	$1$	$7\cdot 4+3\cdot 15+2\cdot 20=113$
$2$	$3$	$7\cdot 8+3\cdot 9+2\cdot 15=113$
$3$	$1$	$7\cdot 4+5\cdot 15+1\cdot 20=123$
$3$	$3$	$7\cdot 8+5\cdot 9+1\cdot 15=116$
none	$1,3$	$7\cdot 4+5\cdot 8+3\cdot 15=113$

As there is no integral solution of cost at most $112$ , there is no optimal integral solution.

6 Conclusion

We studied the multiplicative assignment problem with upgrades and showed that, despite fractional optimal vertices in the natural LP relaxation, an optimal integral vertex always exists and can be found in polynomial time. We also gave a strongly polynomial combinatorial algorithm based on the convexity of the optimal-value function $h(k)$ , and applied the result to the upgrade variants of total completion-time scheduling on identical and uniformly related machines.

An interesting open question is to identify the precise structural boundary of this phenomenon. The counterexamples show that the result does not carry over to arbitrary non-complete compatibility graphs, partition-matroid upgrade constraints, or simultaneous supplier and customer upgrades. However, it remains unclear whether meaningful intermediate classes still admit the same kind of exact polynomial-time solvability. Another interesting open question is to understand what algorithmic guarantees are still possible under richer upgrade constraints, e.g., stemming from partition matroids or general matroids. The counterexamples in this paper show that our techniques do not extend to the setting of partition matroids, so the exact approach developed here cannot be extended directly. Although the associated saving function is submodular, approximating savings does not necessarily yield a meaningful approximation for the original cost-minimization objective. It would therefore be interesting to determine whether these variants admit specialized approximation algorithms for the cost objective itself, or whether one can prove hardness results showing that such guarantees are impossible beyond additive or baseline-relative bounds.

References

[1] Hassene Aissi and A Ridha Mahjoub. On the minimum s-t cut problem with budget constraints. Mathematical Programming, 203(1):421–442, 2024. doi:10.1007/S10107-023-01987-9.
[2] Susanne Albers and Alexander Eckl. Explorable uncertainty in scheduling with non-uniform testing times. In Approximation and Online Algorithms: 18th International Workshop, WAOA 2020, Virtual Event, September 9–10, 2020, Revised Selected Papers 18, pages 127–142. Springer, 2021. doi:10.1007/978-3-030-80879-2_9.
[3] Alexander Armbruster, Lars Rohwedder, Stefan Weltge, Andreas Wiese, and Ruilong Zhang. Multiplicative assignment with upgrades. CoRR, abs/2504.07663, 2025. doi:10.48550/arXiv.2504.07663.
[4] Evripidis Bampis, Konstantinos Dogeas, Alexander Kononov, Giorgio Lucarelli, and Fanny Pascual. Speed scaling with explorable uncertainty. In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 83–93, 2021. doi:10.1145/3409964.3461812.
[5] Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Multi-budgeted matchings and matroid intersection via dependent rounding. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms (SODA), pages 1080–1097. SIAM, 2011. doi:10.1137/1.9781611973082.82.
[6] Christoph Damerius, Peter Kling, Minming Li, Chenyang Xu, and Ruilong Zhang. Scheduling with a limited testing budget: Tight results for the offline and oblivious settings. In 31st Annual European Symposium on Algorithms (ESA), volume 274, pages 38:1–38:15, 2023. doi:10.4230/LIPIcs.ESA.2023.38.
[7] Christoph Dürr, Thomas Erlebach, Nicole Megow, and Julie Meißner. An adversarial model for scheduling with testing. Algorithmica, 82(12):3630–3675, 2020. doi:10.1007/S00453-020-00742-2.
[8] Mingyang Gong, Zhi-Zhong Chen, and Kuniteru Hayashi. Approximation algorithms for multiprocessor scheduling with testing to minimize the total job completion time. Algorithmica, 86(5):1400–1427, 2024. doi:10.1007/S00453-023-01198-W.
[9] Fabrizio Grandoni, Ramamoorthi Ravi, Mohit Singh, and Rico Zenklusen. New approaches to multi-objective optimization. Mathematical Programming, 146:525–554, 2014. doi:10.1007/S10107-013-0703-7.
[10] Alexander Grigoriev, Maxim Sviridenko, and Marc Uetz. Machine scheduling with resource dependent processing times. Mathematical programming, 110:209–228, 2007. doi:10.1007/S10107-006-0059-3.
[11] Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, and Thomas Thierauf. Planarizing gadgets for perfect matching do not exist. ACM Trans. Comput. Theory, 8(4):14:1–14:15, 2016. doi:10.1145/2934310.
[12] Walter J Gutjahr, Christine Strauss, and E Wagner. A stochastic branch-and-bound approach to activity crashing in project management. INFORMS Journal on Computing, 12(2):125–135, 2000. doi:10.1287/IJOC.12.2.125.11894.
[13] Xinrui Jia, Ola Svensson, and Weiqiang Yuan. The exact bipartite matching polytope has exponential extension complexity. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1635–1654. SIAM, 2023. doi:10.1137/1.9781611977554.CH61.
[14] Ravindran Kannan. Polynomial-time aggregation of integer programming problems. Journal of the ACM, 30(1):133–145, 1983. doi:10.1145/322358.322368.
[15] VS Anil Kumar, Madhav V Marathe, Srinivasan Parthasarathy, and Aravind Srinivasan. A unified approach to scheduling on unrelated parallel machines. Journal of the ACM (JACM), 56(5):1–31, 2009. doi:10.1145/1552285.1552289.
[16] Lap Chi Lau, Ramamoorthi Ravi, and Mohit Singh. Iterative methods in combinatorial optimization, volume 46. Cambridge University Press, 2011.
[17] Renato Paes Leme. Gross substitutability: An algorithmic survey. Games and Economic Behavior, 106:294–316, 2017. doi:10.1016/J.GEB.2017.10.016.
[18] Jan Karel Lenstra and David B. Shmoys. Elements of scheduling. CoRR, abs/2001.06005, 2020. arXiv:2001.06005.
[19] Nicolas El Maalouly. Exact matching: Algorithms and related problems. In 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023, March 7-9, 2023, Hamburg, Germany, volume 254, pages 29:1–29:17, 2023. doi:10.4230/LIPIcs.STACS.2023.29.
[20] Ketan Mulmuley, Umesh V Vazirani, and Vijay V Vazirani. Matching is as easy as matrix inversion. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (STOC), pages 345–354, 1987. doi:10.1145/28395.383347.
[21] George L Nemhauser and Laurence A Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of operations research, 3(3):177–188, 1978. doi:10.1287/MOOR.3.3.177.
[22] Ramamoorthi Ravi, Madhav V Marathe, Sekharipuram S Ravi, Daniel J Rosenkrantz, and Harry B Hunt III. Many birds with one stone: Multi-objective approximation algorithms. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing (STOC), pages 438–447, 1993.
[23] Alexander Schrijver et al. Combinatorial optimization: polyhedra and efficiency. Springer, 2003.

Appendix A Supermodularity

In this section, we will prove that the function $\operatorname{cost}(\cdot)$ is supermodular. We first prove the following auxiliary statement.

Lemma 20.

Consider two instances of the multiplicative assignment problem with upgrades. Both instances have the same suppliers $I=\{1,\dotsc,n\}$ , customers $J=\{1,\dotsc,n\}$ , demands $\mathbf{d}$ , but different costs $\mathbf{b},\mathbf{c}$ and $\mathbf{b}^{\prime},\mathbf{c}^{\prime}$ . Further, both cost vectors are ordered non-decreasingly, i.e., $c_{i}\leq c_{i+1}$ and $c^{\prime}_{i}\leq c^{\prime}_{i+1}$ for all $i\leq n-1$ , and the costs in $\mathbf{c}^{\prime}$ are at least as large as $\mathbf{c}$ , i.e., $c^{\prime}_{i}\geq c_{i}\geq b_{i}$ for all $i\in I$ . Finally, there is a special supplier $s$ with $c_{s}=c^{\prime}_{s}$ and $b_{s}=b^{\prime}_{s}$ . Then

\operatorname{cost}(\emptyset)-\operatorname{cost}(\{s\})\leq\operatorname{% cost}^{\prime}(\emptyset)-\operatorname{cost}^{\prime}(\{s\}),

where $\operatorname{cost}(\emptyset),\operatorname{cost}^{\prime}(\emptyset)$ are the optimal objective values for the instances with costs $c,c^{\prime}$ and no upgraded suppliers, and $\operatorname{cost}(\{s\}),\operatorname{cost}^{\prime}(\{s\})$ are those after upgrading $c_{s},c^{\prime}_{s}$ to $b_{s},b^{\prime}_{s}$ .

Proof.

Assume without loss of generality that $d_{j}\geq d_{j+1}$ for all $j\leq n-1$ . As shown in Lemma 1 the assignment $\pi(j)\coloneqq j$ for $j\in J$ is optimal when not upgrading any suppliers in both instances. Let $t\in I$ be minimal with $b_{s}\leq c_{t}$ . Then

\pi_{s}(j)\coloneqq\begin{cases}j&\text{ for }j<t\text{ or }j>s\\ s&\text{ for }j=t\\ j-1&\text{ for }t<j\leq s\end{cases}\quad\text{ and }\quad\pi_{s}^{-1}(i)% \coloneqq\begin{cases}j&\text{ for }i<t\text{ or }i>s\\ t&\text{ for }i=s\\ i+1&\text{ for }t\leq i<s\end{cases}

are an optimal assignment and its inverse for upgrading $\{s\}$ in the instance with costs $\mathbf{c}$ as shown in the proof of Lemma 1. It follows that

	$\displaystyle\operatorname{cost}(\emptyset)-\operatorname{cost}(\{s\})$	$\displaystyle=c_{s}d_{s}-bd_{t}+\sum_{i=t}^{s-1}c_{i}(d_{i}-d_{i+1})$
		$\displaystyle\leq c^{\prime}_{s}d_{s}-bd_{t}+\sum_{i=t}^{s-1}c^{\prime}_{i}(d_% {i}-d_{i+1})$
		$\displaystyle\leq\operatorname{cost}^{\prime}(\emptyset)-\operatorname{cost}^{% \prime}(\{s\}).$

The first inequality holds because all coefficients for $c_{i}$ (respectively, $c^{\prime}_{i}$ ) are non-negative. The second inequality holds because the assignment $\pi_{s}$ has cost at least $\operatorname{cost}^{\prime}(\{s\})$ for upgrading $s$ in the instance with costs $c^{\prime}$ . $\hfill\blacktriangleleft$

Lemma 21.

The set function $\operatorname{cost}(A)$ is supermodular.

Proof.

A set function $\operatorname{cost}$ is supermodular if and only if for all sets $A\subseteq I$ and two distinct elements $s,t\in I\setminus A$ we have

\operatorname{cost}(A)+\operatorname{cost}(A\cup\{s,t\})\geq\operatorname{cost% }(A\cup\{s\})+\operatorname{cost}(A\cup\{t\})

(13)

Assume without loss of generality that $c_{s}\geq c_{t}$ . Consider two instances with modified costs $\mathbf{c}^{\prime}$ and $\mathbf{c}^{\prime\prime}$ that are otherwise identical to the original instance. The cost vector $\mathbf{c}^{\prime}$ are obtained from upgrading $A\cup\{t\}$ and $\mathbf{c}^{\prime\prime}$ are obtained from upgrading $A$ . Formally,

c^{\prime}_{i}=\begin{cases}b_{i}&\text{ if }i\in A\cup\{t\}\\ c_{i}&\text{ otherwise }\end{cases}\quad\text{ and }\quad c^{\prime\prime}_{i}% =\begin{cases}b_{i}&\text{ if }i\in A\\ c_{i}&\text{ otherwise }\end{cases}

We reorder the components of each of the vectors $\mathbf{c}^{\prime}$ and $\mathbf{c}^{\prime\prime}$ non-decreasingly and call the resulting vectors $\bar{\mathbf{c}}^{\prime}$ and $\bar{\mathbf{c}}^{\prime\prime}$ , and the corresponding upgraded cost vectors $\bar{\mathbf{b}}^{\prime}$ and $\bar{\mathbf{b}}^{\prime\prime}$ . Let $s^{\prime}$ , $t^{\prime}$ be the new indices of $s$ , $t$ in $\bar{\mathbf{c}}^{\prime\prime}$ . Since $c_{s}\geq c_{t}$ we may break ties in such a way that $s^{\prime}>t^{\prime}$ . Since we can obtain $\bar{\mathbf{c}}^{\prime}$ from $\bar{\mathbf{c}}^{\prime\prime}$ by upgrading $t^{\prime}$ and reordering the elements $1,2,\dotsc,t^{\prime}$ with an appropriate tie-breaking rule, we also have that $s^{\prime}$ is the new index of $s$ in $\bar{\mathbf{c}}^{\prime}$ . Let $\operatorname{cost}^{\prime}(S)$ and $\operatorname{cost}^{\prime\prime}(S)$ be the optimal objective values in the instances with costs $\bar{\mathbf{b}}^{\prime},\bar{\mathbf{c}}^{\prime}$ and $\bar{\mathbf{b}}^{\prime\prime},\bar{\mathbf{c}}^{\prime\prime}$ when $S\subseteq I$ is upgraded. As $c_{i}^{\prime}\leq c_{i}^{\prime\prime}$ implies $\bar{c}^{\prime}_{i}\leq\bar{c}^{\prime\prime}_{i}$ for all $i\in I$ , we have by Lemma 20 that

	$\displaystyle\operatorname{cost}(A)-\operatorname{cost}(A\cup\{s\})$	$\displaystyle=\operatorname{cost}^{\prime\prime}(\emptyset)-\operatorname{cost% }^{\prime\prime}(\{s\})$
		$\displaystyle\geq\operatorname{cost}^{\prime}(\emptyset)-\operatorname{cost}^{% \prime}(\{s\})=\operatorname{cost}(A\cup\{t\})-\operatorname{cost}(A\cup\{s,t% \}).\$

$\hfill\blacktriangleleft$

[bib.bib1] [1] Hassene Aissi and A Ridha Mahjoub. On the minimum s-t cut problem with budget constraints. Mathematical Programming, 203(1):421–442, 2024. doi:10.1007/S10107-023-01987-9.

[bib.bib2] [2] Susanne Albers and Alexander Eckl. Explorable uncertainty in scheduling with non-uniform testing times. In Approximation and Online Algorithms: 18th International Workshop, WAOA 2020, Virtual Event, September 9–10, 2020, Revised Selected Papers 18, pages 127–142. Springer, 2021. doi:10.1007/978-3-030-80879-2_9.

[bib.bib3] [3] Alexander Armbruster, Lars Rohwedder, Stefan Weltge, Andreas Wiese, and Ruilong Zhang. Multiplicative assignment with upgrades. CoRR, abs/2504.07663, 2025. doi:10.48550/arXiv.2504.07663.

[bib.bib4] [4] Evripidis Bampis, Konstantinos Dogeas, Alexander Kononov, Giorgio Lucarelli, and Fanny Pascual. Speed scaling with explorable uncertainty. In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 83–93, 2021. doi:10.1145/3409964.3461812.

[bib.bib5] [5] Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Multi-budgeted matchings and matroid intersection via dependent rounding. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms (SODA), pages 1080–1097. SIAM, 2011. doi:10.1137/1.9781611973082.82.

[bib.bib6] [6] Christoph Damerius, Peter Kling, Minming Li, Chenyang Xu, and Ruilong Zhang. Scheduling with a limited testing budget: Tight results for the offline and oblivious settings. In 31st Annual European Symposium on Algorithms (ESA), volume 274, pages 38:1–38:15, 2023. doi:10.4230/LIPIcs.ESA.2023.38.

[bib.bib7] [7] Christoph Dürr, Thomas Erlebach, Nicole Megow, and Julie Meißner. An adversarial model for scheduling with testing. Algorithmica, 82(12):3630–3675, 2020. doi:10.1007/S00453-020-00742-2.

[bib.bib8] [8] Mingyang Gong, Zhi-Zhong Chen, and Kuniteru Hayashi. Approximation algorithms for multiprocessor scheduling with testing to minimize the total job completion time. Algorithmica, 86(5):1400–1427, 2024. doi:10.1007/S00453-023-01198-W.

[bib.bib9] [9] Fabrizio Grandoni, Ramamoorthi Ravi, Mohit Singh, and Rico Zenklusen. New approaches to multi-objective optimization. Mathematical Programming, 146:525–554, 2014. doi:10.1007/S10107-013-0703-7.

[bib.bib10] [10] Alexander Grigoriev, Maxim Sviridenko, and Marc Uetz. Machine scheduling with resource dependent processing times. Mathematical programming, 110:209–228, 2007. doi:10.1007/S10107-006-0059-3.

[bib.bib11] [11] Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, and Thomas Thierauf. Planarizing gadgets for perfect matching do not exist. ACM Trans. Comput. Theory, 8(4):14:1–14:15, 2016. doi:10.1145/2934310.

[bib.bib12] [12] Walter J Gutjahr, Christine Strauss, and E Wagner. A stochastic branch-and-bound approach to activity crashing in project management. INFORMS Journal on Computing, 12(2):125–135, 2000. doi:10.1287/IJOC.12.2.125.11894.

[bib.bib13] [13] Xinrui Jia, Ola Svensson, and Weiqiang Yuan. The exact bipartite matching polytope has exponential extension complexity. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1635–1654. SIAM, 2023. doi:10.1137/1.9781611977554.CH61.

[bib.bib14] [14] Ravindran Kannan. Polynomial-time aggregation of integer programming problems. Journal of the ACM, 30(1):133–145, 1983. doi:10.1145/322358.322368.

[bib.bib15] [15] VS Anil Kumar, Madhav V Marathe, Srinivasan Parthasarathy, and Aravind Srinivasan. A unified approach to scheduling on unrelated parallel machines. Journal of the ACM (JACM), 56(5):1–31, 2009. doi:10.1145/1552285.1552289.

[bib.bib16] [16] Lap Chi Lau, Ramamoorthi Ravi, and Mohit Singh. Iterative methods in combinatorial optimization, volume 46. Cambridge University Press, 2011.

[bib.bib17] [17] Renato Paes Leme. Gross substitutability: An algorithmic survey. Games and Economic Behavior, 106:294–316, 2017. doi:10.1016/J.GEB.2017.10.016.

[bib.bib18] [18] Jan Karel Lenstra and David B. Shmoys. Elements of scheduling. CoRR, abs/2001.06005, 2020. arXiv:2001.06005.

[bib.bib19] [19] Nicolas El Maalouly. Exact matching: Algorithms and related problems. In 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023, March 7-9, 2023, Hamburg, Germany, volume 254, pages 29:1–29:17, 2023. doi:10.4230/LIPIcs.STACS.2023.29.

[bib.bib20] [20] Ketan Mulmuley, Umesh V Vazirani, and Vijay V Vazirani. Matching is as easy as matrix inversion. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (STOC), pages 345–354, 1987. doi:10.1145/28395.383347.

[bib.bib21] [21] George L Nemhauser and Laurence A Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of operations research, 3(3):177–188, 1978. doi:10.1287/MOOR.3.3.177.

[bib.bib22] [22] Ramamoorthi Ravi, Madhav V Marathe, Sekharipuram S Ravi, Daniel J Rosenkrantz, and Harry B Hunt III. Many birds with one stone: Multi-objective approximation algorithms. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing (STOC), pages 438–447, 1993.

[bib.bib23] [23] Alexander Schrijver et al. Combinatorial optimization: polyhedra and efficiency. Springer, 2003.

$\displaystyle f_{\hat{A}^{\prime},\hat{B}^{\prime}}(k)$	$\displaystyle=\operatorname{cost}(\hat{B}^{\prime})+\tfrac{\|\hat{B}^{\prime}\|-% k}{\|\hat{B}^{\prime}\|-\|\hat{A}^{\prime}\|}(\operatorname{cost}(\hat{A}^{\prime}% )-\operatorname{cost}(\hat{B}^{\prime}))$
	$\displaystyle=\operatorname{cost}(\hat{B})+\tfrac{\|\hat{B}^{\prime}\|-k}{\|\hat{% B}^{\prime}\|-\|\hat{A}^{\prime}\|}(\operatorname{cost}(\hat{A})-\operatorname{% cost}(\hat{B}))$
	$\displaystyle\leq\operatorname{cost}(\hat{B})+\tfrac{\|\hat{B}^{\prime}\|-k}{\|% \hat{B}^{\prime}\|-\|\hat{A}\|}(\operatorname{cost}(\hat{A})-\operatorname{cost}(% \hat{B}))$
	$\displaystyle=\operatorname{cost}(\hat{A})+\tfrac{k-\|\hat{A}\|}{\|\hat{B}^{% \prime}\|-\|\hat{A}\|}(\operatorname{cost}(\hat{B})-\operatorname{cost}(\hat{A}))$
	$\displaystyle\leq\operatorname{cost}(\hat{A})+\tfrac{k-\|\hat{A}\|}{\|\hat{B}\|-\|% \hat{A}\|}(\operatorname{cost}(\hat{B})-\operatorname{cost}(\hat{A}))=f_{\hat{A% },\hat{B}}(k).$	(8)

	$\displaystyle\operatorname{cost}(S)=g(S)-\frac{\operatorname{cost}(A)-% \operatorname{cost}(B)}{\|B\|-\|A\|}\cdot k$	$\displaystyle\geq g(X^{*})-\frac{\operatorname{cost}(A)-\operatorname{cost}(B)% }{\|B\|-\|A\|}\cdot k$
		$\displaystyle\geq g(A)-\frac{\operatorname{cost}(A)-\operatorname{cost}(B)}{\|B% \|-\|A\|}\cdot k$
		$\displaystyle=f_{A,B}(k).\$