Patrick J. McGovern (1959) Professor of Management

Professor of Operations Research

Biography
| **Selected Publications**

"From linear programming relaxations to approximation algorithms: A tour d’horizon," forthcoming in* Surveys in Operations Research and Management Science.*

*Algorithms - ESA 2014*,* Proceedings of the 22nd Annual European Symposium on Algorithms. *A.S. Schulz, D. Wagner (eds.). Lecture Notes in Computer Science 8737, Springer, Berlin, 2014.

"Robust appointment scheduling," S. Mittal, A.S. Schulz, S. Stiller, in K. Jansen, J.D.P. Rolim, N.R. Devanur and C. Moore (eds.): Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014), Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, 2014, 356-370

"A general framework for designing approximation schemes for combinatorial optimization problems with many objectives combined into one," S. Mittal, A.S. Schulz.* Operations Research* 61 (2013) 386-397. (2013)

"An FPTAS for optimizing a class of low-rank functions over a polytope," S.Mittal,A.S.Schulz. *Mathematical Programming* 141 (2013), 103-120. (2013)

"Approximating the least core value and least core of cooperative games with supermodular costs," A.S. Schulz, N. Uhan. *Discrete Optimization* 10 (2013) 163-180. (2013)

"The Gomory-Chvátal closure of a non-rational polytope is a rational polytope," J. Dunkel, A.S. Schulz. *Mathematics of Operations Research* 38 (2013), 63-91. (2013)

"The price of anarchy of the proportional allocation mechanism revisited," J.R. Correa, A.S. Schulz, N.E. Stier Moses, in Y. Chen and N. Immorlica (eds.): *Web and Internet Economics, Proceedings of the 9th International WINE Conference*, Lecture Notes in Computer Science 8289 (2013), 109-120. (2013)

"The complexity of welfare maximization in congestion games," C.A. Meyers, A.S. Schulz. *Networks* 59 (2012), 252-260. (2012)

"Approximation algorithms and hardness results for the joint replenishment problem with constant demands," A.S. Schulz, C. Telha, in C. Demetrescu and M.M. Halldórsson (eds.): *Algorithms – ESA 2011, Proceedings of the 19th Annual European Symposium on Algorithms*, Lecture Notes in Computer Science 6942 (2011), 628-639.

"Integer-empty polytopes in the 0/1-cube with maximal Gomory-Chvátal rank," S. Pokutta, A.S. Schulz. *Operations Research Letters* 39 (2011), 457-460. (2011)

"Near-optimal solutions and large integrality gaps for almost all instances of single- machine precedence-constrained scheduling," A.S. Schulz, N.A. Uhan. *Mathematics of Operations Research* 36 (2011), 14-23. (2011)

On the membership problem for the 0,1/2-closure (2011)

"Minimizing the sum of weighted completion times in a concurrent open shop," M. Mastrolilli, M. Queyranne, A.S. Schulz, O. Svensson, N.A. Uhan.* Operations Research Letters* 38 (2010), 390-395. (2010)

"On the rank of cutting-plane proof systems," S. Pokutta, A.S. Schulz, in F. Eisenbrand and B. Shepherd (eds.): *Integer Programming and Combinatorial Optimization, Proceedings of the 14th International IPCO Conference*, Lecture Notes in Computer Science 6080 (2010), 450-463. (2010)

"On the Rank of Cutting-Plane Proof Systems," Pokutta, Sebastian, and Andreas Schulz, in F. Eisenbrand and F.B. Shepherd, eds: *Integer Programming and Combinatorial Optimization. *Lecture Notes in Computer Science 6080, 450-463. (2010)

"Sharing supermodular costs," A.S. Schulz, N. Uhan.* Operations Research* 58 (2010), 1051-1056. (2010)

“Integer Programming: Optimization and Evaluation Are Equivalent.” James B. Orlin, Abraham P. Punnen and Andreas S. Schulz. In *Proceedings of the 11th International Symposium on Algorithms and Data Structures*, edited by F. Dehne, M. Gavrilova, J.-R. Sack and C.D. Tóth, 519-529. Berlin, Germany: Springer Berlin Heidelberg, 2009.

"Coordination mechanisms for selfish scheduling," M. Immorlica, L. Li, V.S. Mirrokni, A.S. Schulz.* Theoretical Computer Science* 410 (2009), 1589-1598. (2009)

