Publications

Selected publications

Exact Price of Anarchy for Polynomial Congestion Games (Journal article - 2011)
Quasirandom Load Balancing (Journal article - 2010)
The Price of Stability of Weighted Congestion Games (Conference Paper - 2018)
Price of Stability in Polynomial Congestion Games (Journal article - 2016)
Complexity and Approximation of the Continuous Network Design Problem (Journal article - 2017)

Filter publications

What type of publication do you want to show?

All

Journals

Conference papers

Chapters

Books

Other

2024

In Congestion Games, Taxes Achieve Optimal Approximation

Gairing, M., & Paccagnan, D. (n.d.). In Congestion Games, Taxes Achieve Optimal Approximation. Operations Research. doi:10.1287/opre.2021.0526

DOI: 10.1287/opre.2021.0526
: Journal article

2023

Fair Interventions in Weighted Congestion Games

: Preprint

Existence and Complexity of Approximate Equilibria in Weighted Congestion Games

Christodoulou, G., Gairing, M., Giannakopoulos, Y., Pocas, D., & Waldmann, C. (2022). Existence and Complexity of Approximate Equilibria in Weighted Congestion Games. In MATHEMATICS OF OPERATIONS RESEARCH. doi:10.1287/moor.2022.1272

DOI: 10.1287/moor.2022.1272
: Conference Paper

Fair Interventions in Weighted Congestion Games.

: Preprint

2022

Dynamic Traffic Models in Transportation Science (Dagstuhl Seminar 22192).

Gairing, M., Osorio, C., Peis, B., Watling, D. P., & Eickhoff, K. (2022). Dynamic Traffic Models in Transportation Science (Dagstuhl Seminar 22192). (5).

: Report

2021

In Congestion Games, Taxes Achieve Optimal Approximation

DOI: 10.48550/arxiv.2105.07480
: Preprint

REACHABILITY SWITCHING GAMES

Fearnley, J., Gairing, M., Mnich, M., & Savani, R. (2021). REACHABILITY SWITCHING GAMES. In LOGICAL METHODS IN COMPUTER SCIENCE Vol. 17. doi:10.23638/LMCS-17(2:10)2021

DOI: 10.23638/LMCS-17(2:10)2021
: Conference Paper

Reachability switching games

Fearnley, J., Gairing, M., Mnich, M., & Savani, A. R. (2021). Reachability switching games. Logical Methods in Computer Science, 17(2), 10:1-10:29. doi:10.23638/LMCS-17(2:10)2021

DOI: 10.23638/LMCS-17(2:10)2021
: Journal article

2020

Existence and Efficiency of Equilibria for Cost-Sharing in Generalized Weighted Congestion Games

Gairing, M., Kollias, K., & Kotsialou, G. (2020). Existence and Efficiency of Equilibria for Cost-Sharing in Generalized Weighted Congestion Games. ACM Transactions on Economics and Computation, 8(2). doi:10.1145/3391434

DOI: 10.1145/3391434
: Journal article

Sensor Data for Human Activity Recognition: Feature Representation and Benchmarking

Alves, F., Gairing, M., Oliehoek, F. A., & Do, T. -T. (2020). Sensor Data for Human Activity Recognition: Feature Representation and Benchmarking. In 2020 INTERNATIONAL JOINT CONFERENCE ON NEURAL NETWORKS (IJCNN). doi:10.1109/ijcnn48605.2020.9207068

DOI: 10.1109/ijcnn48605.2020.9207068
: Conference Paper

Sensor Data for Human Activity Recognition: Feature Representation and Benchmarking

DOI: 10.48550/arxiv.2005.07308
: Preprint

Existence and Complexity of Approximate Equilibria in Weighted Congestion Games

Christodoulou, G., Gairing, M., Giannakopoulos, Y., Poças, D., & Waldmann, C. (2020). Existence and Complexity of Approximate Equilibria in Weighted Congestion Games. Retrieved from http://arxiv.org/abs/2002.07466v3

