- share

# Publications

**Articles in Journals:**

- N. Bansal, T. Oosterwijk, T. Vredeveld and R. van der Zwaan. Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds.
*Algorithmica*. To appear, 2016. Preliminary version appeared in LATIN 2014. - N. Megow and T. Vredeveld. A tight 2-approximation for preemptive stochastic scheduling.
*Mathematics of Operations Research*, 39:1297–1310, 2014. Preliminary version appeared in ESA 2006. - T. Brunsch, H. Röglin, C. Rutten and T. Vredeveld. Smoothed performance guarantees for local search.
*Mathematical Programming*, 146:185–218, 2014. Preliminary version appeared in ESA 2011. - S. Marbán, R. van der Zwaan, A. Grigoriev, B. Hiller and T. Vredeveld. Dynamic pricing problems with elastic demand.
*Operations Research Letters*, 40:175–179, 2012. - C. Rutten, D. Recalde, P. Schuurman and T. Vredeveld. Performance guarantees of jump neighborhoods on restricted related parallel machines.
*Operations Research Letters*, 40:287–291, 2012. Preliminary version appeared in LATIN 2010. - B. Hiller and T. Vredeveld. Probabilistic alternatives for competitive analysis Computer Science – Research and Development, 27:189-196, 2012. Also available as Meteor Research Memorandum RM/09/053
- T. Vredeveld. Stochastic Online Scheduling Computer Science – Research and Development, 27:181-187, 2012. Also available as Meteor Research Memorandum RM/09/052
- T. Brueggemann, J.L. Hurink, T. Vredeveld and G.J. Woeginger. Exponential size neighborhoods for makespan minimization scheduling. Naval Research Logistics, 58:795-803, 2011. Preliminary version appeared in WAOA 2007.
- A. Grigoriev, J. van Loon, M. Sviridenko, M. Uetz, and T. Vredeveld. Optimal Bundle Pricing with Monotonicity Constraint.
*Operations Research Letters,*36: 609-614, 2008. Also available as [Meteor Research Memorandum RM/08/015]. Preliminary version appeared in ESA 2007. - S.O. Krumke, S. Saliba, T. Vredeveld, and S. Westphal. Approximation algorithms for a vehicle routing problem.
*Mathematical Methods of Operations Research,*68:333-359, 2008. [pdf] - P. Schuurman and T. Vredeveld. Performance guarantees of local search for multiprocessor scheduling.
*Informs Journal on Computing*, 19:52-63, 2007. Also available as METEOR Research Memorandum RM05055. A preliminary version appeared in IPCO 2001. - Nicole Megow, Marc Uetz, and Tjark Vredeveld, Models and algorithms for stochastic online scheduling.
*Mathematics of Operations Research,*31:513-525, 2006. A preliminary version appeared in WAOA 2004. - L. Becchetti, S. Leonardi, A. Marchetti-Spaccamela, G. Schäfer, and T. Vredeveld, Average case and smoothed competitive analysis for the multi-level feedback algorithm.
*Mathematics of Operations Research*, 31:85-108, 2006. [pdf] An extended abstract appeared in FOCS 2003. - Sandra Guitterez, Sven O. Krumke, Nicole Megow, and Tjark Vredeveld. How to Whack Moles.
*Theoretical Computer Science*, 361:329-341, 2006. A preliminary version appeared in WAOA 2003. - C.A.J. Hurkens and T. Vredeveld. Local search for multiprocessor scheduling: how many moves does it take to a local optimum.
*Operations Research Letters*, 31:137-141, 2003. [pdf] - T. Vredeveld and J.K. Lenstra, On local search for the generalized graph coloring problem.
*Operations Research Letters*, 31:28-34, 2003. [pdf] - A. de Bruin, G.A.P. Kindervater, T. Vredeveld, and AP.M. Wagelmans. Finding a feasible solution for a class of distributed problems with a single sum constraint using agents.
*Constraints*8:209-219, 2003. - T. Vredeveld and C.A.J. Hurkens. Experimental comparison of approximation algorithms for scheduling unrelated parallel machines.
*Informs Journal on Computing*, 14:175-189, 2002. [pdf] [test instances]

**Articles in Refereed Conference Proceedings:**

