René van Bevern

Рене Андреасович ван Беверн

Novosibirsk State University



Dr. rer. nat. René van Bevern <rvb@rvb.su>
Research group leader and senior lecturer
Department of Mechanics and Mathematics,
Novosibirsk State University,
Novosibirsk, Russian Federation

News: Twitter (en), LinkedIn (en), VK (ru)

Publications: Google Scholar, Scopus, ResearchGate, DBLP.

Private: Instagram.


Research


Research projects

2018–present
Leading Russian team of joint project № 18-501-12031 of the Russian Foundation for Basic Research and the German Research Foundation: Trade-offs in parameterized data reduction. Novosibirsk State University. German team leader: Rolf Niedermeier.
2019–2020
Stipend of the President of the Russian Federation for research on parameterized algorithms for discrete optimization problems of wireless communication networks.
2016–2018
Leading project № 16-31-60007 mol_a_dk of the Russian Foundation for Basic Research: Parameterized algorithms for NP-hard routing and scheduling problems. Novosibirsk State University.
2016–2018
Employed in project № 16-11-10041 of the Russian Science Foundation: Discrete optimization problems in computer technologies for massive data analysis. Sobolev Institute of Mathematics.
2011–2015
Employed in project DAPA (NI 369/12) of the German Research Foundation: Data Driven Parameterized Algorithmics for Graph Modification Problems. TU Berlin.
2010
Employed in project AREG (NI 369/9) of the German Research Foundation: Algorithms for Generating Quasi-Regular Structures in Graphs. Friedrich-Schiller-Universität Jena.

Committees

Program committee:
AAAI 2020, AAAI 2021, CSR 2019, CSR 2018, IJCAI 2020, IJCAI 2019, IJCAI-ECAI 2018, IJCAI 2016, MOTOR 2020, MOTOR 2019, OPCS 2016 OPTA 2019, OPTIMA 2019, WG 2017,
Organizing committee:
CSR 2019 (chair), G2R2, G2S2

Teaching


Since 2018 I usually teach my courses in Russian.
Complexity Theory I
Novosibirsk State University (Autumn 2019)
Complexity Theory II
Novosibirsk State University (Spring 2020)
Randomized Algorithms
Novosibirsk State University (Spring 2016, 2017, 2018), TU Berlin (Summer 2014).
Fixed-Parameter Algorithms
Novosibirsk State University (Autumn 2015, 2016, 2017).
Advanced Algorithmics
TU Berlin (Winter 2014/15).

Publications



Click the publication label to see the abstract, links to the publication, and BibTeX entry. See also Google Scholar, DBLP, and my BibTeX file.

Journal articles

Upcoming

[BKM+xx]
René van Bevern, Christian Komusiewicz, Hendrik Molter, Rolf Niedermeier, Manuel Sorge, and Toby Walsh. H-index manipulation by undoing merges. Quantitative Science Studies, Accepted for publication.
[BBN+xx]
Matthias Bentert, René van Bevern, André Nichterlein, Rolf Niedermeier, and Pavel V. Smirnov. Parameterized algorithms for power-efficiently connecting wireless sensor networks: Theory and experiments. INFORMS Journal on Computing, Accepted for publication.

2020

[BS20b]
René van Bevern and Viktoriia A. Slugina. A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem. Historia Mathematica, 53:118–127, 2020.
[BFT20b]
René van Bevern, Till Fluschnik, and Oxana Yu. Tsidulko. On approximate data reduction for the Rural Postman Problem: Theory and experiments. Networks, 76(4):485–508, 2020.
[BS20]
René van Bevern and Pavel V. Smirnov. Optimal-size problem kernels for d-hitting set in linear time and space. Information Processing Letters, page 105998, 2020.
[BFT20]
René van Bevern, Till Fluschnik, and Oxana Yu. Tsidulko. Parameterized algorithms and data reduction for the short secluded s-t-path problem. Networks, 75(1):34–63, 2020.

2019

[BBN19]
Matthias Bentert, René van Bevern, and Rolf Niedermeier. Inductive k-independent graphs and c-colorable subgraphs in scheduling: A review. Journal of Scheduling, 22(1):3–20, 2019.
[BPS19]
René A. van Bevern, Artem V. Pyatkin, and Sergey V. Sevastyanov. An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times. Siberian Electronic Mathematical Reports, 16:42–84, 2019.

