Dr. rer. nat. René van Bevern (Рене ван Беверн)

Postdoc at Novosibirsk State University, Novosibirsk, Russian Federation. E-Mail: rvb@nsu.ru

Teaching
I am teaching the courses
  • Fixed-Parameter Algorithms and
  • Randomized Algorithms
in the international master program Applied Mathematics and Stochastics of the Department of Mathematics and Mechanics of Novosibirsk State University.
Research
Fast algorithms for NP-hard discrete optimization problems by exploiting structures 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.
Photography
Sometimes I am lucky and happen to take some good photo with my cell phone camera. The photos are available at 500px.com.
From January 2011 till May 2015
PhD student and postdoc at the Algorithms and Complexity Theory group, TU Berlin, Germany, funded by the DFG project “Data Driven Parameterized Algorithmics for Graph Modification Problems”.
From April till December 2010
PhD student at the Chair Theoretische Informatik I, Institut für Informatik, Friedrich-Schiller-Universität Jena, Germany, funded by the DFG project “Algorithms for Generating Quasi-Regular Structures in Graphs”.

Publications

Also see Google Scholar, DBLP, arXiv, Scopus, and ResearchGate.

Book Chapters

  1. The Complexity of Arc Routing Problems. René van Bevern, Rolf Niedermeier, Manuel Sorge, Mathias Weller. In Ángel Corberán and Gilbert Laporte (eds.) Arc Routing: Problems, Methods, and Applications, SIAM, 2014. [chapter, book]

