Mittagsseminar

• A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One.
  Shashi Mittal, August 14, 2008.
  Source: S. Mittal & A.S. Schulz, A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One, APPROX 2008.
  
  
• Approximate String Matching.
  Claudio Telha, May 5, 2008.
  Source: M. Kiwi, G. Navarro & C. Telha, On-line Approximate String Matching with Bounded Errors, CPM 2008.
  
  
• All Schedules are Almost Optimal, Almost Surely.
  Nelson Uhan, April 28, 2008.
  Source: A.S. Schulz & N. Uhan, Scheduling Meets Random Graphs: A Probabilistic Analysis of Precedence-Constrained Scheduling, Manuscript, April 2008.
  
  
• One of Three Fundamental, Polynomial-Time Solvable Combinatorial Optimization Problems: The Min-Cut Problem and its Relatives.
  Maurice Queyranne, April 23, 2008.
  Source: J.C. Picard & M. Queyranne, Selected Applications of Minimum Cuts in Networks, Information Systems and Operational Research 20 (1982), 394-422.
  
  
• (Acyclic) Job Shops are Hard to Approximate.
  Ola Svensson, April 14, 2008.
  Source: M. Mastrolilli & O. Svensson, (Acyclic) Job Shops are Hard to Approximate, Manuscript, April 2008.
  
  
• 1-Centers, Constrained Maximum Flows, and Submodular Functions.
  Andreas S. Schulz, April 7, 2008.
  Source: E.M. Craparo, J.P. How & E. Modiano, Optimization of Mobile Backbone Networks: Improved Algorithms and Approximation, Manuscript, March 2008.
  
  
• Small Chvatal Rank.
  Rekha Thomas, August 17, 2007.
  Source: T. Bogart & R. Thomas, Small Chvatal Rank, Manuscript, July 2007.
  
  
• Encouraging Cooperation in Sharing Supermodular Costs.
  Nelson Uhan, July 6, 2007.
  Source: A.S. Schulz & N. Uhan, Encouraging Cooperation in Sharing Supermodular Costs, APPROX 2007.
  
  
• (In)approximability Results for Precedence-Constrained Scheduling, Sparsest Cut and Optimal Linear Arrangement.
  Ola Svensson, July 5, 2007.
  Source: C. Ambühl, M. Mastrolilli, N. Mutsanas & O. Svensson, Scheduling with Precedence Constraints of Low Fractional Dimension, IPCO 2007; C. Ambühl, M. Mastrolilli and O. Svensson, Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling, FOCS 2007.
  
  
• Single Machine Precedence Constrained Scheduling is a Special Case of Vertex Cover.
  Christoph Ambühl, July 5, 2007.
  Source: C. Ambühl & M. Mastrolilli, Single Machine Precedence Constrained Scheduling is a Vertex Cover Problem, ESA 2006.
  
  
• On the Complexity of Pure-Strategy Nash Equilibria in Congestion and Local-Effect Games.
  Juliane Dunkel, May 9, 2007.
  Source: J. Dunkel & A.S. Schulz, On the Complexity of Pure-Strategy Nash Equilibria in Congestion and Local-Effect Games, WINE 2006.
  
  
• Maximum (Weighted) Independent Sets and Matchings in Regular Graphs: Girth, Greed, and Correlation Decay.
  David Goldberg, April 12, 2007.
  Source: D. Gamarnik & D. Goldberg, Maximum (Weighted) Independent Sets and Matchings in Regular Graphs: Girth, Greed, and Correlation Decay. Manuscript.
  
  
• Drawpoint Scheduling in Block Cave Mining.
  Maurice Queyranne, April 6, 2007.
  Source: T. Diering, P. Malkin, S.T. McCormick, A. Parkinson, M. Queyranne & L.A. Wolsey, Drawpoint Scheduling in Block Cave Mining: In Search of a Formulation, Working Paper, 2007.
  
  
• Lift & Project Cuts vs. Gomory-Chvatal Cuts.
  Sebastian Pokutta, March 14, 2007.
  Source: E.A. Hirsch & A. Kojevnikov, Several Notes on the Power of Gomory-Chvatal Cuts, Annals of Pure and Applied Logic 141 (2006), 429-436.
  
  