"Integer equal flows," C.A. Meyers, A.S. Schulz.* Operations Research Letters* 37 (2009), 245-249. (2009)

"On the relative complexity of 15 problems related to 0/1-integer programming," Chapter 19 in Cook, L. Lovász, and J. Vygen (eds.): *Research Trends in Combinatorial Optimization*, Springer, 2009, 399-428.

“On ε-optimization schemes and L-bit precision: alternative perspectives in combinatorial optimization.” Orlin, James B. Andreas S. Schulz and Sudipta Sengupta. *Discrete Optimization *Vol. 5, No. 2 (2008): 550-561. (2008)

"A general framework for designing approximation schemes for combinatorial optimization problems with many objectives combined into one," S. Mittal, A.S. Schulz, in A. Goel, K. Jansen, J.D.P. Rolim, and R. Rubinfeld (eds.): *Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, Proceedings of the 11th International Workshop (APPROX 2008)*, Lecture Notes in Computer Science 5171 (2008), 179-192.

"N.E. Stier Moses, A geometric approach to the price of anarchy in nonatomic congestion games," J.R. Correa, A.S. Schulz. *Games and Economic Behavior* 64 (2008), 457-469 (2008)

"On the complexity of pure-strategy Nash equilibria in congestion and local-effect games," J. Dunkel, A.S. Schulz. *Mathematics of Operations Research* 33 (2008), 851-868. (2008)

"Stochastic online scheduling revisited," A.S. Schulz, in B. Yang, D.-Z. Du, and C.A. Wang (eds.): *Combinatorial Optimization and Applications, Proceedings of the 2nd International Conference (COCOA 2008)*, Lecture Notes in Computer Science 5165 (2008), 448-457.

"Encouraging cooperation in sharing supermodular costs," A.S. Schulz, N.A. Uhan, in M. Charikar, K. Jansen, O. Reingold, and J.D.P. Rolim (eds.): *Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Proceedings of the 10th International Workshop on Approximation Algo- rithms for Combinatorial Optimization Problems (APPROX 2007)*, Lecture Notes in Computer Science 4627 (2007), 271-285.

Encouraging Cooperation in Sharing Supermodular Costs (2007)

"Fast, fair, and efficient flows in networks," J.R. Correa, A.S. Schulz, N.E. Stier Moses.* Operations Research* 55 (2007), 215-225. (2007)

"Approximation bounds for a general class of precedence constrained parallel machine scheduling problems," M. Queyranne, A.S. Schulz.* SIAM Journal on Computing* 35 (2006), 1241-1253. (2006)

"Efficiency and fairness of system-optimal routing with user constraints," A.S. Schulz, N.E. Stier Moses. *Networks* 48 (2006), 223-234. (2006)

"On the complexity of pure-strategy Nash equilibria in congestion and local-effect games," J. Dunkel, A.S. Schulz, in P. Spirakis, M. Mavronicolas, and S. Kontogiannis (eds.): *Internet and Network Economics, Proceedings of the 2nd International Workshop (WINE 2006)*, Lecture Notes in Computer Science 4286 (2006), 62-73.

"Coordination mechanisms for selfish scheduling," N. Immorlica, L. Li, V.S. Mirrokni, A.S. Schulz, in X. Deng and Y. Ye (eds.): *Internet and Network Economics, Proceedings of the 1st International Workshop (WINE 2005)*, Lecture Notes in Computer Science 3828 (2005), 55-69.

"On the inefficiency of equilibria in congestion games," J.R. Correa, A.S. Schulz, N.E. Stier Moses, in M. Jünger and V. Kaibel (eds.): *Integer Programming and Combinatorial Optimization, Proceedings of the 11th International IPCO Conference*, Lecture Notes in Computer Science 3509 (2005), 167-181. (2005)

"Single-machine scheduling with precedence constraints," J.R. Correa, A.S. Schulz.* Mathematics of Operations Research* 30 (2005), 1005-1021. (2005)

"System-optimal routing of traffic flows with user constraints in networks with congestion," O. Jahn, R.H. Möhring, A.S. Schulz, N.E. Stier Moses. *Operations Research* 53 (2005), 600-616. (2005)

