Dr. Alexander Lindermayr

 

Fakultät II - Mathematik und Naturwissenschaften
Institut für Mathematik, Sekr. MA 5-2
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin

Office: MA 678
Email: (lastname)@math.tu-berlin.de

See my personal website for more information on research, hobbies, and news.

Publications

2026

• The Power of Proportional Fairness for Nonclairvoyant Polytope Scheduling (Sven Jäger, Alexander Lindermayr, and Nicole Megow)
  SIAM J. Comput., 55(2):247–279, 2026.
  Extended abstract appeared in Proc. of SODA 2025
  doi Bibtex
  @article{JaegerLM26,
  author = {J{\"{a}}ger, Sven and Lindermayr, Alexander and Megow, Nicole},
  title = {The Power of Proportional Fairness for Nonclairvoyant Polytope Scheduling},
  journal = {SIAM J. Comput.},
  volume = {55},
  number = {2},
  pages = {247--279},
  year = {2026},
  doi = {10.1137/25m1763974},
  }
  
• A Better-Than-5/4-Approximation for Two-Edge Connectivity (Felix Hommelsheim, Alexander Lindermayr, and Zhenwei Liu)
  SODA 2026 – Proc. 37th ACM-SIAM Symposium on Discrete Algorithms, pp. 1468–1520.
  doi Bibtex
  @inproceedings{HommelsheimLL26,
  author = {Hommelsheim, Felix and Lindermayr, Alexander and Liu, Zhenwei},
  title = {A Better-Than-5/4-Approximation for Two-Edge Connectivity},
  booktitle = {SODA 2026 – Proc. 37th ACM-SIAM Symposium on Discrete Algorithms},
  pages = {1468--1520},
  year = {2026},
  doi = {10.1137/1.9781611978971.54},
  }
  

2025

• Boosting Double Coverage for k-Server via Imperfect Predictions (Alexander Lindermayr, Nicole Megow, and Bertrand Simon)
  Algorithmica, 87(11):1477–1517, 2025.
  Extended abstract appeared in Proc. of ITCS 2022
  doi Bibtex
  @article{LindermayrMS25,
  author = {Lindermayr, Alexander and Megow, Nicole and Simon, Bertrand},
  title = {Boosting Double Coverage for k-Server via Imperfect Predictions},
  journal = {Algorithmica},
  volume = {87},
  number = {11},
  pages = {1477--1517},
  year = {2025},
  doi = {10.1007/s00453-025-01333-9},
  }
  
• Permutation Predictions for Non-Clairvoyant Scheduling (Alexander Lindermayr and Nicole Megow)
  ACM Trans. Parallel Comput., 12(2):4:1–4:26, 2025.
  Extended abstract appeared in Proc. of SPAA 2022
  doi Bibtex
  @article{LindermayrM25,
  author = {Lindermayr, Alexander and Megow, Nicole},
  title = {Permutation Predictions for Non-Clairvoyant Scheduling},
  journal = {ACM Trans. Parallel Comput.},
  volume = {12},
  number = {2},
  pages = {4:1--4:26},
  year = {2025},
  doi = {10.1145/3711872},
  }
  
• A Little Clairvoyance Is All You Need (Anupam Gupta, Haim Kaplan, Alexander Lindermayr, Jens Schlöter, and Sorrachai Yingchareonthawornchai)
  FOCS 2025 – Proc. 66th Symposium on Foundations of Computer Science, pp. 86–118.
  doi Bibtex
  @inproceedings{GuptaKLSY25,
  author = {Gupta, Anupam and Kaplan, Haim and Lindermayr, Alexander and Schl{\"{o}}ter, Jens and Yingchareonthawornchai, Sorrachai},
  title = {A Little Clairvoyance Is All You Need},
  booktitle = {FOCS 2025 – Proc. 66th Symposium on Foundations of Computer Science},
  pages = {86--118},
  year = {2025},
  doi = {10.1109/FOCS63196.2025.00010},
  }
  
• A 5/4-Approximation for Two-Edge Connectivity (Miguel Bosch-Calvo, Mohit Garg, Fabrizio Grandoni, Felix Hommelsheim, Afrouz Jabal Ameli, and Alexander Lindermayr)
  STOC 2025 – Proc. 57th Symposium on Theory of Computing, pp. 653–664.
  doi Bibtex
  @inproceedings{BoschCalvoGGHAL25,
  author = {Bosch-Calvo, Miguel and Garg, Mohit and Grandoni, Fabrizio and Hommelsheim, Felix and Jabal Ameli, Afrouz and Lindermayr, Alexander},
  title = {A 5/4-Approximation for Two-Edge Connectivity},
  booktitle = {STOC 2025 – Proc. 57th Symposium on Theory of Computing},
  pages = {653--664},
  year = {2025},
  doi = {10.1145/3717823.3718275},
  }
  
• The Power of Proportional Fairness for Non-Clairvoyant Scheduling under Polyhedral Constraints (Sven Jäger, Alexander Lindermayr, and Nicole Megow)
  SODA 2025 – Proc. 36th ACM-SIAM Symposium on Discrete Algorithms, pp. 3901–3930.
  doi Bibtex
  @inproceedings{JaegerLM25,
  author = {J{\"{a}}ger, Sven and Lindermayr, Alexander and Megow, Nicole},
  title = {The Power of Proportional Fairness for Non-Clairvoyant Scheduling under Polyhedral Constraints},
  booktitle = {SODA 2025 – Proc. 36th ACM-SIAM Symposium on Discrete Algorithms},
  pages = {3901--3930},
  year = {2025},
  doi = {10.1137/1.9781611978322.132},
  }
  

2024

• Elimination Distance to Bounded Degree on Planar Graphs (Alexander Lindermayr, Sebastian Siebertz, and Alexandre Vigny)
  Fundam. Informaticae, 191(2):129–140, 2024.
  Extended abstract appeared in Proc. of MFCS 2020
  doi Bibtex
  @article{LindermayrSV24,
  author = {Lindermayr, Alexander and Siebertz, Sebastian and Vigny, Alexandre},
  title = {Elimination Distance to Bounded Degree on Planar Graphs},
  journal = {Fundam. Informaticae},
  volume = {191},
  number = {2},
  pages = {129--140},
  year = {2024},
  doi = {10.3233/FI-242175},
  }
  
• Accelerating Matroid Optimization through Fast Imprecise Oracles (Franziska Eberle, Felix Hommelsheim, Alexander Lindermayr, Zhenwei Liu, and Nicole Megow)
  NeurIPS 2024 – Proc. 38th Conference on Neural Information Processing Systems.
  html Bibtex
  @inproceedings{EberleHLLMS24,
  author = {Eberle, Franziska and Hommelsheim, Felix and Lindermayr, Alexander and Liu, Zhenwei and Megow, Nicole and Schl{\"{o}}ter, Jens},
  title = {Accelerating Matroid Optimization through Fast Imprecise Oracles},
  booktitle = {NeurIPS 2024 – Proc. 38th Conference on Neural Information Processing Systems},
  year = {2024},
  url = {http://papers.nips.cc/paper_files/paper/2024/hash/aa76039e10ccb71d2922e87a87240f72-Abstract-Conference.html},
  }
  
• Santa Claus meets Makespan and Matroids: Algorithms and Reductions (Étienne Bamas, Alexander Lindermayr, Nicole Megow, and Lars Rohwedder)
  SODA 2024 – Proc. 35th ACM-SIAM Symposium on Discrete Algorithms, pp. 2829–2860.
  doi Bibtex
  @inproceedings{BamasLMRS24,
  author = {Bamas, {\'{E}}tienne and Lindermayr, Alexander and Megow, Nicole and Rohwedder, Lars and Schl{\"{o}}ter, Jens},
  title = {Santa Claus meets Makespan and Matroids: Algorithms and Reductions},
  booktitle = {SODA 2024 – Proc. 35th ACM-SIAM Symposium on Discrete Algorithms},
  pages = {2829--2860},
  year = {2024},
  doi = {10.1137/1.9781611977912.100},
  }
  
• The Safe and Effective Use of Optimistic Period Predictions (Sanjoy K. Baruah, Pontus Ekberg, Alexander Lindermayr, Alberto Marchetti-Spaccamela, Nicole Megow, and Leen Stougie)
  RTNS 2024 – Proc. 32nd International Conference on Real-Time Networks and Systems, pp. 197–206.
  doi Bibtex
  @inproceedings{BaruahELMMS24,
  author = {Baruah, Sanjoy K. and Ekberg, Pontus and Lindermayr, Alexander and Marchetti-Spaccamela, Alberto and Megow, Nicole and Stougie, Leen},
  title = {The Safe and Effective Use of Optimistic Period Predictions},
  booktitle = {RTNS 2024 – Proc. 32nd International Conference on Real-Time Networks and Systems},
  pages = {197--206},
  year = {2024},
  doi = {10.1145/3696355.3696356},
  }
  

2023

• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints (Alexandra Anna Lassota, Alexander Lindermayr, and Nicole Megow)
  ICML 2023 – Proc. 40th International Conference on Machine Learning, pp. 18563–18583.
  html Bibtex
  @inproceedings{LassotaLMS23,
  author = {Lassota, Alexandra Anna and Lindermayr, Alexander and Megow, Nicole and Schl{\"{o}}ter, Jens},
  title = {Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints},
  booktitle = {ICML 2023 – Proc. 40th International Conference on Machine Learning},
  pages = {18563--18583},
  year = {2023},
  url = {https://proceedings.mlr.press/v202/lassota23a.html},
  }
  
• Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary (Alexander Lindermayr, Nicole Megow, and Martin Rapp)
  ICML 2023 – Proc. 40th International Conference on Machine Learning, pp. 21312–21334.
  html Bibtex
  @inproceedings{LindermayrMR23,
  author = {Lindermayr, Alexander and Megow, Nicole and Rapp, Martin},
  title = {Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary},
  booktitle = {ICML 2023 – Proc. 40th International Conference on Machine Learning},
  pages = {21312--21334},
  year = {2023},
  url = {https://proceedings.mlr.press/v202/lindermayr23a.html},
  }
  

2022

• A Universal Error Measure for Input Predictions Applied to Online Graph Problems (Giulia Bernardini, Alexander Lindermayr, Alberto Marchetti-Spaccamela, Nicole Megow, Leen Stougie, and Michelle Sweering)
  NeurIPS 2022 – Proc. 36th Conference on Neural Information Processing Systems.
  html Bibtex
  @inproceedings{BernardiniLMMSS22,
  author = {Bernardini, Giulia and Lindermayr, Alexander and Marchetti-Spaccamela, Alberto and Megow, Nicole and Stougie, Leen and Sweering, Michelle},
  title = {A Universal Error Measure for Input Predictions Applied to Online Graph Problems},
  booktitle = {NeurIPS 2022 – Proc. 36th Conference on Neural Information Processing Systems},
  year = {2022},
  url = {http://papers.nips.cc/paper_files/paper/2022/hash/15212bd2265c4a3ab0dbc1b1982c1b69-Abstract-Conference.html},
  }
  
• Robustification of Online Graph Exploration Methods (Franziska Eberle, Alexander Lindermayr, Nicole Megow, and Lukas Nölke)
  AAAI 2022 – Proc. 36th AAAI Conference on Artificial Intelligence, pp. 9732–9740.
  doi Bibtex
  @inproceedings{EberleLMNS22,
  author = {Eberle, Franziska and Lindermayr, Alexander and Megow, Nicole and N{\"{o}}lke, Lukas and Schl{\"{o}}ter, Jens},
  title = {Robustification of Online Graph Exploration Methods},
  booktitle = {AAAI 2022 – Proc. 36th AAAI Conference on Artificial Intelligence},
  pages = {9732--9740},
  year = {2022},
  doi = {10.1609/aaai.v36i9.21208},
  }
  
• Double Coverage with Machine-Learned Advice (Alexander Lindermayr, Nicole Megow, and Bertrand Simon)
  ITCS 2022 – Proc. 13th Innovations in Computer Science Conference, pp. 99:1–99:18.
  Full paper appeared in Algorithmica 2025
  doi Bibtex
  @inproceedings{LindermayrMS22,
  author = {Lindermayr, Alexander and Megow, Nicole and Simon, Bertrand},
  title = {Double Coverage with Machine-Learned Advice},
  booktitle = {ITCS 2022 – Proc. 13th Innovations in Computer Science Conference},
  pages = {99:1--99:18},
  year = {2022},
  doi = {10.4230/LIPIcs.ITCS.2022.99},
  }
  
• Permutation Predictions for Non-Clairvoyant Scheduling (Alexander Lindermayr and Nicole Megow)
  SPAA 2022 – Proc. 34th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 357–368.
  Full paper appeared in ACM Trans. Parallel Comput. 2025
  doi Bibtex
  @inproceedings{LindermayrM22,
  author = {Lindermayr, Alexander and Megow, Nicole},
  title = {Permutation Predictions for Non-Clairvoyant Scheduling},
  booktitle = {SPAA 2022 – Proc. 34th ACM Symposium on Parallelism in Algorithms and Architectures},
  pages = {357--368},
  year = {2022},
  doi = {10.1145/3490148.3538579},
  }
  

2020

• Elimination Distance to Bounded Degree on Planar Graphs (Alexander Lindermayr, Sebastian Siebertz, and Alexandre Vigny)
  MFCS 2020 – Proc. 45th International Symposium on Mathematical Foundations of Computer Science, pp. 65:1–65:12.
  Full paper appeared in Fundam. Informaticae 2024
  doi Bibtex
  @inproceedings{LindermayrSV20,
  author = {Lindermayr, Alexander and Siebertz, Sebastian and Vigny, Alexandre},
  title = {Elimination Distance to Bounded Degree on Planar Graphs},
  booktitle = {MFCS 2020 – Proc. 45th International Symposium on Mathematical Foundations of Computer Science},
  pages = {65:1--65:12},
  year = {2020},
  doi = {10.4230/LIPIcs.MFCS.2020.65},
  }