• Stochastic Mixed-Integer Programs with First-Order Dominance Constraints.
  Frederike Neise, March 6, 2007.
  Source: R. Gollmer, F. Neise & R. Schultz, Stochastic Programs with First-Order Dominance Constraints Induced by Mixed-Integer Linear Recourse, Manuscript.
  
  
• Lift and Project.
  Sebastian Pokutta, February 20, 2007.
  Source: G. Cornuejols, Valid Inequalities for Mixed Integer Linear Programs, Mathematical Programming, to appear.
  
  
• Approximating Rational Objectives is as Easy as Approximating Linear Objectives.
  Jose Correa, February 13, 2007.
  Source: J.R. Correa, C.G. Fernandes & Y. Wakabayashi, Approximating Rational Objectives is as Easy as Approximating Linear Ones, STACS 2006.
  
  
• Eliciting Coordination with Rebates.
  Nicolas E. Stier Moses, February 12, 2007.
  Source: P. Maille & N.E. Stier Moses, Eliciting Coordination with Rebates, Working Paper, January 2007.
  
  
• News on Stochastic Online Scheduling: The Preemptive Case.
  Nicole Megow, January 26, 2007.
  Source: N. Megow & T. Vredeveld, Approximation in Preemptive Stochastic Online Scheduling, ESA 2006.
  
  
• On the Diameter of Polyhedra.
  Andreas S. Schulz, November 21, 2006.
  Source: G. Kalai & D.J. Kleitman, A Quasi-Polynomial Bound for the Diameter of Graphs of Polyhedra, Bulletin of the American Mathematical Society 26 (1992), 315-316; D. Naddef, The Hirsch Conjecture is True for (0,1)-Polytopes, Mathematical Programming 45 (1989), 109-110.
  
  
• The Impact of Pricing and Buy-Back Menus on Supply Chain Performance.
  Pranava Goundan, November 1, 2006.
  Source: A. Chan, P. Goundan & D. Simchi-Levi, The Impact of Pricing and Buy-Back Menus on Supply Chain Performance, Manuscript, 2006.
  
  
• On the Complexity of Two-Player Win-Lose Games.
  Paul Valiant, October 18, 2006.
  Source: T. Abbott, D. Kane & P. Valiant, On the Complexity of Two-Player Win-Lose Games, FOCS 2005.
  
  
• Strong Price of Anarchy.
  Juliane Dunkel, October 4, 2006.
  Source: N. Andelman, M. Feldman & Y. Mansour, Strong Price of Anarchy, SODA 2007.
  
  
• Toric Ideals and Integer Programming.
  Sebastian Pokutta, September 20, 2006.
  Source: M.Kreuzer & L. Robbiano, Computational Commutative Algebra I, 2000; R. Hemmecke & P. Malkin, Computing Generating Sets of Lattice Ideals, preprint; R.R. Thomas, Applications to Integer Programming, in: D.A. Cox & B. Sturmfels (eds.), Applications of Computational Algebraic Geometry, Amer. Math. Soc., Providence 1998, 119-142.
  
  
• The Stable Set Polytope of Quasi-Line Graphs, Part II.
  Gautier Stauffer, September 13, 2006.
  Source: F. Eisenbrand, G. Oriolo, G. Stauffer & P. Ventura, Circular Ones Matrices and the Stable Set Polytope of Quasi-Line Graphs, IPCO 2005.
  
  
• The Stable Set Polytope of Quasi-Line Graphs, Part I.
  Gautier Stauffer, September 7, 2006.
  Source: F. Eisenbrand, G. Oriolo, G. Stauffer & P. Ventura, Circular Ones Matrices and the Stable Set Polytope of Quasi-Line Graphs, IPCO 2005.
  
  
• An Update on the Generalized Assignment Problem.
  Pranava Goundan, August 31, 2006.
  Source: L. Fleischer, M.X. Goemans, V.S. Mirrokni & M. Sviridenko, Tight Approximation Algorithms for the Maximum General Assignment Problem, SODA 2006.
  
  