: Journal article

Existence and Complexity of Approximate Equilibria in Weighted Congestion Games

DOI: 10.48550/arxiv.2002.07466
: Preprint

Hiring Secretaries over Time: The Benefit of Concurrent Employment

Disser, Y., Fearnley, J., Gairing, M., Goebel, O., Klimm, M., Schmand, D., . . . Toennis, A. (2020). Hiring Secretaries over Time: The Benefit of Concurrent Employment. Mathematics of Operations Research, 45(1), 323-352. doi:10.1287/moor.2019.0993

DOI: 10.1287/moor.2019.0993
: Journal article

Sensor Data for Human Activity Recognition: Feature Representation and Benchmarking.

Alves, F., Gairing, M., Oliehoek, F. A., & Do, T. -T. (2020). Sensor Data for Human Activity Recognition: Feature Representation and Benchmarking.. In IJCNN (pp. 1-8). IEEE. Retrieved from https://ieeexplore.ieee.org/xpl/conhome/9200848/proceeding

: Conference Paper

2019

Greedy Metric Minimum Online Matchings with Random Arrivals

Gairing, M., & Klimm, M. (n.d.). Greedy Metric Minimum Online Matchings with Random Arrivals. Operations Research Letters.

: Journal article

Preface to the Special Issue on Algorithmic Game Theory

Gairing, M., & Savani, R. (2019). Preface to the Special Issue on Algorithmic Game Theory. THEORY OF COMPUTING SYSTEMS, 63(1), 2-3. doi:10.1007/s00224-018-9869-y

DOI: 10.1007/s00224-018-9869-y
: Journal article

Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games.

Gairing, M., & Savani, R. (2019). Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games.. Math. Oper. Res., 44, 1101-1121. doi:10.1287/moor.2018.0960

DOI: 10.1287/moor.2018.0960
: Journal article

Preface to the Special Issue on Algorithmic Game Theory.

Gairing, M., & Savani, R. (2019). Preface to the Special Issue on Algorithmic Game Theory.. Theory Comput. Syst., 63, 2-3. doi:10.1007/s00224-018-9869-y

DOI: 10.1007/s00224-018-9869-y
: Journal article

The Price of Stability of Weighted Congestion Games

Christodoulou, G., Gairing, M., Giannakopoulos, Y., & Spirakis, P. G. (2019). The Price of Stability of Weighted Congestion Games. SIAM Journal on Computing, 48(5), 1544-1582. doi:10.1137/18M1207880

DOI: 10.1137/18M1207880
: Journal article

2018

The Price of Stability of Weighted Congestion Games

Christodoulou, G., Gairing, M., Giannakopoulos, Y., & Spirakis, P. G. (2018). The Price of Stability of Weighted Congestion Games. In LIPIcs : Leibniz International Proceedings in Informatics Vol. 107 (pp. 150:1-150:16). Prague: Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik. doi:10.4230/LIPIcs.ICALP.2018.150

DOI: 10.4230/LIPIcs.ICALP.2018.150
: Conference Paper

The Price of Stability of Weighted Congestion Games

DOI: 10.48550/arxiv.1802.09952
: Preprint

The Price of Stability of Weighted Congestion Games.

Christodoulou, G., Gairing, M., Giannakopoulos, Y., & Spirakis, P. G. (2018). The Price of Stability of Weighted Congestion Games.. In I. Chatzigiannakis, C. Kaklamanis, D. Marx, & D. Sannella (Eds.), ICALP Vol. 107 (pp. 150:1). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.

: Conference Paper

2017

Computing Approximate Pure Nash Equilibria in Shapley Value Weighted Congestion Games

Feldotto, M., Gairing, M., Kotsialou, G., & Skopalik, A. (2017). Computing Approximate Pure Nash Equilibria in Shapley Value Weighted Congestion Games. In Conference on Web and Internet Economics. Bangalore, India.

: Conference Paper

