René van Bevern

Рене ван Беверн

Novosibirsk State University and Sobolev Institute of Mathematics



About / О себе


René van Bevern <rvb@nsu.ru>,
Dr.rer.nat., senior researcher,
Department of Mathematics and Mechanics,
Novosibirsk State University,
Novosibirsk,
Russian Federation
Рене ван Беверн <rvb@nsu.ru>,
Dr.rer.nat., старший научный сотрудник,
Механико-математический факультет,
Новосибирский государственный университет,
Новосибирск,
Российская Федерация

Former institutions

2011–2015
Algorithms and Complexity Theory group, TU Berlin, Germany.
2010
Chair of Theoretical Informatics I / Complexity Theory, Institut für Informatik, Friedrich-Schiller-Universität Jena, Germany.

News


August 10th, 2016
Our paper H-index manipulation by merging articles: Models, theory, and experiments has been accepted to Artificial Intelligence.
July 25th, 2016
I will be in the program committee of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017), Heeze, The Netherlands.
July 25th, 2016
Our paper Twins in subdivision drawings of hypergraphs has been accepted to the 24th International Symposium on Graph Drawing and Network Visualization (GD'16), Athens, Greece.
July 24th, 2016
Our paper Finding secluded places of special interest in graphs has been accepted to the 11th International Symposium on Parameterized and Exact Computation (IPEC'16), Aarhus, Denmark.
June 9th, 2016
Our paper H-index manipulation by undoing merges has been accepted to the 22nd European Conference on Artificial Intelligence (ECAI'16), The Hague, Holland.
June 2nd, 2016
Our paper Precedence-constrained scheduling problems parameterized by partial order width has been accepted to the 9th International Conference on Discrete Optimization and Operations Research (DOOR'16), Vladivostok, Russian Federation.

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.
2016–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. Novosibirsk State University.
2016–present
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

WG 2017
Program committee member at the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017), Heeze, The Netherlands.
G2S2 2016
Organizing committee member at the International Conference and PhD-Master Summer School on Graphs and Groups, Spectra and Symmetries (G2S2), Novosibirsk, Russian Federation.
IJCAI 2016
Program committee member at the 25th International Joint Conference on Artificial Intelligence (IJCAI'16), New York, USA.

Teaching


Currently teaching in the international master program Applied Mathematics and Stochastics of the Department of Mathematics and Mechanics of Novosibirsk State University.
Randomized Algorithms
Novosibirsk State University (Spring 2016), TU Berlin (Summer 2014).
Fixed-Parameter Algorithms
Novosibirsk State University (Autumn 2015 and 2016).
Advanced Algorithmics
TU Berlin (Winter 2014/15).

Invited talks and lectures

May 26–28th, 2016
Invited talk at the 6th International Conference on Network Analysis (NET'16), Nizhny Novgorod, Russian Federation.
May 22–26th, 2016
Two invited lectures and seminar at the 2016 Summer School on Operational Research and Applications, Nizhny Novgorod, Russian Federation.

Software


metapreview.el
Preview Metapost figures while writing them in Emacs.
cis
A solver for the NP-hard Job Interval Selection and 2-Union Independent Set problems. See [BMNW15].
dagpart
A solver for the NP-hard DAG Partitioning problem arising in social network analysis. See [Bev14].
gram
Finds motifs in biological networks. See [BBF+11].
hindex
Tools for computing the articles to merge in order to maximize your H-index in Google Scholar. The zip file also contains anonymized example Google Scholar profiles. See [BKN+16]
hs-linkern
A linear-time data reduction preprocessor for the NP-hard d-Hitting Set problem. See [Bev14b].

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.

Invited journal and book contributions

[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.
[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.
[Bev14b]
René van Bevern. Towards optimal and expressive kernelization for d-hitting set. Algorithmica, 70(1):129–147, 2014. COCOON'12 special issue.
[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.

Journal articles

Upcoming

[BBB+xx]
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, 2016. In press.
[BNSxx]
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, 2016. In press.

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

Upcoming

[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. Springer, 2016. To appear.
[BFM+16]
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, Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. to appear.

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.
[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.
[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. Improved algorithms and experimental evaluations can be found in my Dissertation.

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.

Theses

[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.
[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.
[Bev09]
René van Bevern. Graph-based data clustering: a quadratic-vertex problem kernel for s-plex cluster vertex deletion, 2009. Undergraduate thesis.

Manuscripts waiting for publication

[BPxx]
René van Bevern and Artem V. Pyatkin. Routing open shop with unit processing times, few machines, and few locations. 2016.
[BFKxx]
René van Bevern, Vincent Froese, and Christian Komusiewicz. Parameterizing edge modification problems above lower bounds. 2016.
[BKK+xx]
René van Bevern, Iyad Kanj, Christian Komusiewicz, Rolf Niedermeier, and Manuel Sorge. Well-formed separator sequences, with an application to hypergraph drawing. 2015.
[BBC+xx]
René van Bevern, Robert Bredereck, Morgan Chopin, Sepp Hartung, Falk Hüffner, André Nichterlein, and Ondřej Suchý. Fixed-parameter algorithms for dag partitioning. 2014.

Last modified: Fri Sep 9 13:09:33 +07 2016