• On the Complexity of Pure-Strategy Nash Equilibria in Congestion and Local-Effect Games.
  Juliane Dunkel, July 28, 2006.
  Source: J. Dunkel, The Complexity of Pure-Strategy Nash Equilibria in Non-Cooperative Games, Diplomarbeit, Institut für Mathematik, Technische Universität Berlin, Germany, July 2005.
  
  
• The Network Interdiction Problem.
  Nelson Uhan, July 21, 2006.
  Source: R.K. Wood, Deterministic Network Interdiction, Mathematical and Computer Modelling 17 (1993), 1-18.
  
  
• Supply Contracts and Price of Anarchy.
  Pranava Goundan, July 17, 2006.
  Source: L.M.A. Chan, P.R. Goundan & D. Simchi-Levi, The Impact of Pricing and Buy-back Menus on Supply Chain Performance, Working Paper, 2006.
  
  
• Schedule Planning Games.
  Nelson Uhan, May 3, 2005.
  Source: A.S. Schulz & N. Uhan, The Least Core Value of Schedule Planning Games, Working Paper.
  
  
• Approximation Algorithms for Generalized Assignment Problems.
  Andreas S. Schulz, April 27, 2005.
  Source: L. Fleischer, M.X. Goemans, V.S. Mirrokni & M. Sviridenko, (Almost) Tight Approximation Algorithms for Maximum General Assignment Problems, Manuscript, 2005
  
  
• Facility Location Games.
  Pranava Goundan, March 30, 2005.
  Source: M.X. Goemans & M. Skutella, Cooperative Facility Location Games, Journal of Algorithms 50 (2004), 194-214.
  
  
• The 12-Color Theorem.
  Andreas S. Schulz, November 24, 2004.
  Source: D. Barnette, Map Coloring, Polyhedra, and the Four-Color Problem, The Mathematical Association of America, 1983.
  
  
• A Polynomial-Time Local Search Algorithm for the Max-Cut Problem in Cubic Graphs.
  Juliane Dunkel, July 29, 2004.
  Source: S. Poljak, Integer Linear Programs and Local Search for Max-Cut, SIAM Journal on Computing 24 (1995), 822-839.
  
  
• The Constrained Minimum Spanning Tree Problem.
  Andreas S. Schulz, July 14, 2004.
  Source: M.X. Goemans & R. Ravi, The Constrained Minimum Spanning Tree Problem, SWAT 1996.
  
  
• The Precedence-Constrained Class Sequencing Problem.
  Nicolás E. Stier Moses, June 29, 2004.
  Source: J.R. Correa, S. Fiorini & N.E. Stier Moses, A Note on the Precedence-Constrained Class Sequencing Problem, Manuscript, May 2004.
  
  
• Sequencing Games.
  Nelson Uhan, June 15, 2004.
  Source: I. Curiel, G. Pederzoli & S. Tijs, Sequencing Games, European Journal of Operational Research 40 (1989), 344-351; I. Curiel, J. Potters, R. Prasad, S. Tijs & B. Veltman, Sequencing and Cooperation, Operations Research 42 (1994), 566-568.
  
  
• A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem.
  Juliane Dunkel, April 26, 2004.
  Source: Kamal Jain, A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem, Combinatorica 21 (2001), 39-60.
  
  
• Scheduling with <= Constraints.
  Carol Meyers, April 22, 2004.
  Source: B. Berger & L. Cowen, Scheduling with Concurrency-Based Constraints, Journal of Algorithms 18 (1995), 98-123.
  
  
• Greedy Algorithms for Maximizing Submodular Functions over Independence Systems: New Results and Open Questions.
  Amr Farahat, March 29, 2004.
  Source: A. Farahat & C. Barnhart, Improved Bounds and a Generalized Greedy Algorithm for Maximizing Submodular Functions over Matroids,Working Paper, 2004.
  
  
• Separable Concave Optimization Approximately Equals Piecewise Linear Optimization.
  Dan Stratila, March 15, 2004.
  Source: T.L. Magnanti & D. Stratila, Separable Concave Optimization Approximately Equals Piecewise Linear Optimization, IPCO 2004.
  
  
• Polynomial-Time Algorithms for NP-hard Problems.
  Andreas S. Schulz, March 8, 2004.
  Source: J.B. Orlin, A.S. Schulz & S. Sengupta, "Epsilon"-Optimization Schemes and L-Bit Precision: Alternative Perspectives in Combinatorial Optimization, STOC 2000.
  
  