Computing Approximate Pure Nash Equilibria in Shapley Value Weighted Congestion Games

DOI: 10.48550/arxiv.1710.01634
: Preprint

Reachability Switching Games

DOI: 10.48550/arxiv.1709.08991
: Preprint

Reachability Switching Games

Fearnley, J., Gairing, M., Mnich, M., & Savani, R. (2017). Reachability Switching Games. In April (Vol. 22, pp. 2021). Retrieved from http://dx.doi.org/10.23638/LMCS-17(2:10)2021

: Other

A 3-player protocol preventing persistence in strategic contention with limited feedback

Spirakis, P. G., Christodoulou, G., Gairing, M., Nikoletseas, S., & Raptopoulos, C. (2017). A 3-player protocol preventing persistence in strategic contention with limited feedback. In LNCS ARCoSS. L'Acquilla Iatly.

: Conference Paper

Complexity and Approximation of the Continuous Network Design Problem

Gairing, M., Harks, T., & Klimm, M. (2017). Complexity and Approximation of the Continuous Network Design Problem. SIAM Journal on Optimization, 27(03), 1554-1582. doi:10.1137/15M1016461

DOI: 10.1137/15M1016461
: Journal article

A 3-player protocol preventing persistence in strategic contention with limited feedback

DOI: 10.48550/arxiv.1707.01439
: Preprint

Cost-sharing in generalised selfish routing

Gairing, M., Kollias, K., & Kotsialou, G. (2017). Cost-sharing in generalised selfish routing. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 10236 LNCS (pp. 272-284). doi:10.1007/978-3-319-57586-5_23

DOI: 10.1007/978-3-319-57586-5_23
: Conference Paper

A 3-Player Protocol Preventing Persistence in Strategic Contention with Limited Feedback.

Christodoulou, G., Gairing, M., Nikoletseas, S. E., Raptopoulos, C. L., & Spirakis, P. G. (2017). A 3-Player Protocol Preventing Persistence in Strategic Contention with Limited Feedback.. In V. Bilò, & M. Flammini (Eds.), SAGT Vol. 10504 (pp. 240-251). Springer. Retrieved from https://doi.org/10.1007/978-3-319-66700-3

: Conference Paper

Computing Approximate Pure Nash Equilibria in Shapley Value Weighted Congestion Games.

Feldotto, M., Gairing, M., Kotsialou, G., & Skopalik, A. (2017). Computing Approximate Pure Nash Equilibria in Shapley Value Weighted Congestion Games.. CoRR, abs/1710.01634.

: Journal article

2016

Strategic Contention Resolution with Limited Feedback

Christodoulou, G., Gairing, M., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. G. (2016). Strategic Contention Resolution with Limited Feedback. In Leibniz International Proceedings in Informatics (LIPIcs) Vol. 57 (pp. 30:1-30:16). Aarhus , Denmark. doi:10.4230/LIPIcs.ESA.2016.30

DOI: 10.4230/LIPIcs.ESA.2016.30
: Conference Paper

Strategic Contention Resolution with Limited Feedback

DOI: 10.48550/arxiv.1606.06580
: Preprint

Hiring Secretaries over Time: The Benefit of Concurrent Employment

Disser, Y., Fearnley, J., Gairing, M., Goebel, O., Klimm, M., Schmand, D., . . . Toennis, A. (2020). Hiring Secretaries over Time: The Benefit of Concurrent Employment. doi:10.1287/moor.2019.0993

DOI: 10.1287/moor.2019.0993
: Report

Hiring Secretaries over Time: The Benefit of Concurrent Employment

DOI: 10.48550/arxiv.1604.08125
: Preprint

Price of Stability in Polynomial Congestion Games

Christodoulou, G., & Gairing, M. (2016). Price of Stability in Polynomial Congestion Games. ACM Transactions on Economics and Computation, 4(2), 1-17. doi:10.1145/2841229

DOI: 10.1145/2841229
: Journal article

Preface