"Approximate local search in combinatorial optimization," J.B. Orlin, A.P. Punnen, A.S. Schulz.* SIAM Journal on Computing* 33 (2004), 1201-1214. (2004)

"Approximate local search in combinatorial optimization," J.B. Orlin, A.P. Punnen, A.S. Schulz, in* Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), New Orleans, LA, *2004, 580-589.

"Computational complexity, fairness, and the price of anarchy of the maximum latency problem," J.R. Correa, A.S. Schulz, N.E. Stier Moses, in D. Bienstock and G. Nemhauser (eds.): *Integer Programming and Combinatorial Optimization, Proceedings of the 10th International IPCO Conference*, Lecture Notes in Computer Science 3064 (2004), 59-73. (2004)

*Models and Algorithms for Planning and Scheduling Problems*, P. Baptiste, J. Carlier, A. Munier, A.S. Schulz, eds. Annals of Operations Research, Volume 129, Issue 1-4, Kluwer, 2004.

"On-line scheduling to minimize average completion time revisited," N. Megow, A.S. Schulz. *Operations Research Letters* 32 (2004), 485-490. (2004)

"Scheduling to minimize average completion time revisited: Deterministic on-line algorithms," N. Megow, A.S. Schulz, in K. Jansen and R. Solis-Oba (eds.), *Proceedings of the 1st Workshop on Approximation and Online Algorithms (WAOA 2003)*, Lecture Notes in Computer Science 2909 (2004), 227-234. (2004)

"Selfish routing in capacitated networks," J.R. Correa, A.S. Schulz, N.E. Stier Moses. *Mathematics of Operations Research* 29 (2004), 961-976. (2004)

"Single machine scheduling with precedence constraints," J.R. Correa, A.S. Schulz, in D. Bienstock and G. Nemhauser (eds.): *Integer Programming and Combinatorial Optimization, Proceedings of the 10th International IPCO Conference*, Lecture Notes in Computer Science 3064 (2004), 283-297. (2004)

"Bounds on the Chva´tal rank of polytopes in the 0/1-cube," F. Eisenbrand, A.S. Schulz. *Combinatorica* 23 (2003), 245-261. (2003)

"On the performance of user equilibria in traffic networks," A.S. Schulz, N.E. Stier Moses, in* Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), Baltimore, MD*, 2003, 86-87.

"Solving project scheduling problems by minimum cut computations," R.H. Möhring, A.S. Schulz, F. Stork, M. Uetz. *Management Science* 49 (2003), 330-350. (2003)

"Integer Programming and Combinatorial Optimization,"* Lecture Notes in Computer Science* 2337, Springer: Berlin, 2002

*Integer Programming and Combinatorial Optimization (Proceedings of IPCO IX),* W.J. Cook, A.S. Schulz (eds.). Lecture Notes in Computer Science 2337, Springer, Berlin, 2002.

"Scheduling unrelated machines by randomized rounding," A.S. Schulz, M. Skutella. *SIAM Journal on Discrete Mathematics* 15 (2002), 450-469. (2002)

"Single machine scheduling with release dates," M.X. Goemans, M. Queyranne, A.S. Schulz, M. Skutella, Y. Wang. *SIAM Journal on Discrete Mathematics* 15 (2002), 165-192. (2002)

"The complexity of generic primal algorithms for solving general integer programs," A.S. Schulz, R. Weismantel. *Mathematics of Operations Research* 27 (2002), 681-692. (2002)

"The power of α-points in preemptive single machine scheduling," A.S. Schulz, M. Skutella.* Journal of Scheduling* 5 (2002), 121-133. (2002)

"Transitive packing: A unifying concept in combinatorial optimization," R. Müller, A.S. Schulz. *SIAM Journal on Optimization* 13 (2002), 335-367 (2002)

"On project scheduling with irregular starting time costs," R.H. Möhring, A.S. Schulz, F. Stork, M. Uetz. *Operations Research Letters* 28 (2001), 149-154. (2001)

"ε-optimization schemes and L-bit precision: Alternative perspectives in combinatorial optimization," J.B. Orlin, A.S. Schulz, S. Sengupta, in* Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC 2000), Portland, OR*, 2000, 565-572.

