354 citations · 566 across the 34 of their papers we have counts for
43 papers
Two Complexity Results on Spanning-Tree Congestion Problems
Sunny Atalig, Marek Chrobak, Christoph Dürr +4
In the spanning-tree congestion problem (), we are given a graph , and the objective is to compute a spanning tree of that minimizes the maximum edge congestio…
Randomized Binary and Tree Search under Pressure
Agustín Caracci, Christoph Dürr, José Verschae
We study a generalized binary search problem on the line and general trees. On the line (e.g., a sorted array), binary search finds a target node in queries in the wors…
Set Selection with Uncertain Weights: Non-Adaptive Queries and Thresholds
Christoph Dürr, Arturo Merino, José A. Soto +1
We study set selection problems where the weights are uncertain. Instead of its exact weight, only an uncertainty interval containing its true weight is available for each element.…
On price-induced minmax matchings
Christoph Dürr, Mathieu Mari, Ulrike Schmidt-Kraepelin
We study a natural combinatorial pricing problem for sequentially arriving buyers with equal budgets. Each buyer is interested in exactly one pair of items and purchases this pair…
Scheduling with a processing time oracle
Fanny Dufossé, Christoph Dürr, Noël Nadal +2
In this paper we study a single machine scheduling problem with the objective of minimizing the sum of completion times. Each of the given jobs is either short or long. However the…
Randomized Two-Valued Bounded Delay Online Buffer Management
Christoph Dürr, Shahin Kamali
In the bounded delay buffer management problem unit size packets arrive online to be sent over a network link. The objective is to maximize the total weight of packets sent before…