Gairing, M., & Savani, R. (2016). Preface (Vol. 9928 LNCS).

: Book

Strategic Contention Resolution with Limited Feedback.

Christodoulou, G., Gairing, M., Nikoletseas, S. E., Raptopoulos, C. L., & Spirakis, P. G. (2016). Strategic Contention Resolution with Limited Feedback.. In P. Sankowski, & C. D. Zaroliagis (Eds.), ESA Vol. 57 (pp. 30:1). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Retrieved from http://drops.dagstuhl.de/opus/portals/lipics/index.php?semnr=16013

: Conference Paper

2015

Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games

Gairing, M., & Savani, R. (2019). Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games. In MATHEMATICS OF OPERATIONS RESEARCH (Vol. 44, Iss. 3, pp. 1101-1121). doi:10.1287/moor.2018.0960

DOI: 10.1287/moor.2018.0960
: Other

Computing stable outcomes in symmetric additively-separable hedonic games

DOI: 10.48550/arxiv.1509.05322
: Preprint

Learning Equilibria of Games via Payoff Queries

Fearnley, J., Gairing, M., Goldberg, P. W., & Savani, R. (2015). Learning Equilibria of Games via Payoff Queries. JOURNAL OF MACHINE LEARNING RESEARCH, 16, 1305-1344. Retrieved from https://www.webofscience.com/

: Journal article

Tight Bounds for Cost-Sharing in Weighted Congestion Games

Gairing, M., Kollias, K., & Kotsialou, G. (2015). Tight Bounds for Cost-Sharing in Weighted Congestion Games. In Automata, Languages, and Programming. ICALP 2015. Proceedings, Part II. Lecture Notes in Computer Science, Vol. 9135 (pp. 626-637). Kyoto, Japan,: Springer. doi:10.1007/978-3-662-47666-6_50

DOI: 10.1007/978-3-662-47666-6_50
: Conference Paper

2014

Approximate Pure Nash Equilibria in Social Context Congestion Games

Feldotto, M., Gairing, M., & Skopalik, A. (2014). Approximate Pure Nash Equilibria in Social Context Congestion Games. In Web and Internet Economics - 10th International Conference, WINE 2014 (pp. 30-43). Springer. Retrieved from http://dx.doi.org/10.1007/978-3-319-13129-0_43

: Chapter

Weighted Congestion Games

Bhawalkar, K., Gairing, M., & Roughgarden, T. (2014). Weighted Congestion Games. ACM Transactions on Economics and Computation, 2(4), 1-23. doi:10.1145/2629666

DOI: 10.1145/2629666
: Journal article

Approximate Pure Nash Equilibria in Social Context Congestion Games

Gairing, M., Kotsialou, G., & Skopalik, A. (2014). Approximate Pure Nash Equilibria in Social Context Congestion Games. In Unknown Book (Vol. 8877, pp. 480-485). Retrieved from https://www.webofscience.com/

: Chapter

Bounding the Potential Function in Congestion Games and Approximate Pure Nash Equilibria

Feldotto, M., Gairing, M., & Skopalik, A. (2014). Bounding the Potential Function in Congestion Games and Approximate Pure Nash Equilibria. In WEB AND INTERNET ECONOMICS Vol. 8877 (pp. 30-43). Retrieved from https://www.webofscience.com/

: Conference Paper

2013

Congestion Games with Player-Specific Costs Revisited

Gairing, M., & Klimm, M. (2013). Congestion Games with Player-Specific Costs Revisited. In ALGORITHMIC GAME THEORY, SAGT 2013 Vol. 8146 (pp. 98-109). Retrieved from https://www.webofscience.com/

: Conference Paper

Price of Stability in Polynomial Congestion Games

Christodoulou, G., & Gairing, M. (2013). Price of Stability in Polynomial Congestion Games. In AUTOMATA, LANGUAGES, AND PROGRAMMING, PT II Vol. 7966 (pp. 496-507). Retrieved from https://www.webofscience.com/

