Publications Marc Uetz

Lower Bounds for Smith's rule in Stochastic Machine Scheduling (pdf),
Caroline Jagtenberg, Uwe Schwiegelshohn, and Marc Uetz.
In: Approximation and Online Algorithms (WAOA 2010), K. Jansen and R. Solis-Oba (eds.), Lecture Notes in Computer Science 6534, pp. 142-153, 2011.

On the Complexity of the Highway Pricing Problem (pdf),
Alexander Grigoriev, Joyce van Loon, and Marc Uetz.
In: Theory and Practice of Computer Science (SOFSEM 2010), J. van Leeuwen, A. Muscholl, D. Peleg, J. Pokorný, B. Rumpe (eds.), Lecture Notes in Computer Science 5901, pp. 465-476, 2010.

Algorithmic Feature Generation for Microscale Topographies (pdf),
Kamiel Cornelissen, Hemant Unadkat, Roman Truckenmüller, Clemens van Bitterswijk, Gerhard Post, Jan de Boer, and Marc Uetz
Extended Abstract in: Proceedings of the 4th Annual Symposium of the Benelux Chapter of the IEEE Engineering in Medicine and Biology Society (EMBS), 2009.

Algorithms for Optimal Price Regulations (pdf),
Alexander Grigoriev, Joyce van Loon, and Marc Uetz.
In: Internet And Network Economics (WINE 2008). C. Papadimitriou and S. Zhang (eds.), Lecture Notes in Computer Science 5385, pp. 362-372, 2008.

Optimal Mechanisms for Single Machine Scheduling (pdf) ,
Birgit Heydenreich, Debasis Mishra, Rudolf Müller, and Marc Uetz.
In: Internet And Network Economics (WINE 2008). C. Papadimitriou and S. Zhang (eds.), Lecture Notes in Computer Science 5385, pp. 414-425, 2008.

Bundle Pricing with Comparable Items (pdf),
Alexander Grigoriev, Joyce van Loon, Maxim Sviridenko, Marc Uetz, and Tjark Vredeveld.
In: Algorithms (ESA 2007), L. Arge and E. Welzl (eds.), Lecture Notes in Computer Science 4698, pp. 475-486, 2007.

Optimal Bundle Pricing for Homogeneous Items,
Alexander Grigoriev, Joyce van Loon, Maxim Sviridenko, Marc Uetz, and Tjark Vredeveld.
Proc. 6th Cologne Twente Workshop on Graphs and Combinatorial Optimization (CTW 2007), 57-60.

On Revenue Equivalence in Truthful Mechanisms,
Birgit Heydenreich, Rudolf Müller, Marc Uetz, and Rakesh Vohra.
Proc. 6th Cologne Twente Workshop on Graphs and Combinatorial Optimization (CTW 2007), 69-72.

How to Sell a Graph: Guidelines for Graph Retailers (pdf),
Alexander Grigoriev, Joyce van Loon, René Sitters, and Marc Uetz. In: Graph-Theoretic Concepts in Computer Science (WG 2006), F. V. Fomin (ed.), Lecture Notes in Computer Science 4271, pp. 125-136, 2006. (There is also a journal version.)

LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times (pdf),
Alexander Grigoriev, Maxim Sviridenko, and Marc Uetz. In: Randomization, Approximation, and Combinatorial Optimization (APPROX 2006), Lecture Notes in Computer Science 4110, pp. 140-151, 2006. (There is also a journal version.)

Decentralization and Mechanism Design for Online Machine Scheduling (pdf),
Birgit Heydenreich, Rudolf Müller, and Marc Uetz. In: Algorithm Theory (SWAT 2006), L. Arge and R. Freivalds (eds.), Lecture Notes in Computer Science 4059, pp. 136-147, 2006.

Scheduling Parallel Jobs with Linear Speedup (pdf),
Alexander Grigoriev and Marc Uetz. In: Approximation and Online Algorithms (WAOA 2005), T. Erlebach and P. Persiano (eds.), Lecture Notes in Computer Science, 3879, pp. 203-215, 2006.

Fast Ejection Chain Algorithms for Vehicle Routing with Time Windows (pdf),
Herman Sontrop, Pieter van der Horn, and Marc Uetz. In: Hybrid Metaheuristics (HM 2005), M. J. Blesa, C. Blum, A. Roli, and M. Sampels (eds.), Lecture Notes in Computer Science 3636, pp. 78-89, 2005.

Unrelated Parallel Machine Scheduling with Resource Dependent Processing Times (pdf),
Alexander Grigoriev, Maxim Sviridenko, and Marc Uetz. Integer Programming and Combinatorial Optimization (IPCO 2005), M. Jünger and V. Kaibel (eds.), Lecture Notes in Computer Science 3509, pp. 182-195, 2005. (There is also a journal version.)

Stochastic Online Scheduling on Parallel Machines (pdf),
Nicole Megow, Marc Uetz, and Tjark Vredeveld. Approximation and Online Algorithms (WAOA 2004), G. Persiano and R. Solis-Oba (eds.), Lecture Notes in Computer Science 3351, pp. 167-180, 2005. (There is also a journal version.)

