Dr. rer. nat. René van Bevern

Senior researcher and lecturer at Novosibirsk State University

(Рене ван Беверн)



Senior researcher
Institute of Discrete Mathematics and Informatics,
Scientific Research Department,
Novosibirsk State University,
Novosibirsk, Russian Federation
(ИДМИ НИЧ НГУ)

Lecturer
Chair of Theoretical Cybernetics,
Deptartment of Mathematics and Mechanics,
Novosibirsk State University,
Novosibirsk, Russian Federation
(КафТК ММФ НГУ)

E-Mail: rvb@nsu.ru
Room: 215 ИМ

Google Scholar, DBLP, arXiv,
Scopus, ResearchGate, BibTeX


Research

My main field of research are algorithms for optimally solving NP-hard discrete optimization problems by exploiting structure in practically occuring data (``fixed-parameter algorithms''). Ideally, the algorithms run in linear time when certain parameters in the input data are bounded by constants.

Research projects

2016/01–present
Leading project № 16-31-60007 mol_a_dk of the Russian Foundation for Basic Research:
Parameterized algorithms for NP-hard routing and scheduling problems.
Institute of Discrete Mathematics and Informatics, Scientific Research Departement, Novosibirsk State University, Russian Federation.
2011/01–2015/04
Employed in project DAPA (NI 369/12) of the German Research Foundation:
Data Driven Parameterized Algorithmics for Graph Modification Problems.
Algorithms and Complexity Theory group, TU Berlin, Germany.
2010/04–2010/12
Employed in project AREG (NI 369/9) of the German Research Foundation:
Algorithms for Generating Quasi-Regular Structures in Graphs.
Chair Theoretische Informatik I, Institut für Informatik, Friedrich-Schiller-Universität Jena, Germany.

Committees

IJCAI 2016
Program committee member at the 25th International Joint Conference on Artificial Intelligence IJCAI-16, July 9-15th, 2016, New York, USA.

Teaching

I am currently teaching in the international master program Applied Mathematics and Stochastics of the Department of Mathematics and Mechanics of Novosibirsk State University.

Spring 2016
Randomized Algorithms, Novosibirsk State University.
Autumn 2015
Fixed-Parameter Algorithms, Novosibirsk State University.
Winter 2014/15
Advanced Algorithmics, TU Berlin.
Summer 2014
Randomized Algorithms, TU Berlin.

Conference Talks