: Conference Paper

Complexity and Approximation of the Continuous Network Design Problem

DOI: 10.48550/arxiv.1307.4258
: Preprint

Learning equilibria of games via payoff queries

Fearnley, J., Gairing, M., Goldberg, P., & Savani, R. (2013). Learning equilibria of games via payoff queries. In Proceedings of the fourteenth ACM conference on Electronic commerce (pp. 397-414). ACM. doi:10.1145/2482540.2482558

DOI: 10.1145/2482540.2482558
: Conference Paper

Learning Equilibria of Games via Payoff Queries

Fearnley, J., Gairing, M., Goldberg, P., & Savani, R. (2013). Learning Equilibria of Games via Payoff Queries. Retrieved from http://arxiv.org/abs/1302.3116v4

: Conference Paper

Learning Equilibria of Games via Payoff Queries

DOI: 10.48550/arxiv.1302.3116
: Preprint

Congestion Games with Player-Specific Costs Revisited

Gairing, M., & Klimm, M. (2013). Congestion Games with Player-Specific Costs Revisited. In Symposium on Algorithmic Game Theory (pp. 12). Aachen: Springer.

: Conference Paper

2011

Exact Price of Anarchy for Polynomial Congestion Games

Aland, S., Dumrauf, D., Gairing, M., Monien, B., & Schoppmann, F. (2011). Exact Price of Anarchy for Polynomial Congestion Games. SIAM Journal on Computing, 40(5), 1211-1233. doi:10.1137/090748986

DOI: 10.1137/090748986
: Journal article

Routing (un-) splittable flow in games with player-specific affine latency functions

Gairing, M., Monien, B., & Tiemann, K. (2011). Routing (un-) splittable flow in games with player-specific affine latency functions. ACM Transactions on Algorithms, 7(3), 1-31. doi:10.1145/1978782.1978786

DOI: 10.1145/1978782.1978786
: Journal article

Computing Stable Outcomes in Hedonic Games with Voting-Based Deviations

Gairing, M., & Savani, R. (2011). Computing Stable Outcomes in Hedonic Games with Voting-Based Deviations. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011) (pp. 559-566). Taipei: -. Retrieved from http://portal.acm.org/

: Conference Paper

Computing stable outcomes in hedonic games with voting-based deviations

Gairing, M., & Savani, R. (2011). Computing stable outcomes in hedonic games with voting-based deviations. In 10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011 Vol. 1 (pp. 521-528).

: Conference Paper

2010

Computing Stable Outcomes in Hedonic Games

Gairing, M., & Savani, R. (2010). Computing Stable Outcomes in Hedonic Games. In ALGORITHMIC GAME THEORY Vol. 6386 (pp. 174-185). Retrieved from https://www.webofscience.com/

: Conference Paper

Weighted Congestion Games: Price of Anarchy, Universal Worst-Case Examples, and Tightness

Bhawalkar, K., Gairing, M., & Roughgarden, T. (2010). Weighted Congestion Games: Price of Anarchy, Universal Worst-Case Examples, and Tightness. In Unknown Conference (pp. 17-28). Springer Berlin Heidelberg. doi:10.1007/978-3-642-15781-3_2

DOI: 10.1007/978-3-642-15781-3_2
: Conference Paper

Computing Nash Equilibria for Scheduling on Restricted Parallel Links

Gairing, M., Lücking, T., Mavronicolas, M., & Monien, B. (2010). Computing Nash Equilibria for Scheduling on Restricted Parallel Links. Theory of Computing Systems, 47(2), 405-432. doi:10.1007/s00224-009-9191-9

DOI: 10.1007/s00224-009-9191-9
: Journal article

Quasirandom Load Balancing

Friedrich, T., Gairing, M., & Sauerwald, T. (2010). Quasirandom Load Balancing. SIAM Journal on Computing, 41, 4. Retrieved from http://dx.doi.org/10.1137/100799216

: Journal article

Quasirandom Load Balancing

