Publications of Tjark Vredeveld

Articles in Journals and Refereed Conference Proceedings:

• D. Recalde, C. Rutten, P. Schuurman, and T. Vredeveld
  Local search performance guarantees for restricted related parallel machine scheduling,
  Accepted for: LATIN 2010

• 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]

• 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, Berlin, Germany, 2008.
  Full version available as [Meteor Research Memorandum RM/08/006]

• S.O. Krumke, S. Saliba, T. Vredeveld, and S. Westphal
  Approximation algorithms for a vehicle routing problem. [pdf]
  Mathematical Methods of Operations Research 68: 333-359 (2008).

• Tobias Brueggemann, Johann L. Hurink, Tjark Vredeveld, and Gerhard 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: Fifth International Workshop, WAOA 2007, Lecture Notes in Computer Science 4927, pp. 41-55, Springer, Berlin, Germany, 2008.
  Also available as [Memorandum No. 1801, University of Twente, Dep. of Mathematical Sciences]

• Alexander Grigoriev, Joyce van Loon, Maxim Sviridenko, Marc Uetz, and Tjark 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, Berlin, Germany, 2007.

• Petra Schuurman and Tjark Vredeveld,
  Performance guarantees of local search for multiprocessor scheduling,
  Informs Journal on Computing 19(1): 52-63, 2007.
  A preliminary version appeared in Karen Aardal and Bert Gerards (eds.): Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science 2081, pp. 370-382, Springer, Berlin, Germany, 2001.
  Also available as METEOR Research Memorandum RM05055

• Nicole Megow, and Tjark Vredeveld,
  Approximation results for preemptive stochastic online scheduling
  In: Y. Azar and T. Erlebach (eds.), Algorithms - ESA 2006, LNCS 4168, pp.516--527, 2006
  Full version can be found as TU-Berlin Technical Report Report-008-2006.

• Nicole Megow, Marc Uetz, and Tjark Vredeveld,
  Models and algorithms for stochastic online scheduling.
  Mathematics of Operations Research 31(3): 513-525 (2006)
  A preliminary version appeared as:
• Nicole Megow, Marc Uetz, and Tjark Vredeveld,
  Stochastic Online Scheduling on Parallel Machines,
  In G. Persiano and R. Solis-Oba (eds.): Approximation and Online Algorithms: Second International Workshop, WAOA 2004, Lecture Notes in Computer Science 3351, pp.167-180, Springer, Berlin, Germany, 2005. Proceedings of the Second Workshop on Approximation and Online Algorithms (WAOA) 2004.
  Also available as METEOR Research Memorandum RM04040

• Stefan Heinz, Sven O. Krumke, Nicole Megow, Jörg Rambau, Andreas Tuchscherer, and Tjark Vredeveld,
  The Online Target Date Assignment Problem,
  In: T. Erlebach and G. Persiano (eds.), Approximation and Online Algorithms (WAOA 2005),  LNCS 3879, pp. 230-243, 2006.
  Also available as METEOR Research Memorandum RM05056

• Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Guido Schäfer, and Tjark Vredeveld,
  Average case and smoothed competitive analysis for the multi-level feedback algorithm.
  Mathematics of Operations Research 31(1): 85-108, 2006. [pdf]
  An extended abstract appeared in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 462-471, Cambridge, MA, 2003.
  

• Sandra Guitterez, Sven O. Krumke, Nicole Megow, and Tjark Vredeveld,
  How to Whack Moles,
  Theoretical Computer Science 361(2-3): 329-341, 2006.
  A preliminary version appeared as:
• Sven O. Krumke, Nicole Megow, and Tjark Vredeveld,
  How to Whack Moles, In Klaus Jansen and Roberto Solis-Oba (eds.): Proceedings of the First Workshop on Approximation and Online Algorithms (WAOA) 2003, Lecture Notes in Computer Science 2909, pp. 192-205, Springer, Berlin, Germany, 2004
  Also available as TU-Berlin Technical Report Report-023-2003.

• Cor Hurkens and Tjark Vredeveld,
  Local search for multiprocessor scheduling: how many moves does it take to a local optimum, [pdf]  [ps]
  Operations Research Letters 31: 137-141, 2003

• Tjark Vredeveld and Jan Karel Lenstra,
  On local search for the generalized graph coloring problem. [pdf]  [ps]
  Operations Research Letters 31: 28-34, 2003

• Arie de Bruin, Gerard Kindervater, Tjark Vredeveld, and Albert Wagelmans,
  Finding a feasible solution for a class of distributed problems with a single sum constraint using agents, [ps]
  Constraints 8: 209-219, 2003

• Tjark Vredeveld and Cor Hurkens,
  Experimental comparison of approximation algorithms for scheduling unrelated parallel machines, [pdf]
  Informs Journal on Computing 14: 175-189, 2002.
  [test instances]

• Petra Schuurman and Tjark Vredeveld,
  Performance guarantees of local search for multiprocessor scheduling,
  In K. Aardal and B. Gerards (eds.): Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science 2081, pp. 370-382, Springer, Berlin, Germany, 2001.

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
  Approximating preemptive stochastic scheduling
  Meteor Research Memorandum RM/09/054

• B. Hiller and T. Vredeveld
  Probabilistic alternatives for competitive analysis
  Meteor Research Memorandum RM/09/053

• T. Vredeveld
  Stochastic Online Scheduling
  Meteor Research Memorandum RM/09/052

• 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.

• A. Grigoriev, B. Hiller, S. Marban, and T. Vredeveld
  Dynamic pricing problems with price-sensitive customers, 2009.

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.