Martin Knaack von der TU Berlin zu Besuch

Am 09.03.2026 hält Martin Knaack von der TU Berlin um 15:00 Uhr im IBZ-Raum (31-302) den Vortrag “Submodular Generalized Assignment in the Random-Order Model”.

Abstract:

We consider an online item-allocation problem with budgets and a submodular objective. A set of m agents is known in advance, and each agent j has a known budget. A set of n items arrives over time in a uniformly random order. When item i arrives, its cost c_i,j for each agent j is revealed, and the algorithm must irrevocably assign i to an agent without violating any budget constraint. The goal is to maximize a monotone submodular function defined over all possible assignments [n] x [m]. At the time of decision, the algorithm has only oracle access to this submodular function restricted to items seen so far. This model subsumes welfare maximization with submodular valuations, agent-specific item sizes/prices, and agent-specific budgets/capacities.

We measure the performance of an algorithm by its competitive ratio, i.e., the worst-case ratio between the algorithm’s expected value and that of the offline optimum, which knows all item costs and the full submodular function in advance. Prior work only considered the case of a single agent and achieved a 1/54.4-competitive algorithm. We generalize and improve this result to a polynomial-time α-competitive algorithm with α=(1-1/e)(1/√e-½)≈1/14.85 for an arbitrary number of agents.

We also study the special case in which all item costs and all budgets equal 1 which yields an online submodular matching problem. Prior work achieved a polynomial 1/9.66-competitive algorithm for this problem; we improve this to approximately 1/6.86.

Both our algorithms rely on repeatedly computing 1-1/e-approximations for the multilinear extension of offline variants of subproblems. If super-polynomial runtime is allowed, these subproblems can be solved optimally, and our competitive ratios improve by this factor.

This is joint work with Max Klimm.