2018

[BFM+18]
René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge, and Ondřej Suchý. The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs. Discrete Optimzation, 30:20–50, 2018.
[MB18]
Matthias Mnich and René van Bevern. Parameterized complexity of machine scheduling: 15 open problems. Computers & Operations Research, 100:254–261, 2018.
[BFK18]
René van Bevern, Vincent Froese, and Christian Komusiewicz. Parameterizing edge modification problems above lower bounds. Theory of Computing Systems, 62(3):739–770, 2018. CSR'16 special issue.

2017

[BKS17]
René van Bevern, Christian Komusiewicz, and Manuel Sorge. A parameterized approximation algorithm for the mixed and windy capacitated arc routing problem: theory and experiments. Networks, 70(3):262–278, 2017. WARP 2 special issue.
[BBB+17]
René van Bevern, Robert Bredereck, Laurent Bulteau, Jiehua Chen, Vincent Froese, Rolf Niedermeier, and Gerhard J. Woeginger. Partitioning perfect graphs into stars. Journal of Graph Theory, 85(2):297–335, 2017.
[BNS17]
René van Bevern, Rolf Niedermeier, and Ondřej Suchý. A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack. Journal of Scheduling, 20(3):255–265, 2017.
[BBC+17]
René van Bevern, Robert Bredereck, Morgan Chopin, Sepp Hartung, Falk Hüffner, André Nichterlein, and Ondřej Suchý. Fixed-parameter algorithms for DAG partitioning. Discrete Applied Mathematics, 220:134–160, 2017.

2016

[BKN+16]
René van Bevern, Christian Komusiewicz, Rolf Niedermeier, Manuel Sorge, and Toby Walsh. H-index manipulation by merging articles: Models, theory, and experiments. Artificial Intelligence, 240:19–35, 2016.
[FBNS16]
Vincent Froese, René van Bevern, Rolf Niedermeier, and Manuel Sorge. Exploiting hidden structure in selecting dimensions that distinguish vectors. Journal of Computer and System Sciences, 82(3):521–535, 2016.

2015

[BCH+15]
René van Bevern, Jiehua Chen, Falk Hüffner, Stefan Kratsch, Nimrod Talmon, and Gerhard J. Woeginger. Approximability and parameterized complexity of multicover by c-intervals. Information Processing Letters, 115(10):744–749, 2015.
[BMNW15]
René van Bevern, Matthias Mnich, Rolf Niedermeier, and Mathias Weller. Interval scheduling and colorful independent sets. Journal of Scheduling, 18(5):449–469, 2015.
[BFSS15]
René van Bevern, Andreas Emil Feldmann, Manuel Sorge, and Ondřej Suchý. On the parameterized complexity of computing balanced partitions in graphs. Theory of Computing Systems, 57(1):1–35, 2015.
[BBC+15]
René van Bevern, Robert Bredereck, Jiehua Chen, Vincent Froese, Rolf Niedermeier, and Gerhard J. Woeginger. Network-based vertex dissolution. SIAM Journal on Discrete Mathematics, 29(2):888–914, 2015.
[BDF+15]
René van Bevern, Rodney G. Downey, Michael R. Fellows, Serge Gaspers, and Frances A. Rosamond. Myhill-nerode methods for hypergraphs. Algorithmica, 73(4):696–729, 2015. ISAAC'13 special issue.

2014

[Bev14b]
René van Bevern. Towards optimal and expressive kernelization for d-hitting set. Algorithmica, 70(1):129–147, 2014. COCOON'12 special issue.
[BHNS14]
René van Bevern, Sepp Hartung, André Nichterlein, and Manuel Sorge. Constant-factor approximations for capacitated arc routing without triangle inequality. Operations Research Letters, 42(4):290–292, 2014.

2012

