Kevin Schewior

Search results

• 2022

  Completeness and diversity in depth-first proof-number search with applications to retrosynthesis

  Franz, C., Mogk, G., Mrziglod, T. & Schewior, K., 2022, Proceedings of the 31st International Joint Conference on Artificial Intelligence, IJCAI 2022. De Raedt, L. (ed.). International Joint Conferences on Artificial Intelligence, p. 4747-4753 (IJCAI International Joint Conference on Artificial Intelligence).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Trees (mathematics) 100%
  • Molecules 85%
  • Planning 55%

• Knapsack secretary through boosting

  Abels, A., Ladewig, L., Schewior, K. & Stinzendörfer, M., 2022, Approximation and Online Algorithms - 20th International Workshop, WAOA 2022, Proceedings. Chalermsook, P. & Laekhanukit, B. (eds.). Springer Science+Business Media, p. 61-81 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 13538 LNCS).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Secretary Problem 100%
  • Boosting 90%
  • Knapsack 82%
  • Competitive Ratio 47%
  • Knapsack Problem 33%
• 2021

  Speed-Robust Scheduling: Sand, Bricks, and Rocks

  Eberle, F., Hoeksma, R., Megow, N., Nölke, L., Schewior, K. & Simon, B., 21. May 2021, Conference on Integer Programming and Combinatorial Optimization (IPCO): 22nd International Conference, IPCO 2021, Proceedings. Singh, M. & Williamson, D. P. (eds.). p. 283-296

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  • Brick 100%
  • Sand 83%
  • Rocks 79%
  • Scheduling 64%

• Stochastic Probing with Increasing Precision

  Hoefer, M., Schewior, K. & Schmand, D., 2021, Proceedings of the 30th International Joint Conference on Artificial Intelligence, IJCAI 2021: Montreal, 19-27 August 2021. Zhou, Z-H. (ed.). p. 4069-4075

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Testing 100%
  • Expected Value 72%
  • Maximise 66%
  • Scenarios 64%
  • Polynomial-time Algorithm 64%

• Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility

  Correa, J., Dütting, P., Fischer, F., Schewior, K. & Ziliotto, B., 2021, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, (Leibniz International Proceedings in Informatics, Vol. 185).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  • Streaming 100%
  • Unknown 48%
  • Prophet Inequality 41%
  • Pricing 27%
  • Random variable 26%
• 2020

  Optimally handling commitment issues in online throughput maximization

  Eberle, F., Megow, N. & Schewior, K., 1. Aug 2020, 28th Annual European Symposium on Algorithms (ESA 2020). Grandoni, F., Herman, G. & Sanders, P. (eds.). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Vol. 173. p. 41:1-41:15 41

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  • Throughput 100%
  • Scheduling 98%
  • Cloud computing 42%
• 2019

  A general framework for handling commitment in online admission control

  Chen, L., Eberle, F., Megow, N., Schewior, K. & Stein, C., 2019, Conference on Integer Programming and Combinatorial Optimization (IPCO). p. 141-154

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

• A PTAS for TSP with hyperplane neighborhoods

  Antoniadis, A., Fleszar, K., Hoeksma, R. & Schewior, K., 2019, ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, p. 1089-1105

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Polynomial Time Approximation Scheme 100%
  • Hyperplane 76%
  • Polytope 55%
  • Convex Polytope 47%
  • Search Space 24%

• Improved Bounds for Open Online Dial-a-Ride on the Line

  Birx, A., Disser, Y. & Schewior, K., 2019, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Achlioptas, D. & Vegh, L. A. (eds.). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, p. 1-22 (Leibniz International Proceedings in Informatics (LIPIcs)).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  File

  • Line 100%
  • Competitive Analysis 78%
  • Analysis of Algorithms 67%
  • Lower bound 66%
  • Single Server 63%
  2 Downloads (Pure)

• Online Multistage Subset Maximization Problems

  Bampis, E., Escoffier, B., Schewior, K. & Teiller, A., 2019, 27th European Symposium on Algorithms (ESA 2019). Bender, M. A. (ed.). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, p. 11:1-11:14

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