• Approximation Bounds for Parallel Machine Scheduling with Precedence Delays: Weighted Sum of Completion Times.
  Pranava Goundan, March 3, 2004.
  Source: A. Munier, M. Queyranne & A.S. Schulz, Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems, IPCO 1998.
  
  
• Approximation Bounds for Parallel Machine Scheduling with Precedence Delays: Makespan.
  Pranava Goundan, February 23, 2004.
  Source: A. Munier, M. Queyranne & A.S. Schulz, Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems, IPCO 1998.
  
  
• Stochastic Scheduling: The Deliberate Idleness Problem.
  Nelson Uhan, February 9, 2004.
  Source: M. Uetz, Stochastisches Scheduling: Algorithmen und Polyedrische Methoden, Diplomarbeit, Fachbereich Mathematik, Technische Universität Berlin, Germany, 1996; R.H. Möhring, F.J. Radermacher & G. Weiss, Stochastic Scheduling Problems I: General Strategies. ZOR - Zeitschrift für Operations Research 28 (1984), 193-260; R.H. Möhring, F.J. Radermacher & G. Weiss, Stochastic Scheduling Problems II: Set Strategies, ZOR - Zeitschrift für Operations Research 29 (1985), 65-104.
  
  
• Scheduling with Communication Delays.
  Andreas S. Schulz, December 2, 2003.
  Source: J.A. Hoogeveen, J.K. Lenstra & B. Veltman, Three, Four, Five, Six, or the Complexity of Scheduling with Communication Delays, Operations Research Letters 16 (1994), 129-137; A. Munier & J.-C. König, A Heuristic for a Scheduling Problem with Communication Delays, Operations Research 45 (1997), 145-147.
  
  
• Network Resource Allocation and a Congestion Game.
  Ramesh Johari, November 12, 2003.
  Source: R. Johari & J.N. Tsitsiklis, Network Resource Allocation and a Congestion Game, Manuscript, November 2003.
  
  
• The Integer Equal Flow Problem.
  Carol Meyers, November 4, 2003.
  Source: C. Meyers & A.S. Schulz, The Integer Equal Flow Problem, Manuscript, November 2003.
  
  
• The Parisi and Coppersmith-Sorkin Conjectures for the Random Assignment Problem.
  Nelson Uhan, October 30, 2003.
  Source: C. Nair, B. Prabhakar & M. Sharma, Proofs of the Parisi and Coppersmith-Sorkin Conjectures for the Finite Random Assignment Problem, FOCS 2003.
  
  
• Approximation Algorithms for Scheduling Unrelated Parallel Machines.
  Pranava Goundan, October 7, 2003.
  Source: J.K. Lenstra, D.B. Shmoys & E. Tardos, Approximation Algorithms for Scheduling Unrelated Parallel Machines, Mathematical Programming 46 (1990), 259-271.
  
  
• Overlay Optimization.
  Carol Meyers, October 1, 2003.
  Source: A. Balakrishnan, T. Magnanti & P. Mirchandani, Heuristics, LPs, and Trees on Trees: Network Design Analyses, Operations Research 44 (1996), 478-496.
  
  
• Covering a Symmetric Poset by Symmetric (Anti)Chains.
  Samuel Fiorini, September 25, 2003.
  Source: T. Fleiner, Covering a Symmetric Poset by Symmetric Chains, Combinatorica 17 (1997), 339-344.
  
  
• Nash Equilibria in Competitive Societies with Applications to Facility Location, Traffic Routing and Auctions.
  Nicolas E. Stier Moses, September 12, 2003.
  Source: A. Vetta, Nash Equilibria in Competitive Societies with Applications to Facility Location, Traffic Routing and Auctions, FOCS 2002.
  
  
• An APTAS for Bin Packing.
  Jose R. Correa, September 5, 2003.
  Source: W. Fernandez de la Vega and G.S. Lueker: Bin Packing can be Solved within 1+epsilon in Linear Time, Combinatorica 1 (1981), 349-355.
  
  