"Optimal routing of traffic flows with length restrictions in networks with congestion," O. Jahn, R.H. Möhring, A.S. Schulz, in K. Inderfurth et al. (eds.): *Operations Research Proceedings 1999*, Selected Papers of the Symposium on Operations Research, Magdeburg, Springer, 2000, 437-442.

"An oracle-polynomial time augmentation algorithm for integer programming," A.S. Schulz, R. Weismantel, in *Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’99), Baltimore, MD*, 1999, 967-968.

"Approximation in stochastic scheduling: The power of LP-based priority policies," R.H. Möhring, A.S. Schulz, M. Uetz. *Journal of the ACM* 46 (1999), 924-942. (1999)

"Bounds on the Chvátal rank of polytopes in the 0/1-cube," F. Eisenbrand, A.S. Schulz, in G. Cornuéjols, R.E. Burkard, and G.J. Woeginger (eds.): *Integer Programming and Combinatorial Optimization, Proceedings of the 7th International IPCO Conference*, Lecture Notes in Computer Science 1610 (1999), 137-150. (1999)

"Exact algorithms for the minimum-cost embeddings of reliable virtual private networks into telecommunication networks," R.H. Möhring, M. Oellrich, A.S. Schulz, in P. Kall and H.-J. Lüthi (eds.): *Operations Research Proceedings 1998*, Selected Papers of the International Conference on Operations Research, Zurich, Springer, 1999, 573-582.

"On the Chva´tal rank of polytopes in the 0/1 cube," A. Bockmayr, F. Eisenbrand, M. Hartmann, A.S. Schulz. *Discrete Applied Mathematics* 98 (1999), 21-27. (1999)

"Resource-constrained project scheduling: Computing lower bounds by solving minimum cut problems," R.H. Möhring, A.S. Schulz, F. Stork, M. Uetz, in J. NešetÅ™il (ed.): *Algorithms – ESA ’99, Proceedings of the 7th Annual European Symposium on Algorithms*, Lecture Notes in Computer Science 1643 (1999), 139-150. (1999)

"Stochastic machine scheduling: Performance guarantees for LP-based priority policies," R.H. Möhring, A.S. Schulz, M. Uetz, in D. Hochbaum, K. Jansen, J.D.P. Rolim, and A. Sinclair (eds.): *Randomization, Approximation, and Combinatorial Optimization: Algorithms and Techniques, Proceedings of the 3rd International Workshop on Randomization and Approximation Techniques in Computer Science, and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (RANDOM-APPROX ’99)*, Lecture Notes in Computer Science 1671 (1999), 144-155. (1999)

"Approximation bounds for a general class of precedence constrained parallel machine scheduling problems," A. Munier, M. Queyranne, A.S. Schulz, in R. Bixby, E.A. Boyd, and R.Z. Rios Mercado (eds.):* Integer Programming and Combinatorial Optimization, Proceedings of the 6th International IPCO Conference,* Lecture Notes in Computer Science 1412 (1998), 367-382. (1998)

"Base polytopes of series-parallel posets: Linear description and optimization," R. Schrader, A.S. Schulz, G. Wambach. *Mathematical Programming* 82 (1998), 159-173. (1998)

"Improved bounds on relaxations of a parallel machine scheduling problem," C.A. Phillips, A.S. Schulz, D.B. Shmoys, C. Stein, J. Wein. *Journal of Combinatorial Optimization* 1 (1998), 413-426. (1998)

“Local Search in Combinatorial Optimization,” edited by E. Aarts and J.K. Lenstra. A.S. Schulz, OPTIMA 59 (1998), 13-14. (1998)

"Switchbox routing in VLSI design: Closing the complexity gap," S. Hartmann, M.W. Schäffter, A.S. Schulz. *Theoretical Computer Science* 203 (1998), 31-49. (1998)

"Approximation Algorithms," A.S. Schulz, D.B. Shmoys, D.P. Williamson, in* Proceedings of the National Academy of Sciences* 94 (1997), 12734-12735. (1997)

"Facets of the generalized permutahedron of a poset," A. von Arnim, A.S. Schulz. *Discrete Applied Mathematics* 72 (1997), 179-192. (1997)