- V. Timmermans and T. Vredeveld. Scheduling with state-dependent machine speed. In L. Santina and M. Skutella (eds.):
*Approximation and Online Algorithms (WAOA)*, Lecture Notes in Computer Science 9499, pp. 196–208, Springer, Switzerland, 2015. - N. Bansal, T. Vredeveld, and R. van der Zwaan. Approximating vector scheduling: Almost matching upper and lower bounds. In
*LATIN 2014: Theoretical Informatics*, Lecture Notes in Computer Science 8392, pp. 47-59, Springer, Heidelberg, 2014. - N. Bansal, C. Rutten, S. van der Ster, T. Vredeveld, and R. van der Zwaan. Approximating real-time scheduling on identical machines. In
*LATIN 2014: Theoretical Informatics*, Lecture Notes in Computer Science 8392, pp. 550-561, Springer, Heidelberg, 2014. - S. Marbán, C. Rutten and T. Vredeveld. Learning in stochastic machine scheduling. In R. Solis-Oba and G. Persiano (eds.):
*Approximation and Online Algorithms: 9th International Workshop, WAOA 2011*, Lecture Notes in Computer Science 7164, pp. 21-34, Springer, Heidelberg, 2012. - T. Brunsch, H. Röglin, C. Rutten and T. Vredeveld. Smoothed performance guarantees for local search. In C. Demetrescu and M.M. Halldorsson (eds):
*Algorithms – ESA 2011*, Lecture Notes in Computer Science 6942, pp. 772-783, Springer, Heidelberg, 2011. - D. Recalde, C. Rutten, P. Schuurman and T. Vredeveld. Local search performance guarantees for restricted related parallel machine scheduling, In
*LATIN 2010: Theoretical Informatics*, Lecture Notes in Computer Science 6034, pp. 108-119, Springer, Heidelberg, 2010. - B. Hiller and T. Vredeveld Probabilistic analysis of Online Bin Coloring algorithms via Stochastic Comparison. In D. Halperin and K. Mehlhorn (eds.):
*Algorithms – ESA 2008*, Lecture Notes in Computer Science 5193, pp. 528-539, Springer, Heidelberg, 2008. Full version available as [Meteor Research Memorandum RM/08/006]. - T. Brueggemann, J.L. Hurink, T. Vredeveld and G.J. Woeginger. Very Large-Scale Neighborhoods with Performance Guarantees for Minimizing Makespan on Parallel Machines. In C. Kaklamanis and M. Skutella (eds.):
*Approximation and Online Algorithms: 5th International Workshop, WAOA 2007*, Lecture Notes in Computer Science 4927, pp. 41-55, Springer, Heidelberg, 2008. Also available as [Memorandum No. 1801, University of Twente, Dep. of Mathematical Sciences] - A. Grigoriev, J. van Loon, M. Sviridenko, M. Uetz and T. Vredeveld. Bundle Pricing with Comparable Items. In L. Arge, M. Hoffmann, and E. Welzl (eds.):
*Algorithms – ESA 2007*, Lecture Notes in Computer Science 4698, pp. 475-486, Springer, Heidelberg, 2007. - N. Megow, and T. Vredeveld. Approximation results for preemptive stochastic online scheduling. In Y. Azar and T. Erlebach (eds.),
*Algorithms – ESA 2006*, Lecture Notes in Computer Science 4168, pp. 516–527, 2006 Full version can be found as TU-Berlin Technical Report Report-008-2006. - S. Heinz, S.O. Krumke, N. Megow, J. Rambau, A. Tuchscherer, and T. Vredeveld. The Online Target Date Assignment Problem. In T. Erlebach and G. Persiano (eds.): Approximation and Online Algorithms,
*3rd International Workshop, WAOA 2005*, Lecture Notes in Computer Science 3879, pp. 230-243, 2006. Also available as METEOR Research Memorandum RM05056 - N. Megow, M. Uetz and T. Vredeveld. Stochastic Online Scheduling on Parallel Machines. In G. Persiano and R. Solis-Oba (eds.):
*Approximation and Online Algorithms: 2nd International Workshop, WAOA 2004*, Lecture Notes in Computer Science 3351, pp. 167-180, Springer, Heidelberg, 2005. - L. Becchetti, S. Leonardi, A. Marchetti-Spaccamela, G. Schäfer and T. Vredeveld. Average case and smoothed competitive analysis for the multi-level feedback algorithm. In
*Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS)*, pp. 462-471, Cambridge, MA, 2003. - S.O. Krumke, N. Megow and T. Vredeveld. How to Whack Moles. In K. Jansen and R. Solis-Oba (eds.):
*Approximation and Online Algorithms: 1st International Workshop, WAOA 2003*, Lecture Notes in Computer Science 2909, pp. 192-205, Springer, Heidelberg, 2004 Also available as TU-Berlin Technical Report Report-023-2003. - P. Schuurman and T. Vredeveld. Performance guarantees of local search for multiprocessor scheduling. In K. Aardal and B. Gerards (eds.):
*Integer Programming and Combinatorial Optimization (IPCO 2001)*, Lecture Notes in Computer Science 2081, pp. 370-382, Springer, Heidelberg, 2001.

**Chapters or part of collections:**

- T. Vredeveld. Vector Scheduling Problems. In Ming-Yang Kao (ed.): Encyclopedia of Algorithms. Springer, 2015.
- T. Vredeveld. Uncertainty in stochastic scheduling. In Y.N. Sotskov and F. Werner (eds.): Sequencing and Scheduling with Inaccurate Data, Chapter 2. Nova Science Publishers, New York, 2014.

**Publication as editor:**

- C. Stein, M. Uetz and T. Vredeveld (eds.).
*9th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP)*. Centre for Telematics and Information Technology, 2009.

**Theses:**

- Combinatorial Approximation Algorithms: Guaranteed Versus Experimental Performance [pdf]. PhD thesis, Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, The Netherlands, 2002.
- Parallelle algoritmen voor speciale gevallen van het traveling salesman problem. Master’s thesis (in Dutch), Department of Computer Science, Faculty of Economics, Erasmus University Rotterdam, Rotterdam The Netherlands, 1996.

**Technical reports and miscellaneous:**

- B. Hiller and T. Vredeveld Simple optimality proofs for Least Recently Used in the presence of locality of reference Meteor Research Memorandum RM/09/055
- N. Megow and T. Vredeveld Stochastic Online Scheduling with Precedence Constraints TU-Berlin Technical Report Report-029-2007.
- T. Harks, S. Heinz, M.E. Pfetsch, and T. Vredeveld Online Multicommodity Routing with Time Windows ZIB Report 07-22.
- L. Becchetti, A. Marchetti-Spaccamela, G. Schäfer and T. Vredeveld. On scheduling stochastic jobs to minimize the expected total flow time.