17. September 2015
15th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'15), Patras, Greece.
16-18. December 2013
24th International Symposium on Algorithms and Computation (ISAAC'13), Hong Kong, China.
19-21. June 2013
39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'13), Lübeck, Germany.
14-15. February 2013
65th Theorietag, Paderborn, Germany.
16-17. November 2012
Colloquium on Combinatorics (KolKom) 2012, Berlin, Germany.
20-22. August 2012
18th Annual International Computing and Combinatorics Conference (COCOON'12), Sydney, Australia.
17-18. January 2012
63rd Theorietag, Brandenburg, Germany
24-25. February 2011
61st Theorietag, Trier, Germany
18-30. June 2010
36th International Workshop on Graph Theoretic Concepts in Computer Science (WG'10), Zaros, Crete, Greece
24. February 2010
59th Theorietag, Ilmenau, Germany.

Publications

Book Chapters

  1. van Bevern R, Niedermeier R, Sorge M and Weller M (2014), Complexity of arc routing problems, In Arc Routing: Problems, Methods, and Applications, December, 2014. SIAM. [DOI]

Invited Journal Articles

  1. van Bevern R, Downey RG, Fellows MR, Gaspers S and Rosamond FA (2015), Myhill-Nerode Methods for Hypergraphs, Algorithmica 73(4):696-729, December, 2015. ISAAC'13 special issue. [DOI] [URL]
  2. van Bevern R (2014), Towards Optimal and Expressive Kernelization for d-Hitting Set, Algorithmica 70(1):129-147, September, 2014. COCOON'12 special issue. [DOI] [URL] [source code]
  3. Sorge M, van Bevern R, Niedermeier R and Weller M (2012), A new view on Rural Postman based on Eulerian Extension and Matching, Journal of Discrete Algorithms 16:12-33, October, 2012. IWOCA 2011 special issue. [DOI] [URL]

Journal Articles

  1. Froese V, van Bevern R, Niedermeier R and Sorge M (2016) Exploiting hidden structure in selecting dimensions that distinguish vectors Journal of Computer and System Sciences 82(3):521-535, May, 2016. [DOI] [URL]
  2. van Bevern R, Niedermeier R and Suchý O (2016) A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack Journal of Scheduling, January, 2016. Accepted for publication. [URL]
  3. van Bevern R, Chen J, Hüffner F, Kratsch S, Talmon N and Woeginger GJ (2015) Approximability and parameterized complexity of multicover by c-intervals Information Processing Letters 115(10):744-749, October, 2015. [DOI] [URL]
  4. van Bevern R, Mnich M, Niedermeier R and Weller M (2015), Interval scheduling and colorful independent sets, Journal of Scheduling 18(5):449-469, October, 2015. [DOI] [URL]
  5. van Bevern R, Feldmann AE, Sorge M and Suchý O (2015), On the Parameterized Complexity of Computing Balanced Partitions in Graphs, Theory of Computing Systems 57(1):1-35, July, 2015. [DOI] [URL]
  6. van Bevern R, Bredereck R, Chen J, Froese V, Niedermeier R and Woeginger GJ (2015), Network-Based Vertex Dissolution, SIAM Journal on Discrete Mathematics 29(2):888-914, May, 2015. [DOI] [URL]
  7. van Bevern R, Hartung S, Nichterlein A and Sorge M (2014), Constant-factor approximations for Capacitated Arc Routing without triangle inequality, Operations Research Letters 42(4):290-292, June, 2014. [DOI] [URL]
  8. van Bevern R, Moser H and Niedermeier R (2012), Approximation and Tidying-A Problem Kernel for s-Plex Cluster Vertex Deletion, Algorithmica 62(3-4):930-950, April, 2012. [DOI] [URL]
  9. Betzler N, van Bevern R, Fellows MR, Komusiewicz C and Niedermeier R (2011), Parameterized Algorithmics for Finding Connected Motifs in Biological Networks, Computational Biology and Bioinformatics, IEEE/ACM Transactions on 8(5):1296-1308, September, 2011. [DOI] [URL] [source code]

Conference Articles

  1. van Bevern R, Komusiewicz C and Sorge M (2015), 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, September, 2015. Vol. 48 in OpenAccess Series in Informatics (OASIcs), pp. 130-143. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. Best paper award. [DOI] [URL]
  2. van Bevern R, Komusiewicz C, Niedermeier R, Sorge M and Walsh T (2015), 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, July, 2015., pp. 808-814. AAAI Press. [URL]
  3. van Bevern R, Bredereck R, Chen J, Froese V, Niedermeier R and Woeginger GJ (2014), Network-Based Dissolution, In Proceedings of 39th International Symposium on Mathematical Foundations of Computer Science (MFCS'14), Budapest, Hungary, August, 2014. Vol. 8635 in Lecture Notes in Computer Science, pp. 69-80. Springer. A journal version appeared in SIAM Journal on Discrete Mathematics. [DOI] [URL]
  4. van Bevern R, Bredereck R, Bulteau L, Chen J, Froese V, Niedermeier R and Woeginger GJ (2014), Star Partitions of Perfect Graphs, In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP'14), Copenhagen, Denmark, July, 2014. Vol. 8572 in Lecture Notes in Computer Science, pp. 174-185. Springer. [DOI] [URL]
  5. van Bevern R, Fellows MR, Gaspers S and Rosamond FA (2013), Myhill-Nerode Methods for Hypergraphs, In Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC'13), Hong Kong, China, December, 2013. Vol. 8283 in Lecture Notes in Computer Science, pp. 372-382. Springer. A journal version appeared in the ISAAC'13 special issue of Algorithmica. [DOI] [URL]
  6. Froese V, van Bevern R, Niedermeier R and Sorge M (2013), 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, August, 2013. Vol. 8087 in Lecture Notes in Computer Science, pp. 445-456. Springer. A journal version appeared in Journal of Computer and System Sciences. [DOI] [URL]
  7. van Bevern R, Feldmann AE, Sorge M and Suchý O (2013), 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, June, 2013. Vol. 8165 in Lecture Notes in Computer Science, pp. 76-87. Springer. A journal version appeared in Theory of Computing Systems. [DOI] [URL] [slides]
  8. van Bevern R, Bredereck R, Chopin M, Hartung S, Hüffner F, Nichterlein A and Suchý O (2013), Parameterized Complexity of DAG Partitioning, In Proceedings of the 8th International Conference on Algorithms and Complexity (CIAC'13), Barcelona, Spain, May, 2013. Vol. 7878 in Lecture Notes in Computer Science, pp. 49-60. Springer. Improved algorithms and experimental evaluations can be found in my Dissertation.. [DOI] [URL]
  9. van Bevern R, Mnich M, Niedermeier R, Weller M (2012), Interval Scheduling and Colorful Independent Sets, In Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC'12), Taipei, Taiwan, December, 2012. Vol. 7676(7676) in Lecture Notes in Computer Science, pp. 247-256. Springer. A journal version appeared in Journal of Scheduling. [DOI]
  10. van Bevern R, Hartung S, Kammer F, Niedermeier R, Weller M (2012), 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, September, 2012. Vol. 7112 in Lecture Notes in Computer Science, pp. 194-206. Springer. [DOI] [URL] [slides]
  11. van Bevern R (2012), Towards Optimal and Expressive Kernelization for $d$-Hitting Set, In Proceedings of the 18th Annual International Computing and Combinatorics Conference (COCOON'12), Sydney, Australia, August, 2012. Vol. 7434 in Lecture Notes in Computer Science, pp. 121-132. Springer. A journal version appeared in the COCOON'12 special issue of Algorithmica. [DOI] [slides]
  12. Sorge M, van Bevern R, Niedermeier R, Weller M (2011), 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, June, 2011. Vol. 6986 in Lecture Notes in Computer Science, pp. 307-318. Springer. [DOI] [URL]
  13. van Bevern R, Komusiewicz C, Moser H and Niedermeier R (2010), 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, June, 2010. Vol. 6410 in Lecture Notes in Computer Science, pp. 232-243. Springer. [DOI] [URL] [slides]
  14. van Bevern R, Moser H and Niedermeier R (2010), 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, April, 2010. Vol. 6034 in Lecture Notes in Computer Science, pp. 527-538. Springer. A journal version appeared in Algorithmica. [DOI] [slides]

Theses

  1. van Bevern R (2014), Fixed-Parameter Linear-Time Algorithms for NP-hard Graph and Hypergraph Problems Arising in Industrial Applications, October, 2014. Universitätsverlag der TU Berlin. PhD thesis. [DOI] [slides]
  2. van Bevern R (2010), The Computational Hardness and Tractability of Restricted Seriation Problems on Inaccurate Data. Thesis at: Institut für Informatik, Friedrich-Schiller-Universität Jena, Germany, April, 2010. Diploma thesis. [URL] [slides]
  3. van Bevern R (2009), Graph-based data clustering: a quadratic-vertex problem kernel for s-Plex Cluster Vertex Deletion. Thesis at: Institut für Informatik, Friedrich-Schiller-Universität Jena, Germany, September, 2009. Undergraduate thesis. [URL] [slides]

Manuscripts under review

  1. van Bevern R, Froese V and Komusiewicz C (2015) Parameterizing edge modification problems above lower bounds December, 2015. [URL]
  2. van Bevern R and Pyatkin AV (2015), Completing partial schedules for Open Shop with unit processing times and routing, December, 2015.
  3. van Bevern R, Kanj I, Komusiewicz C, Niedermeier R and Sorge M (2015), Separating an r-outerplanar graph into gluable pieces, November, 2015. [URL]
  4. van Bevern R, Kanj I, Komusiewicz C, Niedermeier R and Sorge M (2015), Well-Formed Separator Sequences, with an Application to Hypergraph Drawing, July, 2015. [URL]
  5. van Bevern R, Bredereck R, Bulteau L, Chen J, Froese V, Niedermeier R and Woeginger GJ (2015), Partitioning perfect graphs into stars, May, 2015.
  6. van Bevern R, Bredereck R, Chopin M, Hartung S, Hüffner F, Nichterlein A and Suchý O (2014), Fixed-parameter algorithms for DAG Partitioning, November, 2014.

Thanks to Christoph Taszus for providing me with web space. © 2010–2015 René van Bevern. Last modified 2015-12-09.