Multiplicative assignment with upgrades

Alexander Armbruster, Lars Rohwedder, Stefan Weltge, Andreas Wiese, Ruilong ZhangarXiv 2025 · DOI · arXiv

Abstract

This paper explores the multiplicative assignment problem with upgrades, a novel challenge at the intersection of matching theory and submodular optimization. We investigate the problem of matching customers to suppliers while allowing for a limited number of cost-reducing upgrades. Despite the presence of fractional optimal solutions in the natural linear programming relaxation, we demonstrate that an optimal integral solution always exists and can be found in polynomial time. This result provides a deterministic solution to a problem previously addressed only by randomized algorithms and resolves open questions in job scheduling.

Introduction

The multiplicative assignment problem with upgrades addresses a fundamental challenge in supply network optimization. In a standard matching scenario, customers with specific demands are assigned to suppliers with fixed unit costs to minimize the total cost (demand $\times$ cost). This paper introduces the concept of "upgrades," where a decision-maker can invest in up to $k$ suppliers to reduce their unit costs. This addition transforms a straightforward matching problem into a complex optimization task involving both selection (which suppliers to upgrade) and assignment (how to match customers to the newly optimized suppliers).

Problem Formulation

The problem is modeled as a bipartite matching task with an additional cardinality constraint on the number of upgraded edges. It is a specific instance of maximizing a submodular function under a cardinality constraint, closely related to the "exact matching problem." The latter involves finding a matching with exactly $k$ edges of a specific type (e.g., red edges), a problem for which no deterministic polynomial-time algorithm was previously known.

The input bipartite graph with upgrade options (left) and a resulting optimal integral solution (right).

Methodology

The authors employ three primary techniques to solve this problem:

  1. Linear Programming (LP) Relaxation: They analyze the natural LP for bipartite matching with the upgrade constraint. While adding such constraints typically destroys the integrality of the polytope, the authors prove that an integral optimal solution always exists even when fractional corners are present.
  2. Redistribution Technique: To prove integrality, they develop a balancing procedure. If an LP solver returns a fractional solution—essentially a mixture of different matchings—they iteratively redistribute assignments between these matchings until an optimal integral assignment is reached.
  3. Combinatorial Algorithm: A strongly polynomial-time algorithm is provided using Lagrangian relaxation. By converting the hard upgrade constraint into a penalty in the objective function, the algorithm iteratively searches for the optimal penalty value to satisfy the $k$-upgrade limit.
Illustration of fractional solutions (a, b, c) in the LP relaxation, showing how weights can be distributed across edges.

Key Insights

A critical discovery is the "peculiar" status of this problem: it occupies a rare middle ground where fractional optimal points exist, but an integral optimal point is guaranteed to be nearby. The authors exploit the supermodularity of the cost function, where the marginal benefit of upgrading a supplier increases as more upgrades are performed. Geometrically, by treating suppliers as intervals $[b_i, c_i]$, they show that any fractional solution can be transformed into an integral one without increasing the total cost.

Results and Conclusion

The paper presents the first deterministic polynomial-time algorithm for this class of problems, resolving a long-standing open question in job scheduling regarding the minimization of average completion time when jobs can be "crashed" (accelerated). However, the authors note that this integrality property is fragile; it fails if the bipartite graph is incomplete or if upgrades are applied to both sides of the matching simultaneously. While this work represents a significant step forward, the general exact matching problem for binary-encoded weights remains a major open challenge in computer science.

Summary updated

BibTeX
@misc{armbruster2025multiplicative,
  author = {Alexander Armbruster and Lars Rohwedder and Stefan Weltge and Andreas Wiese and Ruilong Zhang},
  title = {{Multiplicative assignment with upgrades}},
  year = {2025},
  eprint = {2504.07663},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2504.07663},
}
Figure