Guido Schäfer: Publications
[Journals] [Conferences] [Theses] [Others]
(see also dblp for an uptodate list of publications)

P. Kleer and G. Schäfer.
Tight inefficiency bounds for perceptionparameterized affine congestion games.
Theoretical Computer Science, 754:65–87, 2019.

P. Kleer and G. Schäfer.
The impact of worstcase deviations in nonatomic network routing games.
Theory of Computing Systems, 63(1):5489, 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):851877, 2017.
[pdf]

A. Gupta, J. Könemann, S. Leonardi, R. Ravi, and G. Schäfer.
Efficient costsharing mechanisms for prizecollecting 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 207240, 2014.

A. Berger, V. Bonifaci, F. Grandoni, and G. Schäfer.
Budgeted matching and budgeted matroid intersection via the gasoline puzzle.
Mathematical Programming, 128(12), pages 355372, 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 36163632, 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 709726, 2010.
[pdf]

V. Bonifaci, T. Harks, and G. Schäfer.
Stackelberg routing in arbitrary networks.
Mathematics of Operations Research, volume 35(2), pages 330346, 2010.
[pdf]

J. Brenner and G. Schäfer.
Groupstrategyproof cost sharing mechanisms for makespan and other scheduling problems.
Theoretical Computer Science, volume 401(13), pages 96106, 2008.
[pdf]

J. Könemann, S. Leonardi, G. Schäfer, and S. van Zwam.
A groupstrategyproof cost sharing mechanism for the Steiner forest game.
SIAM Journal on Computing, volume 37(5), pages 13191341, 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 314, 2006.
[pdf]

G. Schäfer and N. Sivadasan.
Topology matters: Smoothed competitiveness of metrical task systems.
Theoretical Computer Science, volume 341(13), pages 216246, 2005.
[pdf]

L. Becchetti, S. Leonardi, A. MarchettiSpaccamela, G. Schäfer, and T. Vredeveld.
Average case and smoothed competitive analysis of the multilevel feedback algorithm.
Mathematics of Operations Research, volume 31(1), pages 85108, 2006.
[pdf]

S. Leonardi and G. Schäfer.
Crossmonotonic cost sharing methods for connected facility location games.
Theoretical Computer Science, volume 326(13), pages 431442, 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 7588, 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.
Allpairs shortestpaths computation in the presence of negative cycles.
Information Processing Letters, 81(6):341343, 2002.
[ps]

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: Complementfree cost functions and beyond
In Proceedings of the 27th Annual European Symposium on Algorithms (ESA), 2019.

G. Amanatidis, P. Kleer, G. Schäfer
Budgetfeasible 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 PerceptionParameterized 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 GroundSetCost 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 WorstCase Deviations in NonAtomic 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 391404, 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 219230, 2013.
[pdf]

B. de Keijzer, E. Markakis, G. Schäfer, and O. Telelis.
Inefficiency of standard multiunit auctions.
In Proceedings of the 20th European Symposium on Algorithms (ESA),
volume 8125 of Lecture Notes in Computer Science, pages 385396, 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 1324, 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 395406, 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 383390, 2011.
[pdf]

V. Bonifaci, M. Salek, and G. Schäfer.
Efficiency of restricted tolls in nonatomic network routing games.
In Proceedings of the 4th International Symposium on Algorithmic Game Theory (SAGT), volume 6982 of Lecture Notes in Computer Science, pages 302313, 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 335346, 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 252263, 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 239250, 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 273287, 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 315326, 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 ACMSIAM Symposium on Discrete Algorithms (SODA), pages 11741183, 2008.
[pdf]

F.G. König, M.E. Lübbecke, R.H. Möhring, G. Schäfer, and I. Spenke.
Solutions to realworld instances of PSPACEcomplete stacking.
In Proceedings of the 15th Annual European Symposium on Algorithms (ESA), volume 4698 of Lecture Notes in Computer Science, pages 729740, 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 670681, 2007.
[pdf]

A. Gupta, J. Könemann, S. Leonardi, R. Ravi, and G. Schäfer.
An efficient costsharing mechanism for the prizecollecting Steiner forest problem.
In Proceedings of the ACMSIAM Symposium on Discrete Algorithms (SODA), pages 11531162, 2007.
[pdf]

L. Fleischer, J. Könemann, S. Leonardi, and G. Schäfer.
Simple cost sharing schemes for multicommodity rentorbuy and stochastic Steiner tree.
In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pages 663670, 2006.
[pdf]

J. Könemann, S. Leonardi, G. Schäfer, and S. van Zwam.
From primaldual 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 930942, 2005.
[pdf]

J. Könemann, S. Leonardi, and G. Schäfer.
A groupstrategyproof mechanism for Steiner forests.
In Proceedings of the Sixteenth Annual ACMSIAM Symposium on Discrete Algorithm (SODA), pages 612619, 2005.
[pdf]

S. Leonardi and G. Schäfer.
Crossmonotonic cost sharing methods for connected facility location games.
In Proceedings of the 5th ACM Conference on Electronic Commerce (EC), pages 242243, 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 8192, 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 489500, 2004.
[pdf]

L. Becchetti, S. Leonardi, A. MarchettiSpaccamela, G. Schäfer, and T. Vredeveld.
Average case and smoothed competitive analysis of the multilevel feedback algorithm.
In Proceedings of the FortyFourth Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 462471, 2003.
[ps]

L. Becchetti, S. Leonardi, A. MarchettiSpaccamela, 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 242253, 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 2338, 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 368380, 1998.

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]

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.

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 mintollbooth problem: Complexity, algorithms and experimental findings.
In Proceedings of the 7th Triennial Symposium on Transportation Analysis, pages 343346, 2010.

G. Schäfer.
A note on the smoothed complexity of the singlesource shortest path problem.
Research Report MPII20031018, MaxPlanckInstitut 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 MPII20021004, MaxPlanckInstitut 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.