Humboldt-Universität zu Berlin - Wirtschaftswissenschaftliche Fakultät

Publications

Working Papers

  • Revenue Gaps for Discriminatory and Anonymous Sequential Posted Pricing
    with Paul Dütting and Felix Fischer
    [arXiv]
  • Online Best Reply Algorithms for Resource Allocation Problems
    with Daniel Schmand and Andreas Tönnis
    [arXiv]

Publications in Journals

  • Hiring Secretaries over Time: The Benefit of Concurrent Employment
    with Yann Disser, John Fearnley, Martin Gairing, Oliver Göbel, Daniel Schmand, Alexander Skopalik and Andreas Tönnis
    Mathematics of Operations Research 45(1), 2020.
    [pdf]
  • Tight Bounds for Undirected Graph Exploration with Pebbles and Multiple Agents
    with Yann Disser and Jan Hackfeld
    Journal of the ACM 66(6), pp. 40:1-40:41, 2019.
  • Greedy Metric Minimum Online Matchings with Random Arrivals
    with Martin Gairing
    Operations Research Letters 47(2), pp. 88-91, 2019.
  • Sensitivity Analysis for Convex Separable Optimization over Integral Polymatroids
    with Tobias Harks and Britta Peis
    SIAM Journal on Optimization 28(3), pp. 2222-2245, 2018.
    [pdf] 
  • Bottleneck Routing with Elastic Demands
    with Tobias Harks and Manuel Schneider
    Operations Research Letters 46(1), pp. 93-98, 2018.
  • Complexity and Approximation of the Continuous Network Design Problem
    with Martin Gairing and Tobias Harks
    SIAM Journal on Optimization 27(3), pp. 1554-1582, 2017.
    [pdf]
  • Packing a Knapsack of Unknown Capacity
    with Yann Disser, Nicole Megow and Sebastian Stiller
    SIAM Journal on Discrete Mathematics 31(3), pp. 1477-1497, 2017.
    [pdf]
  • Impartial Selection and the Power of up to Two Choices
    with Antje Bjelde and Felix Fischer
    ACM Transactions on Economics and Computation 5(4), Art. Nr. 21, 2017.
    [pdf]
  • Congestion Games with Variable Demands
    with Tobias Harks
    Mathematics of Operations Research 41(1), pp. 255-277, 2016.
  • Optimal Impartial Selection
    with Felix Fischer
    SIAM Journal on Computing 44(5), pp. 1263-1285, 2015.
    [pdf]
  • Computing Network Tolls with Support Constraints
    with Tobias Harks, Ingo Kleinert and Rolf H. Möhring
    Networks 65(3), pp. 262-285, 2015.
  • Equilibria in a Class of Aggregative Location Games
    with Tobias Harks
    Journal of Mathematical Economics 61, pp. 211-220, 2015.
  • Improving the Hk-bound on the price of stability in undirected Shapley network design games
    with Yann Disser, Andreas E. Feldmann and Matus Mihalak
    Theoretical Computer Science 562, pp. 557-564, 2015.
  • Strong Equilibria in Games with the Lexicographical Improvement Property
    with Tobias Harks and Rolf H. Möhring
    International Journal on Game Theory 42(2), pp. 461-482, 2013.
  • Computing pure Nash and strong equilibria in bottleneck congestion games
    with Tobias Harks, Martin Hoefer and Alexander Skopalik
    Mathematical Programming 141(1-2), pp. 193-215, 2013.
  • On the Existence of Pure Nash Equilibria in Weighted Congestion Games
    with Tobias Harks
    Mathematics of Operations Research 37(3), pp. 419-436, 2012.
    [pdf]
  • Conflict-free vehicle routing: Load balancing and deadlock prevention
    with Ewgenij Gawrilow, Rolf H. Möhring and Björn Stenzel
    EURO Journal on transportation and logistics 1(1-2), pp. 87-111, 2012.
  • Characterizing the Existence of Potential Functions in Weighted Congestion Games
    with Tobias Harks and Rolf H. Möhring
    Theory of Computing Systems 49(1), pp. 46-70, 2011.

Publications in Refereed Conference Proceedings

  • Computing all Wardrop Equilibria parametrized by the Flow Demand
    with Philipp Warode
    Proc. 30th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), 2019.
    [arXiv]
  • Distance-preserving graph contractions
    with Aaron Bernstein, Karl Däubel, Yann Disser, Torsten Mütze and Frieder Smolny
    Proc. 9th Innovations in Theoretical Computer Science (ITCS), Art. Nr. 51, 2018.
    [arXiv]
  • Brief Announcement: Approximation Algorithms for Unsplittable Resource Allocation Problems with Diseconomies of Scale
    with Antje Bjelde and Daniel Schmand
    Proc. 29th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pp. 227-229, 2017.
  • Undirected Graph Exploration with ⊝(log log n) Pebbles
    with Yann Disser and Jan Hackfeld
    Proc. 27th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 25-39, 2016.
    [extended version published in Journal of the ACM, 2019]
  • Efficiency of Equilibria in Uniform Matroid Congestion Games
    with Jasper de Jong and Marc Uetz
    Proc. 9th Internat. Symp. on Algorithmic Game Theory (SAGT), pp. 105-116, 2016.
  • Scheduling Bidirectional Traffic on a Path
    with Yann Disser and Elisabeth Lübbecke
    Proc. 42nd Intern. Colloq. on Automata, Languages and Programming (ICALP), pp. 406-418, 2015.
  • Impartial Selection and the Power of up to Two Choices
    with Antje Bjelde and Felix Fischer
    Proc. 11th Internat. Conf. on Web and Internet Economics (WINE), pp. 146-158, 2015
    [extended version published in ACM Transactions on Economics and Computation, 2017]
  • Bottleneck Routing with Elastic Demands
    with Tobias Harks
    Proc. 11th Internat. Conf. on Web and Internet Economics (WINE), pp. 384-397, 2015
    [extended version published in OR Letters, 2018]
  • Sharing Non-anonymous Costs of Multiple Resources Optimally
    with Daniel Schmand
    Proc. 9th Intern. Conf. on Algorithms and Complexity (CIAC), pp. 274-287, 2015
  • Packing a Knapsack of Unknown Capacity
    with Yann Disser, Nicole Megow and Sebastian Stiller
    Proc. 31st Internat. Symp. on Theoretical Aspects of Computer Science (STACS), 276-287, 2014
    [extended version published in SIAM Journal of Discrete Optimization, 2017]
  • Optimal Impartial Selection
    with Felix Fischer
    Proc. 15th ACM Conference on Economics and Computation (EC), pp. 803-820, 2014
    [extended version published in SIAM Journal on Computing, 2015]
  • Complexity and Approximation of the Continuous Network Design Problem
    with Martin Gairing and Tobias Harks
    Proc. 18th Internat. Workshop on Approximation Algorithms (APPROX), pp. 226-241, 2014
    [extended version published in SIAM Journal on Optimization, 2017]
  • Approximate Pure Nash Equilibria in Weighted Congestion Games
    with Christoph Hansknecht and Alexander Skopalik
    Proc. 18th Internat. Workshop on Approximation Algorithms (APPROX), pp. 242-257, 2014
  • Congestion Games with Higher Demand Dimensions
    with Andreas Schütz
    Proc. 10th Internat. Conf. on Web and Internet Economics (WINE), pp. 453-459, 2014
  • Resource Competition on Integral Polymatroids
    with Tobias Harks and Britta Peis
    Proc. 10th Internat. Conf. on Web and Internet Economics (WINE), pp. 189-202, 2014
    [extended version published as "Sensitivity Analysis for Convex Separable Optimization over Integral Polymatroids" in SIAM Journal on Optimization, 2018]
  • Multimarket Oligopolies with Restricted Market Access
    with Tobias Harks
    Proc. 7th Internat. Symp. on Algorithmic Game Theory (SAGT), pp. 182-193, 2014
  • Improving the Hk-Bound on the Price of Stability in Undirected Shapley Network Design Games
    with Yann Disser, Andreas E. Feldmann and Matus Mihalak
    Proc. 8th Internat. Conf. on Algorithms and Complexity (CIAC) pp. 158-169, 2013
    [extended version published in Theoretical Computer Science, 2015]
  • Competition for Resources
    Selected Papers of the Internat. Conf. on Operations Research, pp. 249-254, 2013
  • Congestion Games with Player-Specific Costs Revisited
    with Martin Gairing
    Proc. 6th Internat. Symp. on Algorithmic Game Theory (SAGT), pp. 98-109, 2013
  • Congestion games with Variable Demands
    with Tobias Harks
    Proc. 13th Conf. on Theoretical Aspects of Rationality and Knowledge (TARK), pp. 111-120, 2011
    [extended version published in Mathematics of Operations Research, 2015]
  • Optimal File Distribution in Peer-to-Peer Networks
    with Kai-Simon Goetzmann, Tobias Harks and Konstantin Miller
    Proc. 22nd Internat. Symp. on Algorithms and Computation (ISAAC), pp. 210-219, 2011
  • Demand Allocation Games: Integrating Discrete and Continuous Strategy Spaces
    with Tobias Harks
    Proc. 7th Internat. Workshop on Internet and Network Economics (WINE), pp. 194-205, 2011
    [extened version published as "Equilibria in a Class of Aggregative Location Games" in Journal of Mathematical Economics, 2015]
  • On the Existence of Pure Nash Equilibria in Weighted Congestion Games
    with Tobias Harks
    Proc. 37th Internat. Colloq. on Automata, Languages and Programming (ICALP), pp. 79-89, 2010
    [extended version published in Mathematics of Operations Research, 2012]
  • Computing Pure Nash and Strong Equilibria in Bottleneck Congestion Games
    with Tobias Harks, Martin Hoefer and Alexander Skopalik
    Proc. 18th Annual Europ. Symp. on Algorithms (ESA), pp. 29-38, 2010
    [extended version published in Mathematical Programming, 2013]
  • Strong Nash Equilibria in Games with the Lexicographical Improvement Property
    with Tobias Harks and Rolf H. Möhring
    Proc. 5th Internat. Workshop on Internet and Network Economics (WINE), pp. 463-470, 2009
    [extended version published as "Strong Equilibria in Games with the Lexicographical Improvement Property" in International Journal of Game Theory, 2013]
  • Characterizing the Existence of Potential Functions in Weighted Congestion Games
    with Tobias Harks and Rolf H. Möhring
    Proc. 2nd Internat. Symp. on Algorithmic Game Theory (SAGT), pp. 97-108, 2009
    [extended version published in Theory of Computing Systems, 2011]

Book Chapter

  • Linear, Exponential, but Nothing Else
    in Gems of Combinatorial Optimization and Graph Algorithms, pp. 113-123, 2015.