Friedrich, T., Gairing, M., & Sauerwald, T. (2010). Quasirandom Load Balancing. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1620-1629). Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611973075.132

DOI: 10.1137/1.9781611973075.132
: Conference Paper

Quasirandom Load Balancing

Friedrich, T., Gairing, M., & Sauerwald, T. (2010). Quasirandom Load Balancing. In 1st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010) (pp. 10). Austin: ACM. Retrieved from http://www.siam.org/proceedings/soda/2010/SODA10_132_friedricht.pdf

: Conference Paper

2009

Covering Games: Approximation through Non-cooperation

Gairing, M. (2009). Covering Games: Approximation through Non-cooperation. In Unknown Conference (pp. 184-195). Springer Berlin Heidelberg. doi:10.1007/978-3-642-10841-9_18

DOI: 10.1007/978-3-642-10841-9_18
: Conference Paper

Malicious Bayesian Congestion Games

Gairing, M. (2009). Malicious Bayesian Congestion Games. In Lecture Notes in Computer Science (pp. 119-132). Springer Berlin Heidelberg. doi:10.1007/978-3-540-93980-1_10

DOI: 10.1007/978-3-540-93980-1_10
: Chapter

2008

Malicious Bayesian Congestion Games

Gairing, M. (2008). Malicious Bayesian Congestion Games. Retrieved from http://arxiv.org/abs/0805.2421v2

: Conference Paper

Nash equilibria in discrete routing games with convex latency functions

Gairing, M., Lücking, T., Mavronicolas, M., Monien, B., & Rode, M. (2008). Nash equilibria in discrete routing games with convex latency functions. Journal of Computer and System Sciences, 74(7), 1199-1225. doi:10.1016/j.jcss.2008.07.001

DOI: 10.1016/j.jcss.2008.07.001
: Journal article

Selfish Routing with Incomplete Information

Gairing, M., Monien, B., & Tiemann, K. (2008). Selfish Routing with Incomplete Information. Theory of Computing Systems, 42(1), 91-130. doi:10.1007/s00224-007-9015-8

DOI: 10.1007/s00224-007-9015-8
: Journal article

2007

A faster combinatorial approximation algorithm for scheduling unrelated parallel machines

Gairing, M., Monien, B., & Woclaw, A. (2007). A faster combinatorial approximation algorithm for scheduling unrelated parallel machines. Theoretical Computer Science, 380(1-2), 87-99. doi:10.1016/j.tcs.2007.02.056

DOI: 10.1016/j.tcs.2007.02.056
: Journal article

Total Latency in Singleton Congestion Games

Gairing, M., & Schoppmann, F. (n.d.). Total Latency in Singleton Congestion Games. In Unknown Conference (pp. 381-387). Springer Berlin Heidelberg. doi:10.1007/978-3-540-77105-0_42

DOI: 10.1007/978-3-540-77105-0_42
: Conference Paper

2006

The price of anarchy for polynomial social cost

Gairing, M., Lücking, T., Mavronicolas, M., & Monien, B. (2006). The price of anarchy for polynomial social cost. Theoretical Computer Science, 369(1-3), 116-135. doi:10.1016/j.tcs.2006.07.055

DOI: 10.1016/j.tcs.2006.07.055
: Journal article

Price of Anarchy for Polynomial Wardrop Games

Dumrauf, D., & Gairing, M. (2006). Price of Anarchy for Polynomial Wardrop Games. In Unknown Conference (pp. 319-330). Springer Berlin Heidelberg. doi:10.1007/11944874_29

DOI: 10.1007/11944874_29
: Conference Paper

Exact Price of Anarchy for Polynomial Congestion Games

Aland, S., Dumrauf, D., Gairing, M., Monien, B., & Schoppmann, F. (2006). Exact Price of Anarchy for Polynomial Congestion Games. In Unknown Conference (pp. 218-229). Springer Berlin Heidelberg. doi:10.1007/11672142_17