• Approximation Results for the Pup Matching Problem.
  Carol Meyers, May 8, 2003.
  Source: C. Meyers & A.S. Schulz, Manuscript, April 2003.
  
  
• On a Theorem of Lucchesi and Younger.
  Samuel Fiorini, May 1, 2003.
  Source: C.L. Lucchesi & D.H. Younger, A Minimax Theorem for Directed Graphs, Journal of the London Mathematical Society, Series II, 17 (1978), 369-374; L. Lovasz, On Two Minimax Theorems in Graph Theory, Journal of Combinatorial Theory, Series B, 21 (1976), 96-103.
  
  
• A Note on the Complexity of Local Search Problems.
  Pranava Goundan, April 29, 2003.
  Source: S.T. Fischer, A Note on the Complexity of Local Search Problems, Information Processing Letters 53 (1995), 69-75.
  
  
• New Results on 3-Stage Clos Networks.
  Jose R. Correa, April 24, 2003.
  Source: D.Z. Du, B. Gao, F.K. Hwang & J.H. Kim, On Multirate Rearrangeable Clos Networks, SIAM Journal on Computing 28 (1998), 463-470.
  
  
• Performance Guarantees of Local Search for Multiprocessor Scheduling.
  Pranava Goundan, April 10, 2003.
  Source: P. Schuurman & T. Vredeveld, Performance Guarantees of Local Search for Multiprocessor Scheduling, IPCO 2001.
  
  
• On the Assembly-Line Scheduling Problem.
  Jose R. Correa, March 3, 2003.
  Source: J.R. Correa, M.X. Goemans & A.S. Schulz, Manuscript.
  
  
• Stable Traffic Equilibria.
  Nicolas E. Stier Moses, February 26, 2003.
  Source: Y. Nesterov, Stable Traffic Equilibria: Properties and Applications, Optimization and Engineering 1 (2000), 29-50; Y. Nesterov & A. de Palma, Stable Dynamics in Transportation Systems, CORE Discussion Paper 00/27.
  
  
• Approximate Local Optimization.
  Andreas S. Schulz, February 21, 2003.
  Source: J.B. Orlin, A.P. Punnen & A.S. Schulz, Manuscript, February 2003.
  
  
• The k-Splittable Flow Problem.
  Carol A. Meyers, February 20, 2003.
  Source: G. Baier, E. Köhler & M. Skutella, On the k-Splittable Flow Problem, ESA 2002.
  
  
• Analyzing the Complexity of Finding Good Neighborhood Functions for Local Search Algorithms.
  Pranava R. Goundan, February 13, 2003.
  Source: D.E. Armstrong & S.H. Jacobson, Analyzing the Complexity of Finding Good Neighborhood Functions for Local Search Algorithms, Manuscript, July 2002.
  
  
• The Combinatorial Automorphisms of the Linear Ordering Polytope.
  Samuel Fiorini, February 6, 2003.
  
  
• The Multiple Choice Polytope.
  Samuel Fiorini, January 23, 2003.
  Source: S. Fiorini, A Short Proof of a Theorem of Falmagne, Manuscript, January 2003.
  
  
• A New Maximum Flow Algorithm.
  Andreas S. Schulz, January 15, 2003.
  Source: S. Fujishige, A Maximum Flow Algorithm using MA Ordering, to appear in ORL.
  
  
• Single Machine Scheduling under Precedence Constraints.
  Jose R. Correa, January 13, 2003.
  Source: A.S. Schulz & J.R. Correa, Manuscript.
  
  
• On the Performance of User Equilibria in Traffic Networks.
  Nicolas E. Stier Moses, January 8, 2003.
  Source: A.S. Schulz & N.E. Stier Moses, On the Performance of User Equilibria in Traffic Networks, SODA 2003.
  
  
• A Greedy 2-Approximation Algorithm for the Winner Determination Problem in Combinatorial Auctions with Submodular Utilities.
  Andreas S. Schulz, May 2, 2002.
  Source: B. Lehmann, D. Lehmann & N. Nisan, Combinatorial Auctions with Decreasing Marginal Utilities, EC 2001.
  
  
• The Net Present Value Project Scheduling Problem.
  Nicolas E. Stier Moses, April 25, 2002.
  Source: A.S. Schulz & N.E. Stier Moses, Manuscript.
  
  