"Random-based scheduling: New approximations and LP lower bounds," A.S. Schulz, M. Skutella, in J.D.P. Rolim (ed.): *Randomization and Approximation Techniques in Computer Science, Proceedings of the International Workshop RANDOM ’97*, Lecture Notes in Computer Science 1269 (1997), 119-133. (1997)

"Scheduling to minimize average completion time: Off-line and on-line approximation algorithms," *Mathematics of Operations Research* 22 (1997), 513-544. (1997)

"Scheduling-LPs bear probabilities: Randomized approximations for min-sum criteria," A.S. Schulz, M. Skutella, in R.E. Burkard and G.J. Woeginger (eds.): *Algorithms – ESA ’97, Proceedings of the 5th Annual European Symposium on Algorithms*, Lecture Notes in Computer Science 1284 (1997), 416-429. (1997)

"Switchbox routing in VLSI design: Closing the complexity gap," S. Hartmann, M.W. Schäffter, A.S. Schulz, in F. d’Amore, P.G. Franciosa, and A. Marchetti-Spaccamela (eds.): *Graph-Theoretic Concepts in Computer Science, Proceedings of the 22nd International Workshop (WG ’96)*, Lecture Notes in Computer Science 1197 (1997), 196-210. (1997)

"Improved scheduling algorithms for minsum criteria," C.A. Phillips, A.S. Schulz, D.B. Shmoys, C. Stein, J. Wein, in F. Meyer auf der Heide and B. Monien (eds.): *Automata, Languages and Programming, Proceedings of the 23rd ICALP,* Lecture Notes in Computer Science 1099 (1996), 646-657 (1996)

"Scheduling jobs with communication delays: Using infeasible solutions for approximation," R.H. Möhring, M.W. Schäffter, A.S. Schulz, in J. Diaz and M. Serna (eds.): *Algorithms – ESA ’96, Proceedings of the 4th Annual European Symposium on Algorithms*, Lecture Notes in Computer Science 1136 (1996), 76- 90. (1996)

"Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds," A.S. Schulz, in W.H. Cunningham, S.T. McCormick, and M. Queyranne (eds.): *Integer Programming and Combinatorial Optimization, Proceedings of the 5th International IPCO Conference,* Lecture Notes in Computer Science 1084 (1996), 301-315. (1996)

"Transitive packing," R. Müller, A.S. Schul, in W.H. Cunningham, S.T. McCormick, and M. Queyranne (eds.): *Integer Programming and Combinatorial Optimization, Proceedings of the 5th International IPCO Conference,* Lecture Notes in Computer Science 1084 (1996), 430-444. (1996)

"0/1-integer programming: Optimization and augmentation are equivalent," A.S. Schulz, R. Weismantel, G.M. Ziegler, in P. Spirakis (ed.): *Algorithms – ESA ’95, Proceedings of the 3rd Annual European Symposium on Algorithms*, Lecture Notes in Computer Science 979 (1995), 473-483. (1995)

"Scheduling unit jobs with compatible release dates on parallel machines with nonstationary speeds," M. Queyranne, A.S. Schulz, in E. Balas and J. Clausen (eds.): *Integer Programming and Combinatorial Optimization, Proceedings of the 4th International IPCO Conference*, Lecture Notes in Computer Science 920 (1995), 307-320. (1995)

"The interval order polytope of a digraph," R. Müller, A.S. Schulz, in E. Balas and J. Clausen (eds.): *Integer Programming and Combinatorial Optimization, Proceedings of the 4th International IPCO Conference*, Lecture Notes in Computer Science 920 (1995), 50-64. (1995)

"The permutahedron of series-parallel posets," A.S. Schulz. *Discrete Applied Mathematics* 57 (1995), 85-90. (1995)

**Research Center(s)**

**General Expertise**

Algorithms; Algorithms; Applied math; Applied mathematics; Auctions; Combinatorial optimization; Computational complexity; Computational economics; Europe; Facility location; Facility location; Germany; Healthcare operations management; Heuristics; Hospital operations management; Integer programming; Inventory; Inventory; Logistics; Logistics; Mathematical programming; Mathematical programming; Mathematical programming; Network optimization; Operations research; Optimization; Optimization; Optimization; Project management; Project management; Robust optimization; Stochastic modeling; Telecommunications; Telecommunications; Transportation; Vehicle routing; Vehicle routing