DOI: 10.1007/11672142_17
: Conference Paper

THE PRICE OF ANARCHY FOR RESTRICTED PARALLEL LINKS

GAIRING, M., LÜCKING, T., MAVRONICOLAS, M., & MONIEN, B. (2006). THE PRICE OF ANARCHY FOR RESTRICTED PARALLEL LINKS. Parallel Processing Letters, 16(01), 117-131. doi:10.1142/s0129626406002514

DOI: 10.1142/s0129626406002514
: Journal article

Routing (Un-) Splittable Flow in Games with Player-Specific Linear Latency Functions

Gairing, M., Monien, B., & Tiemann, K. (2006). Routing (Un-) Splittable Flow in Games with Player-Specific Linear Latency Functions. In Unknown Conference (pp. 501-512). Springer Berlin Heidelberg. doi:10.1007/11786986_44

DOI: 10.1007/11786986_44
: Conference Paper

2005

Structure and complexity of extreme Nash equilibria

Gairing, M., Lücking, T., Mavronicolas, M., Monien, B., & Spirakis, P. (2005). Structure and complexity of extreme Nash equilibria. Theoretical Computer Science, 343(1-2), 133-157. doi:10.1016/j.tcs.2005.05.011

DOI: 10.1016/j.tcs.2005.05.011
: Journal article

Selfish routing with incomplete information

Gairing, M., Monien, B., & Tiemann, K. (2005). Selfish routing with incomplete information. In Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures. ACM. doi:10.1145/1073970.1074000

DOI: 10.1145/1073970.1074000
: Conference Paper

A Faster Combinatorial Approximation Algorithm for Scheduling Unrelated Parallel Machines

Gairing, M., Monien, B., & Woclaw, A. (2005). A Faster Combinatorial Approximation Algorithm for Scheduling Unrelated Parallel Machines. In Unknown Conference (pp. 828-839). Springer Berlin Heidelberg. doi:10.1007/11523468_67

DOI: 10.1007/11523468_67
: Conference Paper

A Simple Graph-Theoretic Model for Selfish Restricted Scheduling

Elsässer, R., Gairing, M., Lücking, T., Mavronicolas, M., & Monien, B. (2005). A Simple Graph-Theoretic Model for Selfish Restricted Scheduling. In Unknown Conference (pp. 195-209). Springer Berlin Heidelberg. doi:10.1007/11600930_20

DOI: 10.1007/11600930_20
: Conference Paper

Nash Equilibria, the Price of Anarchy and the Fully Mixed Nash Equilibrium Conjecture

Gairing, M., Lücking, T., Monien, B., & Tiemann, K. (2005). Nash Equilibria, the Price of Anarchy and the Fully Mixed Nash Equilibrium Conjecture. In Unknown Conference (pp. 51-65). Springer Berlin Heidelberg. doi:10.1007/11523468_5

DOI: 10.1007/11523468_5
: Conference Paper

2004

DISTANCE-TWO INFORMATION IN SELF-STABILIZING ALGORITHMS

GAIRING, M., GODDARD, W., HEDETNIEMI, S. T., KRISTIANSEN, P., & McRAE, A. A. (2004). DISTANCE-TWO INFORMATION IN SELF-STABILIZING ALGORITHMS. Parallel Processing Letters, 14(03n04), 387-398. doi:10.1142/s0129626404001970

DOI: 10.1142/s0129626404001970
: Journal article

Computing Nash equilibria for scheduling on restricted parallel links

Gairing, M., Lücking, T., Mavronicolas, M., & Monien, B. (2004). Computing Nash equilibria for scheduling on restricted parallel links. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (pp. 613-622). ACM. doi:10.1145/1007352.1007446

DOI: 10.1145/1007352.1007446
: Conference Paper

SELFISH ROUTING IN NON-COOPERATIVE NETWORKS: A SURVEY

