me on mount everest



Homepage of Tim Nonner

IBM Research - Zurich
Säumerstrasse 4
8803 Rüschlikon
tno@zurich(dot)ibm(one more dot)com
+41 44 724 8651

Tim studied mathematics at the universities of Stuttgart and Uppsala from 2000 to 2005. After some time in the IT-industry, he made his PhD at Albert Ludwigs University of Freiburg from 2007 to 2010. Then he started working at IBM Research - Zurich in July 2010 executing descriptive, predictive and prescriptive analytics projects.





Publications

PTAS for Densest k-Subgraph in Interval Graphs
Algorithmica 74(1): 528-539 (2016)

Capacitated Max-Batching with interval graph compatibilities
Theor. Comput. Sci. 613: 79-93 (2016)

Stochastic Travel Planning for Unreliable Public Transportation Systems
(with Adi Botea and Marco Laumanns) ERCIM News 98 (2014)

Shortest Path with Alternatives for Uniform Arrival Times: Algorithms and Experiments
(with Marco Laumanns) accepted to Proceedings of the 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'14)

The Bell is Ringing is Speed-Scaled Multiprocessor Scheduling
(with Gero Greiner and Alexander Souza) Theory of Computing Systems, Volume 54, Number 1 (January 2014)

An Efficient Polynomial-Time Approximation Scheme for the Joint Replenishment Problem
(with Maxim Sviridenko) accepted to Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization (IPCO'13)

Optimal Algorithms for Train Shunting and Relaxed List Update Problems
(with Alexander Souza) In Proceedings of the 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'12)

Polynomial-Time Approximation Schemes for Shortest Path with Alternatives
In Proceedings of the 20th Annual European Symposium on Algorithms (ESA'12) Thanks to my talk at ESA, i recently found out that there is a significant overlap with a paper from SODA from 2003. Therefore, i am currently doing a rewrite which takes this into account. Please write me an email if you are interested.

PTAS for Densest k-Subgraph in Interval Graphs
In Proceedings of the 12th Workshop on Algorithms and Data Structures (WADS'11)

Clique Clustering yields a PTAS for max-Coloring Interval Graphs
In Proceeding of the 38th International Conference on Automata, Languages and Programming (ICALP'11)

Capacitated Max-Batching with Interval Graph Compatibilities
In Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT'10)

SRPT is 1.86-Competitive for Completion Time Scheduling
(with Christine Chung and Alexander Souza) In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA'10)

The Bell is Ringing in Speed-Scaled Multiprocessor Scheduling
(with Gero Greiner and Alexander Souza) In Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'09)

Approximating the Joint Replenishment Problem with Deadlines
(with Alexander Souza) Discrete Mathematics, Algorithms and Applications (DMAA), World Scientific, Volume 1, Issue 2 (June 2009)

Latency Constrained Data Aggregation in Chain Networks Admits a PTAS
(with Alexander Souza) In Proceedings of the 5th International Conference on Algorithmic Aspects in Information and Management (AAIM'09)

A 5/3-Approximation Algorithm for Joint Replenishment with Deadlines
(with Alexander Souza) In Proceedings of the 3rd Annual Conference on Combinatorial Optimization and Applications (COCOA'09)

Distributed Approximation Algorithms for Finding 2-Edge-Connected Subgraphs
(with Sven Krumke, Peter Merz, and Katharina Gerhardt) In Proceedings of the 12th International Conference On Principles Of Distributed Systems (OPODIS'07)

Theses

Approximation in Batch and Multiprocessor Scheduling
PhD thesis, Albert Ludwigs University of Freiburg, 2010

Subwordproblems in compressed words
Diploma thesis (in german), University of Stuttgart, 2005, advisor: Markus Lohrey

Talks

Shortest path with alternatives for uniform arrival times: algorithms and experiments
MAPSP'15, La Roche-en-Ardenne, Belgium, June 11th 2015

pyschedule - a Python Package to Formulate and Solve Resource-Constrained Scheduling Problems
EURO'15, Glasgow, Scotland, July 13th 2015

Shortest Path with Alternatives for Uniform Arrival Times: Algorithms and Experiments
ATMOS'14, Wrocław, Poland, September 11th 2014

An Efficient Polynomial-Time Approximation Scheme for the Joint Replenishment Problem
IPCO'13, Valparaiso, Chile, May 14th 2013

Optimal Algorithms for Train Shunting and Relaxed List Update Problems
ATMOS'12, Ljubliana, Slovenia, September 13th 2012

Polynomial-Time Approximation Schemes for Shortest Path with Alternatives
ESA'12, Ljubliana, Slovenia, September 12th 2012

Polynomial-Time Approximation Schemes for Shortest Path with Alternatives
ISMP'12, Berlin, Germany, August 22nd 2012

Polynomial-Time Approximation Schemes for Shortest Path with Alternatives
DIMAP Seminar at University of Warwick, Coventry, UK, April 16th 2012

Introduction to IBM Research
DPG Fruehjahrstagung, Berlin, Germany, March 28th 2012

PTAS for Densest k-Subgraph in Interval Graphs
IP for Lunch Seminar, IBM T.J. Watson, United States, August 23rd 2011

PTAS for Densest k-Subgraph in Interval Graphs
WADS'11, New York City, United States, August 7th 2011

Clique Clustering yields a PTAS for Max-Coloring Interval Graphs
MAPSP'11, Nymburg, Czech Republic, June 22nd 2011

Approximation in Batch and Multiprocessor Scheduling
my defense talk at Albert Ludwigs University of Freiburg, December 3rd 2010

Geometric Max-Partitioning Problems
8th Swiss Joint OR Days, Fribourg, Switzerland, September 10th 2010

Capacitated max-Batching with Interval Graph Compatibilities
SWAT'10, Bergen, Norway, June 22nd 2010

Batch Scheduling with Interval Compatibilities
Research Seminar, IBM Research Zurich, Switzerland, April 27th 2010

SRPT is 1.86-Competitive for Completion Time Scheduling
SODA'10, Austin, United States, January 19th 2010

SRPT and Completion Time Scheduling
IP for Lunch Seminar, IBM T.J. Watson, United States, September 14th 2009

The Bell is Ringing in Speed-Scaled Multiprocessor Scheduling
SPAA'09, Calgary, Canada, August 11th 2009

The Bell is Ringing in Speed-\ADScaled Multiprocessor Scheduling
MAPSP'09, Rolduc, Netherlands, June 30th 2009

Latency Constrained Aggregation in Chain Networks Admits a PTAS
AAIM'09, San Francisco, United States, June 15th 2009

A 5/3-\ADApproximation Algorithm for Joint Replenishment with Deadlines
COCOA'09, Huangshan, China, June 10th 2009

Distributed Algorithms for Finding 2-Edge-Connected Subgraphs
OPODIS'07, Guadeloupe, France, December 7th 2007

More Matching Problems on Compressed Strings
Oberseminar Universit\E4t Stuttgart, June 1st 2005, the seminar talk about my diploma thesis, back in the days