[SBNW12]
Manuel Sorge, René van Bevern, Rolf Niedermeier, and Mathias Weller. A new view on rural postman based on eulerian extension and matching. Journal of Discrete Algorithms, 16:12–33, 2012. IWOCA'11 special issue.
[BMN12]
René van Bevern, Hannes Moser, and Rolf Niedermeier. Approximation and tidying—a problem kernel for s-plex cluster vertex deletion. Algorithmica, 62(3-4):930–950, 2012.

2011

[BBF+11]
Nadja Betzler, René van Bevern, Michael R. Fellows, Christian Komusiewicz, and Rolf Niedermeier. Parameterized algorithmics for finding connected motifs in biological networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8(5):1296–1308, 2011.

Conference articles

2019

[BFT19]
René van Bevern, Till Fluschnik, and Oxana Yu. Tsidulko. On (1+ɛ)-approximate data reduction for the Rural Postman Problem. In Proceedings of the 18th International Conference on Mathematical Optimization Theory and Operations Research (MOTOR 2019), volume 11548 of Lecture Notes in Computer Science, pages 279–294, 2019.
[BTZ19]
René van Bevern, Oxana Yu. Tsidulko, and Philipp Zschoche. Fixed-parameter algorithms for maximum-profit facility location under matroid constraints. In Proceedings of the 11th International Conference on Algorithms and Complexity (CIAC'19), Rome, Italy, Lecture Notes in Computer Science, pages 62–74. Springer, 2019.

2018

[BFT18]
René van Bevern, Till Fluschnik, and Oxana Yu. Tsidulko. Parameterized algorithms and data reduction for safe convoy routing. In Proceedings of the 18th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'18), Helsinki, Finland, volume 65 of OpenAccess Series in Informatics (OASIcs), pages 10:1–10:19. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018.

2017

[BBNN17]
M. Bentert, R. van Bevern, A. Nichterlein, and R. Niedermeier. Parameterized algorithms for power-efficient connected symmetric wireless sensor networks. In Proceedings of the 13th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS'17), Wien, Austria, volume 10718 of Lecture Notes in Computer Science, pages 26–40. Springer, 2017.
[BFM+17]
René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge, and Ondřej Suchý. Finding secluded places of special interest in graphs. In Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC'16), Aarhus, Denmark, volume 63 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:16. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017.

2016

[BKK+16]
René van Bevern, Iyad Kanj, Christian Komusiewicz, Rolf Niedermeier, and Manuel Sorge. Twins in subdivision drawings of hypergraphs. In Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD'16), Athens, Greece, volume 9801 of Lecture Notes in Computer Science, pages 67–80. Springer, 2016.
[BBB+16]
René van Bevern, Robert Bredereck, Laurent Bulteau, Christian Komusiewicz, Nimrod Talmon, and Gerhard J. Woeginger. Precedence-constrained scheduling problems parameterized by partial order width. In Proceedings of the 9th International Conference on Discrete Optimization and Operations Research (DOOR'16), Vladivostok, Russian Federation, volume 9869 of Lecture Notes in Computer Science, pages 105–120. Springer, 2016.
[BKM+16]
René van Bevern, Christian Komusiewicz, Hendrik Molter, Rolf Niedermeier, Manuel Sorge, and Toby Walsh. H-index manipulation by undoing merges. In Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI'16), The Hague, Holland, volume 285 of Frontiers in Artificial Intelligence and Applications, pages 895–903, 2016.
[BFK16]
René van Bevern, Vincent Froese, and Christian Komusiewicz. Parameterizing edge modification problems above lower bounds. In Proceedings of the 11th International Computer Science Symposium in Russia (CSR'16), St. Petersburg, Russian Federation, volume 9691 of Lecture Notes in Computer Science, pages 57–72. Springer, 2016. The final version of this article appeared in the CSR'16 special issue of Theory of Computing Systems.
[BP16]
René van Bevern and Artem V. Pyatkin. Completing partial schedules for open shop with unit processing times and routing. In Proceedings of the 11th International Computer Science Symposium in Russia (CSR'16), St. Petersburg, Russian Federation, volume 9691 of Lecture Notes in Computer Science, pages 73–87. Springer, 2016.

2015

[BKS15]
René van Bevern, Christian Komusiewicz, and Manuel Sorge. Approximation algorithms for mixed, windy, and capacitated arc routing problems. In Proceedings of the 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'15), Patras, Greece, volume 48 of OpenAccess Series in Informatics (OASIcs), pages 130–143. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015. Best paper award. The final version of this article appeared in the WARP 2 special issue of Networks.
[BKN+15]
René van Bevern, Christian Komusiewicz, Rolf Niedermeier, Manuel Sorge, and Toby Walsh. H-index manipulation by merging articles: Models, theory, and experiments. In Proceedings of the 24th International Joint Conference on Artificial Intelligence, IJCAI'15, Buenos Aires, Argentina, pages 808–814. AAAI Press, 2015. The final version of this article appeared in Artificial Intelligence.

2014

[BBC+14b]
René van Bevern, Robert Bredereck, Jiehua Chen, Vincent Froese, Rolf Niedermeier, and Gerhard J. Woeginger. Network-based dissolution. In Proceedings of 39th International Symposium on Mathematical Foundations of Computer Science (MFCS'14), Budapest, Hungary, volume 8635 of Lecture Notes in Computer Science, pages 69–80. Springer, 2014. The final version of this article appeared in SIAM Journal on Discrete Mathematics.
[BBB+14]
René van Bevern, Robert Bredereck, Laurent Bulteau, Jiehua Chen, Vincent Froese, Rolf Niedermeier, and Gerhard J. Woeginger. Star partitions of perfect graphs. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP'14), Copenhagen, Denmark, volume 8572 of Lecture Notes in Computer Science, pages 174–185. Springer, 2014. The final version of this article appeared in Journal of Graph Theory.

2013

[BFGR13]
René van Bevern, Michael R. Fellows, Serge Gaspers, and Frances A. Rosamond. Myhill-nerode methods for hypergraphs. In Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC'13), Hong Kong, China, volume 8283 of Lecture Notes in Computer Science, pages 372–382. Springer, 2013. The final version of this article appeared in the ISAAC'13 special issue of Algorithmica.
[FBNS13]
Vincent Froese, René van Bevern, Rolf Niedermeier, and Manuel Sorge. A parameterized complexity analysis of combinatorial feature selection problems. In Proceedings of the 38th International on Symposium Mathematical Foundations of Computer Science (MFCS'13), Klosterneuburg, Austria, volume 8087 of Lecture Notes in Computer Science, pages 445–456. Springer, 2013. The final version of this article appeared in Journal of Computer and System Sciences.
[BFSS13]
René van Bevern, Andreas Emil Feldmann, Manuel Sorge, and Ondřej Suchý. On the parameterized complexity of computing graph bisections. In Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'13), Lübeck, Germany, volume 8165 of Lecture Notes in Computer Science, pages 76–87. Springer, 2013. The final version of this article appeared in Theory of Computing Systems.
[BBC+13]
René van Bevern, Robert Bredereck, Morgan Chopin, Sepp Hartung, Falk Hüffner, André Nichterlein, and Ondřej Suchý. Parameterized complexity of DAG partitioning. In Proceedings of the 8th International Conference on Algorithms and Complexity (CIAC'13), Barcelona, Spain, volume 7878 of Lecture Notes in Computer Science, pages 49–60. Springer, 2013. A final version of this article with improved algorithms and an experimental evaluations has appeared in Discrete Applied Mathematics.

2012

[BMNW12]
René van Bevern, Matthias Mnich, Rolf Niedermeier, and Mathias Weller. Interval scheduling and colorful independent sets. In Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC'12), Taipei, Taiwan, volume 7676 of Lecture Notes in Computer Science, pages 247–256. Springer, 2012. The final version of this article appeared in Journal of Scheduling.
[BHK+11]
René van Bevern, Sepp Hartung, Frank Kammer, Rolf Niedermeier, and Mathias Weller. Linear-time computation of a linear problem kernel for dominating set on planar graphs. In Proceedings of the 6th International Symposium on Parameterized and Exact Computation (IPEC'11), Saarbrücken, Germany, volume 7112 of Lecture Notes in Computer Science, pages 194–206. Springer, 2012.
[Bev12]
René van Bevern. Towards optimal and expressive kernelization for d-hitting set. In Proceedings of the 18th Annual International Computing and Combinatorics Conference (COCOON'12), Sydney, Australia, volume 7434 of Lecture Notes in Computer Science, pages 121–132. Springer, 2012. The final version of this article appeared in the COCOON'12 special issue of Algorithmica.

2011

[SBNW11]
Manuel Sorge, René van Bevern, Rolf Niedermeier, and Mathias Weller. From few components to an eulerian graph by adding arcs. In Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'11), Teplá Monastery, Czech Republic, volume 6986 of Lecture Notes in Computer Science, pages 307–318. Springer, 2011.

2010

[BKMN10]
René van Bevern, Christian Komusiewicz, Hannes Moser, and Rolf Niedermeier. Measuring indifference: Unit interval vertex deletion. In Proceedings of the 36th International Workshop on Graph Theoretic Concepts in Computer Science (WG'10), Zarós, Crete, Greece, volume 6410 of Lecture Notes in Computer Science, pages 232–243. Springer, 2010.
[BMN10]
René van Bevern, Hannes Moser, and Rolf Niedermeier. Kernelization through tidying—a case study based on s-plex cluster vertex deletion. In Proceedings of the 9th Latin American Symposium on Theoretical Informatics (LATIN'10), Oaxaca, Mexico, volume 6034 of Lecture Notes in Computer Science, pages 527–538. Springer, 2010. The final version of this article appeared in Algorithmica.

Book chapters

[BNSW14]
René van Bevern, Rolf Niedermeier, Manuel Sorge, and Mathias Weller. Complexity of arc routing problems. In Ángel Corberán and Gilbert Laporte, editors, Arc Routing: Problems, Methods, and Applications, chapter 2. SIAM, 2014.

Edited works

[BK19]
René van Bevern and Gregory Kucherov, editors. Proceedings of the 14th International Computer Science Symposium in Russia (CSR 2019), Novosibirsk, Russian Federation, July 1-5, 2019, volume 11532 of Lecture Notes in Computer Science. Springer, 2019.

Theses

[Bev09]
René van Bevern. Graph-based data clustering: a quadratic-vertex problem kernel for s-plex cluster vertex deletion, 2009. Undergraduate thesis.
[Bev10]
René van Bevern. The computational hardness and tractability of restricted seriation problems on inaccurate data. Master's thesis, Institut für Informatik, Friedrich-Schiller-Universität, Jena, Germany, 2010. Diploma thesis.
[Bev14]
René van Bevern. Fixed-Parameter Linear-Time Algorithms for NP-hard Graph and Hypergraph Problems Arising in Industrial Applications. PhD thesis, Fakultät IV – Elektrotechnik und Informatik, TU Berlin, 2014. PhD thesis.

Student's work

[Smi18]
Pavel V. Smirnov. Редукция данных для задачи о вершинном покрытии гиперграфа за линейное время с линейной памятью (Russian; data reduction for the vertex cover problem in hypergraphs in linear time and linear space). Bachelor's thesis.
[Smi20]
Pavel V. Smirnov. Разработка алгоритмов и программного обеспечения для решения задач анализа сетевых структур (Russian; development of algorithms and software for solving network analysis problems). Master's thesis, Novosibirsk State University, Novosibirsk, Russian Federation, 2020.

Manuscripts waiting for publication

[BBF+xx]
Matthias Bentert, René van Bevern, Till Fluschnik, André Nichterlein, and Rolf Niedermeier. Polynomial-time preprocessing for weighted problems beyond additive goal functions. 2019.
[BTZxx]
René van Bevern, Oxana Yu. Tsidulko, and Philipp Zschoche. Fixed-parameter algorithms for maximum-profit facility location under matroid constraints. 2019.
[ABTxx]
Vsevolod A. Afanasev, René van Bevern, and Oxana Yu. Tsidulko. The hierarchical Chinese postman problem: the slightest disorder makes it hard, yet disconnectedness is manageable. 2020.
[BKK+xx]
René van Bevern, Iyad Kanj, Christian Komusiewicz, Rolf Niedermeier, and Manuel Sorge. The role of twins in computing planar supports of hypergraphs. 2020.

Last modified: Tue Nov 17 16:48:49 UTC 2020