FELDMANN, R., GAIRING, M., LÜCKING, T., MONIEN, B., & RODE, M. (2004). SELFISH ROUTING IN NON-COOPERATIVE NETWORKS: A SURVEY. In Current Trends in Theoretical Computer Science (pp. 373-401). WORLD SCIENTIFIC. doi:10.1142/9789812562494_0020

DOI: 10.1142/9789812562494_0020
: Chapter

SELF-STABILIZING MAXIMAL k-DEPENDENT SETS IN LINEAR TIME

GAIRING, M., GODDARD, W., HEDETNIEMI, S. T., & JACOBS, D. P. (2004). SELF-STABILIZING MAXIMAL k-DEPENDENT SETS IN LINEAR TIME. Parallel Processing Letters, 14(01), 75-82. doi:10.1142/s0129626404001726

DOI: 10.1142/s0129626404001726
: Journal article

A Self-Stabilizing Algorithm for Maximal 2-Packing

Gairing, M., Geist, R. M., Hedetniemi, S. T., & Kristiansen, P. (2004). A Self-Stabilizing Algorithm for Maximal 2-Packing. Nordic Journal of Computing, 11(1), 1-11.

: Journal article

Nash Equilibria in Discrete Routing Games with Convex Latency Functions

Gairing, M., Lücking, T., Mavronicolas, M., Monien, B., & Rode, M. (2004). Nash Equilibria in Discrete Routing Games with Convex Latency Functions. In Unknown Conference (pp. 645-657). Springer Berlin Heidelberg. doi:10.1007/978-3-540-27836-8_55

DOI: 10.1007/978-3-540-27836-8_55
: Conference Paper

The Price of Anarchy for Polynomial Social Cost

Gairing, M., Lücking, T., Mavronicolas, M., & Monien, B. (2004). The Price of Anarchy for Polynomial Social Cost. In Unknown Conference (pp. 574-585). Springer Berlin Heidelberg. doi:10.1007/978-3-540-28629-5_44

DOI: 10.1007/978-3-540-28629-5_44
: Conference Paper

2003

Extreme Nash Equilibria

Gairing, M., Lücking, T., Mavronicolas, M., Monien, B., & Spirakis, P. (2003). Extreme Nash Equilibria. In Unknown Conference (pp. 1-20). Springer Berlin Heidelberg. doi:10.1007/978-3-540-45208-9_1

DOI: 10.1007/978-3-540-45208-9_1
: Conference Paper

Nashification and the Coordination Ratio for a Selfish Routing Game

Feldmann, R., Gairing, M., Lücking, T., Monien, B., & Rode, M. (2003). Nashification and the Coordination Ratio for a Selfish Routing Game. In Unknown Conference (pp. 514-526). Springer Berlin Heidelberg. doi:10.1007/3-540-45061-0_42

DOI: 10.1007/3-540-45061-0_42
: Conference Paper

Self-Stabilizing Algorithms for {k}-Domination

Gairing, M., Hedetniemi, S. T., Kristiansen, P., & McRae, A. A. (2003). Self-Stabilizing Algorithms for {k}-Domination. In Unknown Conference (pp. 49-60). Springer Berlin Heidelberg. doi:10.1007/3-540-45032-7_4

DOI: 10.1007/3-540-45032-7_4
: Conference Paper

Selfish Routing in Non-cooperative Networks: A Survey

Feldmann, R., Gairing, M., Lücking, T., Monien, B., & Rode, M. (2003). Selfish Routing in Non-cooperative Networks: A Survey. In Unknown Conference (pp. 21-45). Springer Berlin Heidelberg. doi:10.1007/978-3-540-45138-9_2

DOI: 10.1007/978-3-540-45138-9_2
: Conference Paper

2002

Gallei Theorems Involving Domination Parameters

Balasubramanian, S., Bernasconi, K., Farr, J., Gairing, M., Hedetniemi, S. T., Hutson, K., . . . Villalpando, J. (2002). Gallei Theorems Involving Domination Parameters. Congressus Numerantium, 157, 149-157.

: Journal article