Invited Journal Articles

  1. Myhill-Nerode Methods for Hypergraphs. René van Bevern, Rodney G. Downey, Michael R. Fellows, Serge Gaspers, Frances A. Rosamond. Algorithmica (ISAAC'13 special issue), in press, 2015. [paper, abstract, preprint]
  2. Towards Optimal and Expressive Kernelization for d-Hitting Set. René van Bevern. Algorithmica (COCOON'12 special issue), 2014. [paper, abstract, preprint, source code].
  3. A New View on Rural Postman Based on Eulerian Extension and Matching. Manuel Sorge, René van Bevern, Rolf Niedermeier, and Mathias Weller. Journal of Discrete Algorithms (IWOCA'11 special issue), 2012. [paper, abstract, preprint].

Journal Articles

  1. Approximability and parameterized complexity of multicover by c-intervals. René van Bevern, Jiehua Chen, Falk Hüffner, Stefan Kratsch, Nimrod Talmon, Gerhard J. Woeginger. Information Processing Letters, 2015. [paper, abstract, preprint]
  2. On the Parameterized Complexity of Computing Balanced Partitions in Graphs. René van Bevern, Andreas Emil Feldmann, Manuel Sorge, Ondřej Suchý. Theory of Computing Systems, 2015. [paper, abstract, preprint]
  3. Network-Based Vertex Dissolution. René van Bevern, Robert Bredereck, Jiehua Chen, Vincent Froese, Rolf Niedermeier, Gerhard J. Woeginger. SIAM Journal on Discrete Mathematics, 2015. [paper, abstract, preprint]
  4. Interval Scheduling and Colorful Independent Sets. René van Bevern, Mathias Mnich, Rolf Niedermeier, and Mathias Weller. Journal of Scheduling, in press, 2014. [paper, abstract, preprint]
  5. Constant-factor approximations for Capacitated Arc Routing without triangle inequality. René van Bevern, Sepp Hartung, André Nichterlein, Manuel Sorge. Operations Research Letters, 2014. [paper, abstract, preprint]
  6. Approximation and Tidying—A Problem Kernel for s-Plex Cluster Vertex Deletion. René van Bevern, Hannes Moser, and Rolf Niedermeier. Algorithmica, 2012. [paper, abstract, preprint]
  7. Parameterized Algorithmics for Finding Connected Motifs in Biological Networks. Nadja Betzler, René van Bevern, Michael R. Fellows, Christian Komusiewicz, and Rolf Niedermeier. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2011. [paper, abstract, preprint, source code]

Conference Articles

  1. Approximation algorithms for mixed, windy, and capacitated arc routing problems. René van Bevern, Christian Komusiewicz, Manuel Sorge. Best paper at ATMOS'15, Patras, Greece. [abstract, manuscript]
  2. H-Index Manipulation by Merging Articles: Models, Theory, and Experiments. René van Bevern, Christian Komusiewicz, Rolf Niedermeier, Manuel Sorge, Toby Walsh. IJCAI'15, Buenos Aires, Argentina. [abstract, paper, preprint]
  3. Network-Based Dissolution. René van Bevern, Robert Bredereck, Jiehua Chen, Vincent Froese, Rolf Niedermeier, Gerhard J. Woeginger. MFCS'14, Budapest, Hungary. A journal version appeared in SIAM Journal on Discrete Mathematics. [paper, abstract, preprint]
  4. Star Partitions of Perfect Graphs. René van Bevern, Robert Bredereck, Laurent Bulteau, Jiehua Chen, Vincent Froese, Rolf Niedermeier, Gerhard J. Woeginger. At ICALP'14, Copenhagen, Denmark. A journal version is under review. [paper, abstract, preprint].
  5. Myhill-Nerode Methods for Hypergraphs. René van Bevern, Michael R. Fellows, Serge Gaspers, Frances A. Rosamond. At ISAAC'13, Hong Kong, China. A journal version appeared in the ISAAC'13 special issue of Algorithmica. [paper, abstract, preprint]
  6. On the parameterized complexity of graph bisections. René van Bevern, Andreas Emil Feldmann, Manuel Sorge, Ondřej Suchý. At WG'13, Lübeck, Germany. A journal version appeared in Theory of Computing Systems. [paper, abstract , preprint, slides]
  7. A Parameterized Complexity Analysis of Combinatorial Feature Selection Problems. Vincent Froese, René van Bevern, Rolf Niedermeier, Manuel Sorge. At MFCS'13, Klosterneuburg, Austria. Journal version with many new results under review. [paper, abstract, preprint]
  8. Parameterized Complexity of DAG Partitioning. René van Bevern, Robert Bredereck, Morgan Chopin, Sepp Hartung, Falk Hüffner, André Nichterlein, Ondřej Suchý At CIAC'13, Barcelona, Spain. Improved algorithms and experimental evaluations can be found in my Dissertation. [paper, abstract, preprint].
  9. Interval Scheduling and Colorful Independent Sets. René van Bevern, Mathias Mnich, Rolf Niedermeier, and Mathias Weller. At ISAAC'12, Teipei, Taiwan. A journal version appeared in Journal of Scheduling. [paper, abstract].
  10. Towards Optimal and Expressive Kernelization for d-Hitting Set. René van Bevern. At COCOON'12, Sydney, Australia. A journal version appeared in the COCOON'12 special issue of Algorithmica. [paper, abstract, slides] .
  11. Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs. René van Bevern, Sepp Hartung, Frank Kammer, Rolf Niedermeier, and Mathias Weller. At IPEC'11, Saarbrücken, Germany. [paper, abstract, preprint, slides]
  12. A New View on Rural Postman Based on Eulerian Extension and Matching. Manuel Sorge, René van Bevern, Rolf Niedermeier, and Mathias Weller. At IWOCA'11, Victoria, Canada. A journal version appeared in the IWOCA'11 special issue of Journal of Discrete Algorithms.
  13. From Few Components to an Eulerian Graph by Adding Arcs. Manuel Sorge, René van Bevern, Rolf Niedermeier, and Mathias Weller. At WG'11, Teplá Monastery, Czech Republic. [paper, abstract, preprint]
  14. Measuring Indifference: Unit Interval Vertex Deletion. René van Bevern, Christian Komusiewicz, Hannes Moser, and Rolf Niedermeier. At WG'10, Zarós, Greece. [paper, abstract, preprint, slides]
  15. Kernelization through Tidying—A case study based on s-Plex Cluster Vertex Deletion. René van Bevern, Hannes Moser, and Rolf Niedermeier. At LATIN'10, Oaxaca, Mexico. A journal version appeared in Algorithmica. [paper, abstract, slides]

Theses

  1. Fixed-Parameter Linear-Time Algorithms for NP-hard Graph and Hypergraph Problems Arising in Industrial Applications. René van Bevern. Dissertation, Institut für Softwaretechnik und Theoretische Informatik, Technische Universität Berlin, Germany, June 2014. [abstract, thesis, read online, slides]
  2. The Computational Hardness and Tractability of Restricted Seriation Problems on Inaccurate Data. René van Bevern. Diplomarbeit, Institut für Informatik, Friedrich-Schiller-Universität Jena, Germany, April 2010. [thesis, slides]
  3. Graph-based data clustering: a quadratic-vertex problem kernel for s-Plex Cluster Vertex Deletion. René van Bevern. Studienarbeit, Institut für Informatik, Friedrich-Schiller-Universität Jena, Germany, September 2009. [abstract, thesis, slides]

Manuscripts under review

  1. A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack. René van Bevern, Rolf Niedermeier, Ondřej Suchý. August 2015. [abstract, manuscript]
  2. Well-Formed Separator Sequences, with an Application to Hypergraph Drawing. René van Bevern, Iyad Kanj, Christian Komusiewicz, Rolf Niedermeier, Manuel Sorge. July 2015. [abstract, manuscript]
  3. Partitioning Perfect Graphs into Stars. René van Bevern, Robert Bredereck, Laurent Bulteau, Jiehua Chen, Vincent Froese, Rolf Niedermeier, Gerhard J. Woeginger. May 2015.
  4. Fixed-parameter algorithms for DAG Partitioning. René van Bevern, Robert Bredereck, Morgan Chopin, Sepp Hartung, Falk Hüffner, André Nichterlein, Ondřej Suchý. November 2014.
  5. Exploiting hidden structure in selecting features to distinguish vectors. Vincent Froese, René van Bevern, Rolf Niedermeier, Manuel Sorge. July 2014.

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