Pricing Network Edges to Cross a River (pdf),
Alexander Grigoriev , Stan van Hoesel, Anton van der Kraaij, Marc Uetz, and Mustapha Bouhtou. Approximation and Online Algorithms (WAOA 2004), G. Persiano and R. Solis-Oba (eds.), Lecture Notes in Computer Science 3351, pp. 140-153, 2005. (There is also a journal version.)

Enumeration of Circuits and Minimal Forbidden Sets,
Frederik Stork and Marc Uetz. Graphs and Combinatorial Optimization (CTW 2003), in Electronic Notes in Discrete Mathematics, 13, 2003, 108-111. (There is also a journal version.)

Approximation Algorithms for Stochastic Machine Scheduling with Precedence Constraints,
Martin Skutella and Marc Uetz. 8th International Workshop on Project Management and Scheduling (PMS 2002), Valencia, Spain, April 2002, pp. 238-241. (There is also a journal version.)

Scheduling Precedence-Constrained Jobs with Stochastic Processing Times on Parallel Machines,
Martin Skutella and Marc Uetz. 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), Washington, DC, January 2001, pp. 589-590. (There is also a journal version.)

Resource-Constrained Project Scheduling: From a Lagrangian Relaxation to Competitive Solutions,
Frederik Stork and Marc Uetz. 7th International Workshop on Project Management and Scheduling (PMS 2000), Osnabrück, Germany, April 2000, pp. 254-257. (There is also a journal version.)

Stochastic Machine Scheduling: Performance Guarantees for LP-based Priority Policies ,
Rolf H. Möhring, Andreas S. Schulz, and Marc Uetz. Randomization, Approximation, and Combinatorial Optimization (APPROX 1999), D. Hochbaum, K. Jansen, J. D. P. Rolim, and A. Sinclair (eds.), Lecture Notes in Computer Science 1671, Springer, Berlin, 1999, pp. 144-155. (There is also a journal version.)

Resource-Constrained Project Scheduling: Computing Lower Bounds by Solving Minimum Cut Problems,
Rolf H. Möhring, Andreas S. Schulz, Frederik Stork, and Marc Uetz. Algorithms (ESA 1999), J. Nesetril (ed.), Lecture Notes in Computer Science 1643, Springer, Berlin, 1999, pp. 139-150. (There is also a journal version.)

Resource-Constrained Project Scheduling with Time Windows: A Branching Scheme Based on Dynamic Release Dates,
Rolf H. Möhring, Frederik Stork, and Marc Uetz. 6th International Workshop on Project Management and Scheduling (PMS 1998), Istanbul, July 1998, pp. 98-101. (There is also a technical report.)

top

Publications in Journals

An algorithm-based topographical biomaterials library to instruct cell fate,
Hemant Unadkat, Marc Hulsman, Kamiel Cornelissen, Bernke Papenburg, Roman Truckenmüller, Gerhard Post, Marc Uetz, Marcel Reinders, Dimitrios Stamatialis, Clemens van Blitterswijk, Jan de Boer.
Proceedings of the National Academy of Sciences of the United States of America (PNAS), 108(40), October 2011, 16565-16570.
DOI 10.1073/pnas.1109861108

On the complexity of a bundle pricing problem,
Alexander Grigoriev, Joyce van Loon, and Marc Uetz.
4OR: A Quarterly Journal of Operations Research, 9(3), 2011, 255-260.
DOI 10.1007/s10288-011-0154-z

Mechanism Design for Decentralized Online Machine Scheduling (pdf) ,
Birgit Heydenreich, Rudolf Müller, and Marc Uetz.
Operations Research, 58(2), March-April 2010, 445-457.
DOI 10.1287/opre.1090.0732
An extended abstract with parts of this work appeared as Decentralization and Mechanism Design for Online Machine Scheduling at SWAT 2006.

Scheduling Jobs with Time-Resource Tradeoff via Nonlinear Programming (pdf) ,
Alexander Grigoriev and Marc Uetz.
Discrete Optimization, 6(4), November 2009, 414-419.
DOI 10.1016/j.disopt.2009.05.002
An extended abstract with parts of this work appeared as Scheduling Parallel Jobs with Linear Speedup at WAOA 2005.

Characterization of Revenue Equivalence (pdf),
Birgit Heydenreich, Rudolf Müller, Marc Uetz, and Rakesh Vohra.
Econometrica, 77(1), January 2009, 307-316.

Optimal Pricing of Capacitated Networks (pdf),
Alexander Grigoriev, Joyce van Loon, René Sitters, and Marc Uetz.
Networks, 53(1), January 2009, pp. 79-87.
DOI: 10.1002/net.20260
An extended abstract with parts of this work appeared as How to sell a graph: guidelines for graph retailers at WG 2006.

