Search Results

Documents authored by Weltge, Stefan

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.13
Multiplicative Assignment with Upgrades

Authors: Alexander Armbruster, Lars Rohwedder, Stefan Weltge, Andreas Wiese, and Ruilong Zhang

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

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.
Cite as

Alexander Armbruster, Lars Rohwedder, Stefan Weltge, Andreas Wiese, and Ruilong Zhang. Multiplicative Assignment with Upgrades. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 13:1-13:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{armbruster_et_al:LIPIcs.ICALP.2026.13,
  author =	{Armbruster, Alexander and Rohwedder, Lars and Weltge, Stefan and Wiese, Andreas and Zhang, Ruilong},
  title =	{{Multiplicative Assignment with Upgrades}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{13:1--13:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.13},
  URN =		{urn:nbn:de:0030-drops-264022},
  doi =		{10.4230/LIPIcs.ICALP.2026.13},
  annote =	{Keywords: Scheduling, Bipartite Matching, LP-based Algorithm, Combinatorial Optimization, Resource Allocation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.80
The Pareto Cover Problem

Authors: Bento Natura, Meike Neuwohner, and Stefan Weltge

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We introduce the problem of finding a set B of k points in [0,1]ⁿ such that the expected cost of the cheapest point in B that dominates a random point from [0,1]ⁿ is minimized. We study the case where the coordinates of the random points are independently distributed and the cost function is linear. This problem arises naturally in various application areas where customers' requests are satisfied based on predefined products, each corresponding to a subset of features. We show that the problem is NP-hard already for k = 2 when each coordinate is drawn from {0,1}, and obtain an FPTAS for general fixed k under mild assumptions on the distributions.
Cite as

Bento Natura, Meike Neuwohner, and Stefan Weltge. The Pareto Cover Problem. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 80:1-80:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{natura_et_al:LIPIcs.ESA.2022.80,
  author =	{Natura, Bento and Neuwohner, Meike and Weltge, Stefan},
  title =	{{The Pareto Cover Problem}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{80:1--80:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.80},
  URN =		{urn:nbn:de:0030-drops-170186},
  doi =		{10.4230/LIPIcs.ESA.2022.80},
  annote =	{Keywords: Pareto, Covering, Optimization, Approximation Algorithm}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact