Guido Schäfer: Publications

[Journals] [Conferences] [Theses] [Others]

NOTE: Please see dblp for an up-to-date list of publications.

Articles in Journals

P. Kleer and G. Schäfer.
Tight inefficiency bounds for perception-parameterized affine congestion games.
Theoretical Computer Science, 754:65–87, 2019.
P. Kleer and G. Schäfer.
The impact of worst-case deviations in non-atomic network routing games.
Theory of Computing Systems, 63(1):54-89, 2019.
K. R. Apt, B. de Keijzer, M. Rahn, G. Schäfer, S. Simon
Coordination games on graphs.
International Journal of Game Theory, 46(3):851-877, 2017.
[pdf]
A. Gupta, J. Könemann, S. Leonardi, R. Ravi, and G. Schäfer.
Efficient cost-sharing mechanisms for prize-collecting problems.
Mathematical Programming, 152(1- 2):147–188, 2015.
[pdf]
A. Anagnostopoulos, L. Becchetti, B. de Keijzer, and G. Schäfer.
Inefficiency of games with social context.
Theory of Computing Systems, 57(3):782–804, 2015.
[pdf]
B. de Keijzer, G. Schäfer, and O. Telelis.
The strong price of anarchy of linear bottleneck congestion games.
Theory of Computing Systems, 57(2):377–396, 2015.
[pdf]
P. A. Chen, B. de Keijzer, D. Kempe and G. Schäfer.
Altruism and its impact on the price of anarchy.
ACM Transactions on Economics and Computation, 2(4), 2014.
[pdf]
K. R. Apt and G. Schäfer.
Selfishness level of strategic games.
Journal of Artificial Intelligence Research, 49, pages 207-240, 2014.
A. Berger, V. Bonifaci, F. Grandoni, and G. Schäfer.
Budgeted matching and budgeted matroid intersection via the gasoline puzzle.
Mathematical Programming, 128(1-2), pages 355-372, 2011.
[pdf]
L. Fleischer, J. Könemann, S. Leonardi, and G. Schäfer.
Strict cost sharing schemes for Steiner forest.
SIAM Journal on Computing, 39(8), pages 3616-3632, 2010.
[pdf]
F. Eisenbrand, F. Grandoni, T. Rothvoss, and G. Schäfer.
Connected facility location via random facility sampling and core detouring.
Journal of Computer and System Sciences, 76(8), pages 709-726, 2010.
[pdf]
V. Bonifaci, T. Harks, and G. Schäfer.
Stackelberg routing in arbitrary networks.
Mathematics of Operations Research, volume 35(2), pages 330-346, 2010.
[pdf]
J. Brenner and G. Schäfer.
Group-strategyproof cost sharing mechanisms for makespan and other scheduling problems.
Theoretical Computer Science, volume 401(1-3), pages 96-106, 2008.
[pdf]
J. Könemann, S. Leonardi, G. Schäfer, and S. van Zwam.
A group-strategyproof cost sharing mechanism for the Steiner forest game.
SIAM Journal on Computing, volume 37(5), pages 1319-1341, 2008.
[pdf]
H. Bast, K. Mehlhorn, G. Schäfer, and H. Tamaki.
Matching algorithms are fast in sparse random graphs.
Theory of Computing Systems, volume 39(1), pages 3-14, 2006.
[pdf]
G. Schäfer and N. Sivadasan.
Topology matters: Smoothed competitiveness of metrical task systems.
Theoretical Computer Science, volume 341(1-3), pages 216-246, 2005.
[pdf]
L. Becchetti, S. Leonardi, A. Marchetti-Spaccamela, G. Schäfer, and T. Vredeveld.
Average case and smoothed competitive analysis of the multi-level feedback algorithm.
Mathematics of Operations Research, volume 31(1), pages 85-108, 2006.
[pdf]
S. Leonardi and G. Schäfer.
Cross-monotonic cost sharing methods for connected facility location games.
Theoretical Computer Science, volume 326(1-3), pages 431-442, 2004.
[pdf]
H. Bast, K. Mehlhorn, G. Schäfer, and H. Tamaki.
A heuristic for Dijkstra's algorithm with many targets and its use in weighted matching algorithms.
Algorithmica, volume 36(1), pages 75-88, 2003.
[pdf]
K. Mehlhorn and G. Schäfer.
Implementation of O(nm log n) weighted matchings in general graphs: The power of data structures.
ACM Journal of Experimental Algorithmics, 7, 2002.
[ps]
K. Mehlhorn, V. Priebe, G. Schäfer, and N. Sivadasan.
All-pairs shortest-paths computation in the presence of negative cycles.
Information Processing Letters, 81(6):341-343, 2002.
[ps]

Articles in Refereed Conference Proceedings

P. Kleer, G. Schäfer
Topological Price of Anarchy Bounds for Clustering Games on Networks
In Proceedings of the 15th International Conference on Web and Internet Economics (WINE), 2019.
R. Brokkelkamp, S. C. Polak, G. Schäfer, Y. Velaj
Approximate Pricing in Networks: How to Boost the Betweenness and Revenue of a Node
In Proceedings of the 30th International Symposium on Algorithms and Computation (ISAAC), 2019.
G. Birmpas, E. Markakis, G. Schäfer
Cost sharing over combinatorial domains: Complement-free cost functions and beyond
In Proceedings of the 27th Annual European Symposium on Algorithms (ESA), 2019.
G. Amanatidis, P. Kleer, G. Schäfer
Budget-feasible mechanism design for non- monotone submodular objectives: Offline and online
In Proceedings of the 2019 ACM Conference on Economics and Computation (EC), 2019.
C. Groenland, G. Schäfer
The curse of ties in congestion games with limited lookahead
In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2018.
F. C. Rodrigues, G. Schäfer, E. C. Xavier
On the effectiveness of connection tolls in fair cost facility location games
In Proceedings of the 19th Italian Conference on Theoretical Computer Science (ICTCS), 2018.
P. Kleer, G. Schäfer
Potential function minimizers of combinatorial congestion games: Efficiency and computation
In Proceedings of the 18th ACM Conference on Economics and Computation (EC), 2017.
P. Kleer, G. Schäfer
Path Deviations Outperform Approximate Stability in Heterogeneous Congestion Games
In Proceedings of the 9th International Symposium on Algorithmic Game Theory (SAGT), 2017.
P. Kleer, G. Schäfer
Potential Function Minimizers of Combinatorial Congestion Games: Efficiency and Computation
In Proceedings of the 18th ACM Conference on Economics and Computation (EC), 2017.
[pdf]
P. Kleer, G. Schäfer
Tight Inefficiency Bounds for Perception-Parameterized Affine Congestion Games.
In Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC), 2017.
[pdf]
I. van Heuven van Staereling, B. de Keijzer, G. Schäfer
The Ground-Set-Cost Budgeted Maximum Coverage Problem.
In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS), 2016.
[pdf]
P. Kleer, G. Schäfer
The Impact of Worst-Case Deviations in Non-Atomic Network Routing Games.
In Proceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT), 2016.
[pdf]
M. Rahn, G. Schäfer
Efficient equilibria in polymatrix coordination games.
In Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2015.
[pdf]
K. Apt, M. Rahn, G. Schäfer, and S. Simon
Coordination games on graphs.
In Proceedings of the 10th Conference On Web and Internet Economics (WINE), 2014.
[pdf] (extended abstract), [arxiv] (full version)
E. Pountourakis, and G. Schäfer.
Mechanisms for hiring a matroid base without money.
In Proceedings of the 6th International Symposium on Algorithmic Game Theory (SAGT), 2014.
[pdf]
T. Jelinek, M. Klaas, and G. Schäfer.
Computing optimal tolls with arc restrictions and heterogeneous players.
In Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS), 2014. [pdf]
M. Rahn and G. Schäfer.
Bounding the inefficiency of altruism through social contribution games.
In Proceedings of the 9th Conference On Web and Internet Economics (WINE), volume 8289 of Lecture Notes in Computer Science, pages 391-404, 2013.
[pdf]
A. Anagnostopoulos, L. Becchetti, B. de Keijzer, and G. Schäfer.
Inefficiency of games with social context.
In Proceedings of the 6th International Symposium on Algorithmic Game Theory (SAGT), volume 8146 of Lecture Notes in Computer Science, pages 219-230, 2013.
[pdf]
B. de Keijzer, E. Markakis, G. Schäfer, and O. Telelis.
Inefficiency of standard multi-unit auctions.
In Proceedings of the 20th European Symposium on Algorithms (ESA), volume 8125 of Lecture Notes in Computer Science, pages 385-396, 2013.
[pdf]
K. R. Apt and G. Schäfer.
Selfishness level of strategic games.
In Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT), volume 7615 of Lecture Notes in Computer Science, pages 13-24, 2012.
[pdf]
B. de Keijzer and G. Schäfer.
Finding social optima in congestion games with positive externalities.
In Proceedings of the 20th European Symposium on Algorithms (ESA), volume 7501 of Lecture Notes in Computer Science, pages 395-406, 2012.
[pdf]
P.-A. Chen, B. de Keijzer, D. Kempe, and G. Schäfer.
The robust price of anarchy of altruistic games.
In Proceedings of the 7th International Workshop On Internet and Network Economics (WINE), volume 7090 of Lecture Notes in Computer Science, pages 383-390, 2011.
[pdf]
V. Bonifaci, M. Salek, and G. Schäfer.
Efficiency of restricted tolls in non-atomic network routing games.
In Proceedings of the 4th International Symposium on Algorithmic Game Theory (SAGT), volume 6982 of Lecture Notes in Computer Science, pages 302-313, 2011.
[pdf]
L. Buriol, M. Ritt, F. Rodrigues, and G. Schäfer.
On the smoothed price of anarchy of the traffic assignment problem.
In Proceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS), OpenAccess Series in Informatics (OASIcs), 2011, to appear.
[pdf]
B. de Keijzer, G. Schäfer, and O. Telelis.
On the inefficiency of equilibria in linear bottleneck congestion games.
In Proceedings of the 3rd International Symposium on Algorithmic Game Theory (SAGT), volume 6386 of Lecture Notes in Computer Science, pages 335-346, 2010.
[pdf]
J. Brenner and G. Schäfer.
Online cooperative cost sharing.
In Proceedings of the 7th International Conference on Algorithms and Complexity (CIAC), volume 6078 of Lecture Notes in Computer Science, pages 252-263, 2010.
[pdf]
V. Bonifaci, T. Harks, and G. Schäfer.
Stackelberg routing in arbitrary networks.
In Proceedings of the 4th International Workshop On Internet and Network Economics (WINE), volume 5385 of Lecture Notes in Computer Science, pages 239-250, 2008.
[pdf]
A. Berger, V. Bonifaci, F. Grandoni, and G. Schäfer.
Budgeted matching and budgeted matroid intersection via the gasoline puzzle.
In Proceedings of the 13th Conference on Integer Programming and Combinatorial Optimization (IPCO), volume 5035 of Lecture Notes in Computer Science, pages 273-287, 2008.
[pdf]
J. Brenner and G. Schäfer.
Singleton acyclic mechanisms and their applications to scheduling problems.
In Proceedings of the 1st International Symposium on Algorithmic Game Theory (SAGT), volume 4997 of Lecture Notes in Computer Science, pages 315-326, 2008.
[pdf]
F. Eisenbrand, F. Grandoni, T. Rothvoss, and G. Schäfer.
Approximating connected facility location problems via random facility sampling and core detouring.
In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1174-1183, 2008.
[pdf]
F.G. König, M.E. Lübbecke, R.H. Möhring, G. Schäfer, and I. Spenke.
Solutions to real-world instances of PSPACE-complete stacking.
In Proceedings of the 15th Annual European Symposium on Algorithms (ESA), volume 4698 of Lecture Notes in Computer Science, pages 729-740, 2007.
[pdf]
J. Brenner and G. Schäfer.
Cost sharing methods for makespan and completion time scheduling.
In Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, volume 4393 of Lecture Notes in Computer Science, pages 670-681, 2007.
[pdf]
A. Gupta, J. Könemann, S. Leonardi, R. Ravi, and G. Schäfer.
An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem.
In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1153-1162, 2007.
[pdf]
L. Fleischer, J. Könemann, S. Leonardi, and G. Schäfer.
Simple cost sharing schemes for multi-commodity rent-or-buy and stochastic Steiner tree.
In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pages 663-670, 2006.
[pdf]
J. Könemann, S. Leonardi, G. Schäfer, and S. van Zwam.
From primal-dual to cost shares and back: A stronger LP relaxation for the Steiner forest problem.
In Proceedings of the 32nd International Colloquium on Automata, Languages and a Programming (ICALP), volume 3580 of Lecture Notes in Computer Science, pages 930-942, 2005.
[pdf]
J. Könemann, S. Leonardi, and G. Schäfer.
A group-strategyproof mechanism for Steiner forests.
In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithm (SODA), pages 612-619, 2005.
[pdf]
S. Leonardi and G. Schäfer.
Cross-monotonic cost sharing methods for connected facility location games.
In Proceedings of the 5th ACM Conference on Electronic Commerce (EC), pages 242-243, 2004.
[pdf]
H. Bast, K. Mehlhorn, G. Schäfer, and H. Tamaki.
Matching algorithms are fast in sparse random graphs.
In Proceedings of the 21st Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 2996 of Lecture Notes in Computer Science, pages 81-92, 2004.
[pdf]
G. Schäfer and N. Sivadasan.
Topology matters: Smoothed competitiveness of metrical task systems.
In Proceedings of the 21st Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 2996 of Lecture Notes in Computer Science, pages 489-500, 2004.
[pdf]
L. Becchetti, S. Leonardi, A. Marchetti-Spaccamela, G. Schäfer, and T. Vredeveld.
Average case and smoothed competitive analysis of the multi-level feedback algorithm.
In Proceedings of the Forty-Fourth Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 462-471, 2003.
[ps]
L. Becchetti, S. Leonardi, A. Marchetti-Spaccamela, and G. Schäfer.
Scheduling to minimize flow time metrics.
In 3rd Workshop on Wireless, Mobile and Ad Hoc Networks (WMAN), satellite workshop of 17th IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2003.
K. Mehlhorn and G. Schäfer.
A heuristic for Dijkstra's algorithm with many targets and its use in weighted matching algorithms.
In Proceedings of the 9th Annual European Symposium on Algorithms (ESA), volume 2161 of Lecture Notes in Computer Science, pages 242-253, 2001.
[ps]
K. Mehlhorn and G. Schäfer.
Implementation of O(nm log n) weighted matchings in general graphs: The power of data structures.
In 4th International Workshop on Algorithm Engineering (WAE), volume 1982 of Lecture Notes in Computer Science, pages 23-38, 2000.
[ps]
D. Frigioni, T. Miller, U. Nanni, G. Pasqualone, G. Schäfer, and C. Zaroliagis.
An experimental study of dynamic algorithms for directed graphs.
In Proceedings of the 6th Annual European Symposium on Algorithms (ESA), volume 1461 of Lecture Notes in Computer Science, pages 368-380, 1998.

