11 citations · 14 across the 5 of their papers we have counts for
7 papers
Supermodular Approximation of Norms and Applications
Thomas Kesselheim, Marco Molinaro, Sahil Singla
Many classical problems in theoretical computer science involve norm, even if implicitly; for example, both XOS functions and downward-closed sets are equivalent to some norms. The…
Approximating Optimum Online for Capacitated Resource Allocation
Alexander Braun, Thomas Kesselheim, Tristan Pollner +1
We study online capacitated resource allocation, a natural generalization of online stochastic max-weight bipartite matching. This problem is motivated by ride-sharing and Internet…
Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints
Thomas Kesselheim, Andreas Tönnis
We study various generalizations of the secretary problem with submodular objective functions. Generally, a set of requests is revealed step-by-step to an algorithm in random order…
Approximation Algorithms for Wireless Link Scheduling with Flexible Data Rates
Thomas Kesselheim
We consider scheduling problems in wireless networks with respect to flexible data rates. That is, more or less data can be transmitted per time depending on the signal quality, wh…
Dynamic Packet Scheduling in Wireless Networks
Thomas Kesselheim
We consider protocols that serve communication requests arising over time in a wireless network that is subject to interference. Unlike previous approaches, we take the geometry of…
A Constant-Factor Approximation for Wireless Capacity Maximization with Power Control in the SINR Model
Thomas Kesselheim
In modern wireless networks, devices are able to set the power for each transmission carried out. Experimental but also theoretical results indicate that such power control can imp…