• Prophet Inequalities for I.I.D. Random Variables from an Unknown Distribution

  Correa, J., Dütting, P., Fischer, F. & Schewior, K., 2019, EC '19: Proceedings of the 2019 ACM Conference on Economics and Computation. Association for Computing Machinery, p. 3-17

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Prophet Inequality 100%
  • I.i.d. Random Variables 71%
  • Unknown 39%
  • Random variable 28%
  • Stopping Time 23%
• 2018

  A tight lower bound for online convex optimization with switching costs

  Antoniadis, A. & Schewior, K., 2018, Approximation and Online Algorithms: 15th International Workshop, WAOA 2017, Vienna, Austria, September 7–8, 2017, Revised Selected Papers. Solis-Oba, R. & Fleischer, R. (eds.). p. 164-175 (Theoretical Computer Science and General Issues).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Convex optimization 100%
  • Costs 35%
  • Servers 34%

• Handling critical tasks online

  Schewior, K., 2018, Operations Research Proceedings 2017: Selected Papers of the Annual International Conference of the German Operations Research Society (GOR), Freie Universiät Berlin, Germany, September 6-8, 2017. Springer, p. 25-29 (Operations Research Proceedings).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Autonomous vehicles 100%
  • Scheduling 64%

• Preface: A (Super)Natural variant of the card game SET

  Botler, F., Cristi, A., Hoeksma, R., Schewior, K. & Tönnis, A., 2018, International Conference on FUN with Algorithms (FUN). p. ix

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  Open Access

  File
  2 Downloads (Pure)

• The Itinerant List-Update Problem

  Olver, N., Pruhs, K., Schewior, K., Sitters, R. & Stougie, L., 2018, Workshop on Approximation and Online Algorithms (WAOA). Epstein, L. & Erlebach, T. (eds.). Springer, p. 310-326 17 p. (Lecture Notes in Computer Science, Vol. 11312).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Domain walls 100%
  • Data storage equipment 81%
  • Approximation algorithms 72%
  • Relaxation 62%
• 2017

  Tight Bounds for Online TSP on the Line

  Bjelde, A., Disser, Y., Hackfeld, J., Hansknecht, C., Lipmann, M., Meißner, J., Schewior, K., Schlöter, M. & Stougie, L., 2017, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. Klein, P. N. (ed.). Association for Computing Machinery, p. 994-1005 12 p.

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Servers 100%
  • NP-hard 44%
• 2016

  An O(log m)-competitive algorithm for online machine minimization

  Chen, L., Megow, N. & Schewior, K., 2016, SODA '16: Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms. Kraughgamer, R. (ed.). p. 155-163

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

• Chasing convex bodies and functions

  Antoniadis, A., Barcelo, N., Nugent, M., Pruhs, K., Schewior, K. & Scquizzato, M., Dec 2016, LATIN 2016: Theoretical Informatics: 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings. Navarro, G., Kranakis, E. & Chávez, E. (eds.). Springer, p. 68-81 (Lecture Notes in Computer Science).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Convex optimization 100%
  • Cost functions 21%
  • Costs 8%

• The Power of Migration in Online Machine Minimization

  Chen, L., Megow, N. & Schewior, K., 11. Jul 2016, SPAA 2016 - Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery, p. 175-184

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Scheduling 100%
• 2015

  A 2-competitive algorithm for online convex optimization with switching costs

  Bansal, N., Gupta, A., Krishnaswamy, R., Pruhs, K., Schewior, K. & Stein, C., 1. Aug 2015, Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). Garg, N., Jansen, K., Rao, A. & Rolim, J. D. P. (eds.). p. 96-109

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Online Optimization 100%
  • Online Algorithms 78%
  • Convex Optimization 63%
  • Costs 44%
  • Real Line 37%
• 2014

  Routing Games with Progressive Filling

  Harks, T., Skopalik, A., Hoefer, M. & Schewior, K., 2014, IEEE INFOCOM 2014: IEEE Conference on Computer Communications. IEEE, p. 352-360

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Bandwidth 100%
  • Polynomials 81%
  • NP-hard 51%