Theses

G. Schäfer.
Approximation and cost sharing algorithms for network design problems.
Habilitation, Institut für Mathematik, Technische Universität Berlin, Germany, 2009.
G. Schäfer.
Worst case instances are fragile: Average case and smoothed competitive analysis of algorithms.
PhD thesis, Universität des Saarlandes, Saarbrücken, Germany, 2004.
[pdf]
G. Schäfer.
Weighted matchings in general graphs.
Master's thesis, Fachbereich Informatik, Universität des Saarlandes, Saarbrücken, Germany, 2000.
[pdf]

Conference Proceedings

E. Markakis, G. Schäfer, editors
Proceedings of the 11th International Conference on Web and Internet Economics (WINE)
Lecture Notes in Computer Science 9470, Springer, 2015.

Contributions to Books

G. Schäfer.
Budgeted Matching via the Gasoline Puzzle.
In A. S. Schulz, M. Skutella, S. Stiller, D. Wagner, editors, Gems of Combinatorial Optimization and Graph Algorithms, Springer, 2015.
G. Schäfer.
Steiner forest.
In Ming Yang Kao, editor, Encyclopedia of Algorithms, Springer, 2008.

Manuscripts

J. Brenner and G. Schäfer.
Generalized incremental mechanisms for scheduling games.
Manuscript, 2010.
[pdf]
T. Harks, G. Schäfer, and M. Sieg.
The min-toll-booth problem: Complexity, algorithms and experimental findings.
In Proceedings of the 7th Triennial Symposium on Transportation Analysis, pages 343-346, 2010.
G. Schäfer.
A note on the smoothed complexity of the single-source shortest path problem.
Research Report MPI-I-2003-1-018, Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany, November 2003.
[ps]
S. Hert, T. Polzin, L. Kettner, and G. Schäfer.
ExpLab: A tool set for computational experiments.
Research Report MPI-I-2002-1-004, Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany, November 2002.

Copyright notice

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.