Optimal Bundle Pricing with Monotonicity Constraint (pdf),
Alexander Grigoriev, Joyce van Loon, Maxim Sviridenko, Marc Uetz, and Tjark Vredeveld.
Operations Research Letters, 36(5), September 2008, pp. 609-614.
DOI 10.1016/j.orl.2008.04.008
An extended abstract with parts of this work appeared as Bundle Pricing with Comparable Items at ESA 2007.

Games and Mechanism Design in Machine Scheduling - An Introduction (pdf),
Birgit Heydenreich, Rudolf Müller, and Marc Uetz.
Production and Operations Management, 16(4), July-August 2007, pp.437-454.

Machine Scheduling with Resource Dependent Processing Times (pdf),
Alexander Grigoriev, Maxim Sviridenko, and Marc Uetz.
Mathematical Programming, 110(1), June 2007, pp. 209-228.
DOI 10.1007/s10107-006-0059-3
Extended abstracts with parts of this work appeared as Unrelated Parallel Machine Scheduling with Resource Dependent Processing Times at IPCO 2005 and as LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times at APPROX 2006.

Pricing Bridges to Cross a River (pdf),
Mustapha Bouhtou, Alexander Grigoriev , Stan van Hoesel, Anton van der Kraaij, Frits Spieksma, and Marc Uetz.
Naval Research Logistics, 54(4), June 2007, pp. 411-420.
DOI 10.1002/nav.20216.
An extended abstract with parts of this work appeared as Pricing Network Edges to Cross a River at WAOA 2004.

Models and Algorithms for Stochastic Online Scheduling (pdf),
Nicole Megow, Marc Uetz, and Tjark Vredeveld.
Mathematics of Operations Research, 31(3), August 2006, pp. 513-525.
DOI 10.1287/moor.1060.0201.
An extended abstract with parts of this work appeared as Stochastic Online Scheduling on Parallel Machines at WAOA 2004.

Stochastic Machine Scheduling with Precedence Constraints (pdf),
Martin Skutella and Marc Uetz.
SIAM Journal on Computing 34(4), April 2005, pp. 788-802.
DOI: 10.1137/S0097539702415007.
An extended abstract with parts of this work appeared as Scheduling Precedence-Constrained Jobs with Stochastic Processing Times on Parallel Machines at SODA 2001.

On the Generation of Circuits and Minimal Forbidden Sets,
Frederik Stork and Marc Uetz.
Mathematical Programming 102(1), January 2005, pp. 185-203.
DOI: 10.1007/s10107-004-0512-0.
An extended abstract with parts of this work appeared as Enumeration of Circuits and Minimal Forbidden Sets at CTW 2003.

When Greediness Fails: Examples from Stochastic Scheduling,
Marc Uetz.
Operations Research Letters 31(6), November 2003, pp. 413-419.
DOI: 10.1016/S0167-6377(03)00047-6. See also the top 25 list for this journal.

Solving Project Scheduling Problems by Minimum Cut Computations,
Rolf H. Möhring, Andreas S. Schulz, and Frederik Stork, and Marc Uetz.
Management Science 49(3), March 2003, pp. 330-350.
DOI: 10.1287/mnsc.49.3.330.12737.
An extended abstract with parts of this work appeared as Resource-Constrained Project Scheduling: Computing Lower Bounds by Solving Minimum Cut Problems at ESA 1999.

On Project Scheduling with Irregular Starting Time Costs,
Rolf H. Möhring, Andreas S. Schulz, Frederik Stork, and Marc Uetz.
Operations Research Letters 28 (4), May 2001, pp. 149-154.
DOI: 10.1016/S0167-6377(01)00064-5.

Approximation in Stochastic Scheduling: The Power of LP-based Priority Policies,
Rolf H. Möhring, Andreas S. Schulz, and Marc Uetz.
Journal of the ACM 46(6), November 1999, pp. 924-942.
DOI: 10.1145/331524.331530.
An extended abstract with parts of this work appeared as Stochastic Machine Scheduling: Performance Guarantees for LP-based Priority Policies at APPROX 1999.

top

Book Chapters

Scheduling Scarce Resources in Chemical Engineering,
Rolf H. Möhring and Marc Uetz.
In: Mathematics - Key Technology for the Future: Joint Projects Between Universities and Industry, W. Jäger and H.-J. Krebs (Eds.), Springer-Verlag, Berlin, 2003. This project was funded by the German Ministry for Education and Research (bmb+f).

top

Theses

PhD Thesis (2001): Algorithms for Deterministic and Stochastic Scheduling, Marc Uetz, promotor: Rolf H. Möhring (Technische Universität Berlin, Germany), co-promotor: Jan Karel Lenstra (Technische Universiteit Eindhoven, The Netherlands). Awarded with the Tiburtius-Preis 2003 (Anerkennungspreis) by the Universities of Berlin. Published by Cuvillier Verlag Göttingen, Germany, 2002.

Diplomarbeit (1997, in German): Stochastisches Scheduling - Polyedrische Methoden und Algorithmen, Marc Uetz, supervisors: Rolf H. Möhring and Andreas S. Schulz, Technische Universität Berlin, Germany.

top