• Extended Neighborhoods.
  Dushyant Sharma, April 19, 2002.
  Source: D. Sharma, Ph.D. thesis, 2002.
  
  
• On the Approximability of Average Completion Time Scheduling under Precedence Constraints.
  Jose R. Correa, April 4, 2002.
  Source: G.J. Woeginger, On the Approximability of Average Completion Time Scheduling under Precedence Constraints, ICALP 2001, 887-897.
  
  
• Approximation Algorithms for the Quickest Flow Problem with Flow-Dependent Transit Times.
  Nicolas E. Stier Moses, April 1, 2002.
  Source: E. Köhler, K. Langkau & M. Skutella, Manuscript 2002.
  
  
• 0/1 Optimization and 0/1 Primal Separation are Equivalent.
  Andreas S. Schulz, March 19, 2002.
  Source: F. Eisenbrand, G. Rinaldi & P. Ventura, 0/1 Optimization and 0/1 Primal Separation are Equivalent, SODA 2002.
  
  
• Performance Analysis of On-line Algorithms in Machine Scheduling.
  Nicole Megow, March 14, 2002.
  Source: N. Megow, Performance Analysis of On-line Algorithms in Machine Scheduling, Diploma Thesis, 2002.
  
  
• Non-Oblivious Local Search.
  Dushyant Sharma, March 12, 2002.
  Source: S. Khanna, R. Motwani, M. Sudan & U. Vazirani, On Syntactic versus Computational Views of Approximability, SIAM Journal on Computing 28 (1998) 164-191.
  
  
• Resource-Constrained Scheduling and Clos Networks.
  Andreas S. Schulz, February 20, 2002.
  Source: M.R. Garey & R.L. Graham, Bounds for Multiprocessor Scheduling with Resource Constraints, SIAM Journal on Computing 4 (1975), 187-200.
  
  
• 3-Stage Clos Networks and the Chung-Ross Conjecture.
  Jose R. Correa, February 14, 2002.
  Source: S-P. Chung & K.W. Ross, On Nonblocking Multirate Interconnection Networks, SIAM Journal on Computing 20 (1991), 726-736; R. Melen & J.S. Turner, Nonblocking Multirate Networks, SIAM Journal on Computing 18 (1989), 301-313; S. Mneimneh & K-Y. Siu, Scheduling Unsplittable Flows Using Parallel Switches, Manuscript 2001.
  
  
• Flows Over Time with Load-Dependent Transit Times.
  Nicolas E. Stier Moses, February 7, 2002.
  Source: E. Köhler & M. Skutella, Flows Over Time with Load-Dependent Transit Times, SODA 2002, 174-183.
  
  
• Very Large Scale Neighborhood Search for Combinatorial Optimization Problems.
  Dushyant Sharma, January 31, 2002.
  Source: D. Sharma, Ph.D. thesis, 2002.
  
  
• Sidney Decompositions in Single Machine Scheduling.
  Jose R. Correa, October 11, 2001.
  Source: C. Chekuri & R. Motwani, Precedence Constrained Scheduling to Minimize Sum of Weighted Completion Times on a Single Machine, Discrete Applied Mathematics 98 (1999), 29-38; F.A. Chudak & D.S. Hochbaum, A Half-Integral Linear Programming Relaxation for Scheduling Precedence-Constrained Jobs on a Single Machine, Operations Research Letters 25 (1999), 199-204; J.R. Correa & A.S. Schulz, Manuscript.
  
  
• On the Complexity of Postoptimality Analysis for 0/1 Integer Programs.
  Andreas S. Schulz, September 27, 2001.
  Source: S. van Hoesel & A. Wagelmans, On the Complexity of Postoptimality Analysis of 0/1 Programs, Discrete Applied Mathematics 91 (1999), 251-263.
  
  
• Zadeh's Bad Examples for Min-Cost Flow Algorithms.
  Nicolas E. Stier Moses, September 20, 2001.
  Source: N. Zadeh, A Bad Network Problem for the Simplex Method and Other Minimum Cost Flow Algorithms, Mathematical Programming 5 (1973), 255-266.