The Complexity of Congestion Games (2009)
Carol A. Meyers, Andreas S. Schulz
We investigate issues of complexity related to congestion games. In particular, we provide a full classification of complexity results for the problem of finding a minimum cost solution to a...
On the Relative Complexity of 15 Problems Related to 0/1-Integer Programming (2009)
Summary. An integral part of combinatorial optimization and computational complexity consists of establishing relationships between different problems or different versions of the same problem. In...
Sharing Supermodular Costs (2009)
Schulz, Andreas S., Uhan, Nelson A.
We apply ideas from cooperative game theory to study situations in which a set of agents face supermodular costs. These situations appear in a variety of scheduling contexts, as well as in some...
A GEOMETRIC APPROACH TO THE PRICE OF ANARCHY IN NONATOMIC CONGESTION GAMES (2008)
José R. Correa, Andreas S. Schulz, E. Stier-moses
Abstract. We present a short, geometric proof for the price-of-anarchy results that have recently been established in a series of papers on selfish routing in multicommodity flow networks and on...
ON THE INEFFICIENCY OF EQUILIBRIA IN CONGESTION GAMES — DRAFT; PLEASE DO NOT DISTRIBUTE — (2008)
José R. Correa, Andreas S. Schulz, E. Stier-moses
Abstract. We present a short geometric proof of the price of anarchy and price of stability results that have recently been established in a series of papers on selfish routing. This novel proof also...
Andreas S. Schulz, Martin Skutella
We consider the NP-hard preemptive single-machine scheduling problem to minimize the total weighted completion time subject to release dates. A natural extension of Smith’s ratio rule is to preempt...
Fast, Fair, and Efficient Flows in Networks (2008)
José R. Correa, Andreas S. Schulz
informs ® doi 10.1287/opre.1070.0383 © 2007 INFORMS We study the problem of minimizing the maximum latency of flows in networks with congestion. We show that this problem is NP-hard, even when all...
Andreas S. Schulz, Martin Skutella
We consider the NP-hard preemptive single-machine scheduling problem to minimize the total weighted completion time subject to release dates. A natural extension of Smith’s ratio rule is to preempt...
Andreas S. Schulz, Robert Weismantel
Primal methods constitute a common approach to solving (combinatorial) optimization problems. Starting from a given feasible solution, they successively produce new feasible solutions with point of...
© 2005 INFORMS Single-Machine Scheduling with Precedence Constraints (2008)
José R. Correa, Andreas S. Schulz
informs ® doi 10.1287/moor.1050.0158
Friedrich Eisenbrand, Andreas S. Schulz
Abstract. Gomory's and Chvatal's cutting-plane procedure proves recursively the validity of linear inequalities for the integer hull of a given polyhedron. The number of rounds needed to...
Leslie A. Hall, Andreas S. Schulz, David B. Shmoys, Joel Wein
In this paper we introduce two general techniques for the design and analysis of approximation algorithms for NP-hard scheduling problems in which the objective is to minimize the weighted sum of the...
The complexity of generic primal algorithms for solving general integer programs (2007)
Andreas S. Schulz, Robert Weismantel
Primal methods constitute a common approach to solving (combinatorial) optimization problems. Starting from a given feasible solution, they successively produce new feasible solutions with...
Michel X. Goemans, Maurice Queyranne, Andreas S. Schulz, Martin Skutella, Yaoguang Wang
We consider the scheduling problem of minimizing the average weighted completion time of n jobs with release dates on a single machine. We rst study two linear programming relaxations of the problem,...
On the Complexity of Pure-Strategy Nash Equilibria in Congestion and Local-Effect Games (2006)
Juliane Dunkel, Andreas S. Schulz
doi 10.1287/moor.1080.0322
On the inefficiency of equilibria in congestion games. Extended abstract (2005)
José R. Correa, Andreas S. Schulz
Abstract We present a short geometric proof for the price of anarchy results that have recently been established in a series of papers on selfish routing in multicommodity flow networks. This novel...
On the inefficiency of equilibria in congestion games. Extended abstract (2005)
José R. Correa, Andreas S. Schulz
Abstract We present a short geometric proof for the price of anarchy results that have recently been established in a series of papers on selfish routing in multicommodity flow networks. This novel...
New Old Algorithms for Stochastic Scheduling,” in (2005)
Abstract We consider the stochastic identical parallel machine scheduling problem and its online extension, when the objective is to minimize the expected total weighted completion time of a set of...
Olaf Jahn, Rolf H. Möhring, Andreas S. Schulz
informs ® doi 10.1287/opre.1040.0197
New Old Algorithms for Stochastic Scheduling (2005)
We consider the stochastic identical parallel machine scheduling problem and its online extension, when the objective is to minimize the expected total weighted completion time of a set of jobs that...
Computational Complexity, Fairness, and the Price of Anarchy of the Maximum Latency Problem (2004)
Correa, Jose R., Schulz, Andreas S., Stier Moses, Nicolas E.
We study the problem of minimizing the maximum latency of flows in networks with congestion. We show that this problem is NP-hard, even when all arc latency functions are linear and there is a single...
Computational Complexity, Fairness, and the Price of Anarchy of the Maximum Latency Problem (2004)
Correa, Jose R., Schulz, Andreas S., Stier Moses, Nicolas E.
We study the problem of minimizing the maximum latency of flows in networks with congestion. We show that this problem is NP-hard, even when all arc latency functions are linear and there is a single...
Scheduling to Minimize Average Completion Time Revisited: Deterministic On-line Algorithms (2004)
Megow, Nicole, Schulz, Andreas S.
We consider the scheduling problem of minimizing the average weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive...
Scheduling to Minimize Average Completion Time Revisited: Deterministic On-line Algorithms (2004)
Megow, Nicole, Schulz, Andreas S.
We consider the scheduling problem of minimizing the average weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive...
Computational complexity, fairness, and the price of anarchy of the maximum latency problem (2004)
Abstract. We study the problem of minimizing the maximum latency of flows in networks with congestion. We show that this problem is NP-hard, even when all arc latency functions are linear and there...
On-Line Scheduling to Minimize Average Completion Time Revisited (2004)
Nicole Megow, Andreas S. Schulz, I Mlm
We consider the scheduling problem of minimizing the average weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive...
Efficiency and fairness of systemoptimal routing with user constraints. Networks. Forthcoming (2004)
We study the route-guidance system proposed by
Approximate local search in combinatorial optimization (2004)
Andreas S. Schulz, James B. Orlin, James B. Orlin, Abraham P. Punnen, Abraham P. Punnen, ...
Short sections of text, not to exceed two paragraphs, may be quoted without
Selfish routing in capacitated networks (2004)
Jose R. Correa, Jose R. Correa, Andreas S. Schulz, Andreas S. Schulz
Abstract. According to Wardrop’s first principle, agents in a congested network choose their routes selfishly, a behavior that is captured by the Nash equilibrium of the underlying noncooperative...
On-line scheduling to minimize average completion time revisited (2004)
Nicole Megow, Nicole Megow, Andreas S. Schulz, Andreas S. Schulz
Short sections of text, not to exceed two paragraphs, may be quoted without
Computational complexity, fairness, and the price of anarchy of the maximum latency problem (2004)
Jose R. Correa, José R. Correa, Andreas S. Schulz, Andreas S. Schulz
Short sections of text, not to exceed two paragraphs, may be quoted without
Approximate local search in combinatorial optimization (2004)
Andreas S. Schulz, James B. Orlin, James B. Orlin, Abraham P. Punnen, Abraham P. Punnen, ...
Short sections of text, not to exceed two paragraphs, may be quoted without
Approximate Local Search in Combinatorial Optimization (2003)
Orlin, James B., Punnen, Abraham P., Schulz, Andreas S.
Local search algorithms for combinatorial optimization problems are in general of pseudopolynomial running time and polynomial-time algorithms are often not known for finding locally optimal...
Approximate Local Search in Combinatorial Optimization (2003)
Orlin, James B., Punnen, Abraham P., Schulz, Andreas S.
Local search algorithms for combinatorial optimization problems are in general of pseudopolynomial running time and polynomial-time algorithms are often not known for finding locally optimal...
Selfish Routing in Capacitated Networks (2003)
Correa, Jose R., Schulz, Andreas S., Stier Moses, Nicolas E.
According to Wardrop's first principle, agents in a congested network choose their routes selfishly, a behavior that is captured by the Nash equilibrium of the underlying noncooperative game. A Nash...
Selfish Routing in Capacitated Networks (2003)
Correa, Jose R., Schulz, Andreas S., Stier Moses, Nicolas E.
According to Wardrop's first principle, agents in a congested network choose their routes selfishly, a behavior that is captured by the Nash equilibrium of the underlying noncooperative game. A Nash...
Bounds on the Chvátal rank of Polytopes in the 0/1 Cube (2003)
Eisenbrand,Friedrich, Schulz,Andreas S.
Gomory's and Chvátal's cutting-plane procedure proves recursively the validity of linear inequalities for the integer hull of a given polyhedron. The number of rounds needed to obtain all valid...
Solving project scheduling problems by minimum cut computations (2003)
Mohring, Rolf H., Schulz, Andreas S., Stork, Frederik, Uetz, Marc
Bounds on the Chvátal rank of Polytopes in the 0/1 Cube (2003)
Eisenbrand, Friedrich, Schulz, Andreas S.
Gomory's and Chvátal's cutting-plane procedure proves recursively the validity of linear inequalities for the integer hull of a given polyhedron. The number of rounds needed to obtain all valid...
Selfish Routing in Capacitated Networks (2003)
Jose R. Correa, Andreas S. Schulz
According to Wardrop's first principle, agents in a congested network choose their routes selfishly, a behavior that is captured by the Nash equilibrium of the underlying noncooperative game. A...
MIT Sloan School of Management (2003)
Working Paper December, Nicolás Stier Moses, Nicolás Stier, Moses All Short, Andreas S. Schulz, Andreas S. Schulz, ...
According to Wardrop's first principle, drivers in a tra#c network choose their routes selfishly; that is, they travel on a shortest path under the prevailing tra#c conditions between their...
Solving Project Scheduling Problems by Minimum Cut (2002)
Moehring, Rolf, Uetz, Marc, Stork, Frederik, Schulz, Andreas S.
In project scheduling, a set of precedence-constrained jobs has to be scheduled so as to minimize a given objective. In resource-constrained project scheduling, the jobs additionally compete for...
Solving Project Scheduling Problems by Minimum Cut (2002)
Moehring, Rolf, Uetz, Marc, Stork, Frederik, Schulz, Andreas S.
In project scheduling, a set of precedence-constrained jobs has to be scheduled so as to minimize a given objective. In resource-constrained project scheduling, the jobs additionally compete for...
A Polyhedral Approach to Surface Reconstruction from Planar Contours. (2002)
Althaus, Ernst, Fink, Christian, Cook, William J., Schulz, Andreas S.
We investigate the problem of reconstruction a surface given its contours on parallel slices. We present a branch-and-cut algorithm which computes the surface with the minimal area. This surface is...
Scheduling unrelated machines by randomized rounding (2002)
Andreas S. Schulz, Martin Skutella
Abstract. We present a new class of randomized approximation algorithms for unrelated parallel machine scheduling problems with the average weighted completion time objective. The key idea is to...
Scheduling unrelated machines by randomized rounding (2002)
Andreas S. Schulz, Martin Skutella
Abstract. We present a new class of randomized approximation algorithms for unrelated parallel machine scheduling problems with the average weighted completion time objective. The key idea is to...
System-optimal routing of traffic flows with user constraints in networks with congestion (2002)
Olaf Jahn, Rolf H. Möhring, Andreas S. Schulz
The design of route guidance systems faces a well-known dilemma. The approach that theoretically yields the system-optimal traffic pattern may discriminate against some users in favor of others....
Transitive packing: A unifying concept in combinatorial optimization (2002)
Rudolf Müller, Andreas S. Schulz
This paper attempts to give a better understanding of the facial structure of previously separately investigated polyhedra. It introduces the notion of transitive packing and the transitive packing...
Rolf H. Mohring, Andreas S. Schulz
Abstract. The design of route guidance systems faces a well-known dilemma. The approach that theoretically yields the system-optimal traffic pattern may discriminate against some users in favor of...
On the performance of user equilibrium in traffic networks (2002)
Schulz, Andreas S., Stier Moses, Nicols E.
Title from cover.
A Note on Scheduling Problems with Irregular Starting Time Costs (2000)
Schulz, Andreas S., Möhring, Rolf H., Stork, Frederik, Uetz, Marc
In [9], Maniezzo and Mingozzi study a project scheduling problem with irregular starting time costs. Starting from the assumption that its computational complexity status is open, they develop a...
A Note on Scheduling Problems with Irregular Starting Time Costs (2000)
Schulz, Andreas S., Möhring, Rolf H., Stork, Frederik, Uetz, Marc
In [9], Maniezzo and Mingozzi study a project scheduling problem with irregular starting time costs. Starting from the assumption that its computational complexity status is open, they develop a...
Solving Project Scheduling Problems by Minimum Cut Computations (2000)
Rolf H. Möhring, Andreas S. Schulz, Frederik Stork, Marc Uetz
We present a Lagrangian relaxation based approach to compute both lower bounds and feasible solutions for a wide class of resource-constrained project scheduling problems. It is based on a wellknown...
Optimal routing of traffic flows with length restrictions in networks with congestion (2000)
Olaf Jahn, Rolf H. Möhring, Andreas S. Schulz
When traffic flows are routed through a road network it is desirable to minimize the total road usage. Since a route guidance system can only recommend paths to the drivers, special care has to be...
Solving Project Scheduling Problems by Minimum Cut Computations (2000)
Rolf H. Möhring, Andreas S. Schulz, Frederik Stork, Marc Uetz
In project scheduling, a set of precedence-constrained jobs has to be scheduled so as to minimize a given objective. In resource-constrained project scheduling, the jobs additionally compete for...
A note on scheduling problems with irregular starting time costs (2000)
A. Schulz, R. H. Mohring, F. Stork, M. Uetz, Rolf H. Mhring, Andreas S. Schulz, ...
In [9], Maniezzo and Mingozzi study a project scheduling problem with irregular starting time costs. Starting from the assumption that its computational complexity status is open, they develop a...
Single Machine Scheduling with Release Dates (1999)
Goemans, Michel X., Queyranne, Maurice, Schulz, Andreas S., Skutella, Martin, Wang, Yaoguang
We consider the scheduling problem of minimizing the average weighted completion time of n jobs with release dates on a single machine. We first study two linear programming relaxations of the...
Transitive Packing: A Unifying Concept in Combinatorial Optimization (1999)
Schulz, Andreas S., Müller, Rudolf
This paper attempts to give a better understanding of the facial structure of previously separately investigated polyhedra. It introduces the notion of transitive packing and the transitive packing...
Transitive Packing: A Unifying Concept in Combinatorial Optimization (1999)
Schulz, Andreas S., Müller, Rudolf
This paper attempts to give a better understanding of the facial structure of previously separately investigated polyhedra. It introduces the notion of transitive packing and the transitive packing...
Single Machine Scheduling with Release Dates (1999)
Goemans, Michel X., Queyranne, Maurice, Schulz, Andreas S., Skutella, Martin, Wang, Yaoguang
We consider the scheduling problem of minimizing the average weighted completion time of n jobs with release dates on a single machine. We first study two linear programming relaxations of the...
On the Chvátal rank of polytopes in the $0/1$ cube (1999)
Bockmayr, Alexander, Eisenbrand, Friedrich, Hartmann, Mark, Schulz, Andreas S.
Scheduling Unrelated Machines by Randomized Rounding (1999)
Andreas S. Schulz, Martin Skutella
In this paper, we provide a new class of randomized approximation algorithms for parallel machine scheduling problems. The most general model we consider is scheduling unrelated machines with release...
The Power of alpha-Points in Preemptive Single Machine Scheduling (1999)
Andreas S. Schulz, Martin Skutella, Tu Berlin
We consider the NP-hard preemptive single machine scheduling problem to minimize the total weighted completion time subject to release dates. A natural extension of Smith's ratio rule is to...
Single Machine Scheduling with Release Dates (1999)
Michel X. Goemans, Maurice Queyranne, Andreas S. Schulz, Martin Skutella, Yaoguang Wang
We consider the scheduling problem of minimizing the average weighted completion time of n jobs with release dates on a single machine. We rst study two linear programming relaxations of the problem,...
Extended Abstract, Rolf H. Möhring, Andreas S. Schulz, Marc Uetz
) Rolf H. Mohring 1 , Andreas S. Schulz 2 , and Marc Uetz 1 1 Technische Universitat Berlin, Fachbereich Mathematik Sekr. MA 6-1, Strae des 17. Juni 136, 10623 Berlin, Germany...
Rolf H. Möhring, Andreas S. Schulz, Frederik Stork, Marc Uetz
We present a novel approach to compute Lagrangian lower bounds on the objective function value of a wide class of resourceconstrained project scheduling problems. The basis is a polynomial-time...
On the Chvátal Rank of Polytopes in the 0-1 Cube (1999)
Alexander Bockmayr, Friedrich Eisenbrand, Mark Hartmann, Andreas S. Schulz
Given a polytope P , the Chvátal-Gomory procedure computes iteratively the integer hull P I of P. The Chvátal rank of P is the minimal number of iterations needed to obtain P I .It is always...
Approximation in stochastic scheduling: The power of LP-based priority policies (1999)
Rolf H. Möhring, Andreas S. Schulz
Abstract. We consider the problem to minimize the total weighted completion time of a set of jobs with individual release dates which have to be scheduled on identical parallel machines. Job...
Single machine scheduling with release dates (1999)
Michel X. Goemans, Maurice Queyranne, Andreas S. Schulz, Martin Skutella, Yaoguang Wang
Abstract. We consider the scheduling problem of minimizing the average weighted completion time of n jobs with release dates on a single machine. We first study two linear programming relaxations of...
Bounds on the chvátal rank of polytopes in the 0/1 cube (1999)
Friedrich Eisenbrand, Andreas S. Schulz
Gomory’s and Chvátal’s cutting-plane procedure proves recursively the validity of linear inequalities for the integer hull of a given polyhedron. The Chvátal rank of the polyhedron is the...
Single machine scheduling with release dates (1999)
Michel X. Goemans, Maurice Queyranne, Andreas S. Schulz, Martin Skutella, Yaoguang Wang
Abstract. We consider the scheduling problem of minimizing the average weighted completion time of n jobs with release dates on a single machine. We first study two linear programming relaxations of...
Base polytopes of seriesparallel posets: Linear description and optimization (1998)
Rainer Schrader, Andreas S. Schulz, Georg Wambach
We dene the base polytope B#P # g# of a partially ordered set P and a supermodular function g on the ideals of P as the convex hull of the incidence vectors of all linear extensions of P . This new...
Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem (1998)
Cynthia Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, Joel Wein
We consider the problem of scheduling n jobs with release dates on m identical parallel machines to minimize the average completion time of the jobs. We prove that the ratio of the average completion...
Resource Constrained Project Computing Lower Bounds By Solving Minimum Problems (1998)
Rolf H. Möhring, Rolf H. Mohring, Andreas S. Schulz, Andreas S. Schulz, Frederik Stork, Frederik Stork, ...
January 17, 1999 Abstract We propose a novel approach to compute bounds on the objective function value of a wide class of resource-constrained project scheduling problems. The basis is a...
Approximation in Stochastic Scheduling: The Power of LP-based Priority Policies (1998)
Rolf H. Möhring, Andreas S. Schulz, Marc Uetz
Devices]: Modes of Computation---Online computation General Terms: ALGORITHMS, THEORY Additional Key Words and Phrases: Stochastic scheduling, Approximation, Worst-case performance, Priority policy,...
Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem (1998)
Cynthia Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, Joel Wein
We consider the problem of scheduling n jobs with release dates on m identical parallel machines to minimize the average completion time of the jobs. We prove that the ratio of the average completion...
Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem (1998)
Cynthia Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, Joel Wein
We consider the problem of scheduling n jobs with release dates on m identical parallel machines to minimize the average completion time of the jobs. We prove that the ratio of the average completion...
Alix Munier, Maurice Queyranne, Andreas S. Schulz
this paper are as follows. 1. We clarify the relationship between two forms of List Scheduling Algorithms (LSAs): Graham 's non-idling LSAs and job-based LSAs. In particular, it is shown that...
Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem (1998)
Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, Joel Wein
We consider the problem of scheduling n jobs with release dates on m identical parallel machines to minimize the average completion time of the jobs. We prove that the ratio of the average completion...
Complexity of Primal Methods in Integer Programming (1998)
Andreas S. Schulz, Robert Weismantel
One common approach to solve optimization problems is the primal method. One starts with a feasible point and then successively produces new feasible solutions with better objective function values...
Approximation in Stochastic Scheduling: The Power of LP-Based Priority Rules (1998)
Rolf H. Möhring, Rolf H. M��hring, Andreas S. Schulz, Marc Uetz
We address the problem of minimizing the total weighted completion time in stochastic machine scheduling. A set of jobs has to be processed on identical parallel machines, job processing times are...
Improved bounds on relaxations of a parallel machine scheduling problem (1998)
Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein
Abstract. We consider the problem of scheduling n jobs with release dates on m identical parallel machines to minimize the average completion time of the jobs. We prove that the ratio of the average...
Improved bounds on relaxations of a parallel machine scheduling problem (1998)
Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, Joel Wein
Abstract We consider the problem of scheduling n jobs with release dates on m identical parallel machines to minimize the average completion time of the jobs. We prove that the ratio of the average...
Scheduling-LPs bear probabilities: Randomized approximations for min-sum criteria (1997)
Andreas S. Schulz, Martin Skutella
Abstract. In this paper, we provide a new class of randomized approximation algorithms for scheduling problems by directly interpreting solutions to so-called time-indexed LPs as probabilities. The...
Random-Based Scheduling - New Approximations and LP Lower Bounds (Extended Abstract) (1997)
Andreas S. Schulz, Andreas S. Schulz, Martin Skutella, Martin Skutella
) Andreas S. Schulz and Martin Skutella Technische Universitat Berlin, Fachbereich Mathematik, MA 6--1, Straße des 17. Juni 136, 10623 Berlin, Germany, E-mail fschulz,skutellag@math.tu-berlin.de...
Approximation Algorithms (1997)
Andreas S. Schulz, David B. Shmoys, David P. Williamson
Increasing global competition, rapidly changing markets, and greater consumer awareness have altered the way in which corporations do business. To become more efficient, many industries have sought...
Scheduling jobs with communication delays - using infeasible solutions for approximation (1996)
Rolf H. Mhring, Markus W. Schffter, Andreas S. Schulz
In the last few years, multi-processor scheduling with interprocessor communication delays has received increasing attention. This is due to the more realistic constraints in modeling parallel...
Improved scheduling algorithms for minsum criteria (1996)
Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, Joel Wein
Abstract. We consider the problem of finding near-optimal solutions for a variety of NP-hard scheduling problems for which the objective is to minimize the total weighted completion time. Recent work...
Improved Scheduling Algorithms for Minsum Criteria (1996)
Exte Nd Ed, Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, ...
) Soumen Chakrabarti ? Cynthia A. Phillips ?? Andreas S. Schulz ??? David B. Shmoys y Cliff Stein z Joel Wein x Abstract. We consider the problem of finding near-optimal solutions for a variety of...
Switchbox Routing in VLSI Design: Closing the Complexity Gap (1996)
Stephan Hartmann, Markus W. Schäffter, Stephan Hartmann, Markus W. Sch��ffter, Markus W. Sch��ffter, Andreas S. Schulz, ...
The design of integrated circuits has achieved a great deal of attention in the last decade. In the routing phase, there have survived two open layout problems which are important from both the...
Extended Abstract, A.S. Schulz, Andreas S. Schulz, M. Skutella, Martin Skutella
) ANDREAS S. SCHULZ MARTIN SKUTELLA No. 533/1996 Scheduling--LPs Bear Probabilities Randomized Approximations for Min--Sum Criteria (Extended Abstract) Andreas S. Schulz Martin Skutella November...
S. T. Mccormick, M. Queyranne, Lower Bounds, ...
. There has been recent success in using polyhedral formulations of scheduling problems not only to obtain good lower bounds in practice but also to develop provably good approximation algorithms....
Polytopes and Scheduling (1996)
Andreas S. Schulz, Doktor Der Naturwissenschaften, Berichter Prof, Berichter Prof, Dr. Martin Gr��tschel
refer to his results in this thesis; Marjan van den Akker, Leslie Hall, David Shmoys, and Joel Wein for discussions on various topics; Robert Weismantel and Günter M. Ziegler for their encouragement...
Base Polytopes of Series-Parallel Posets: Linear Description and Optimization (1996)
Rainer Schrader, Andreas S. Schulz, Georg Wambach
We define the base polytope B(P; g) of a partially ordered set P and a supermodular function g on the ideals of P as the convex hull of the incidence vectors of all linear extensions of P . This new...
Rudolf Müller, Andreas S. Schulz
This paper is intended to give a concise understanding of the facial structure of previously separately investigated polyhedra. It introduces the notion of transitive packing and the transitive...
Improved Scheduling Algorithms for Minsum Criteria (1996)
Extend Ed, Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, ...
) Soumen Chakrabarti ? Cynthia A. Phillips ?? Andreas S. Schulz ??? David B. Shmoys y Cliff Stein z Joel Wein x Abstract. We consider the problem of finding near-optimal solutions for a variety of...
Scheduling to Minimize Average Completion Time: Off-line and On-line Approximation Algorithms (1996)
Leslie A. Hall, Andreas S. Schulz, David B. Shmoys, Joel Wein
In this paper we introduce two general techniques for the design and analysis of approximation algorithms for NP-hard scheduling problems in which the objective is to minimize the weighted sum of the...
Improved Scheduling Algorithms for Minsum Criteria (Extended Abstract) (1996)
Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, Joel Wein
We consider the problem of finding near-optimal solutions for a variety of NP-hard scheduling problems for which the objective is to minimize the total weighted completion time. Recent work has led...
Scheduling to Minimize Average Completion Time: Off-line and On-line Approximation Algorithms (1996)
Dedicated To The, Leslie A. Hall, Andreas S. Schulz, David B. Shmoys, Joel Wein
In this paper we introduce two general techniques for the design and analysis of approximation algorithms for NP-hard scheduling problems in which the objective is to minimize the weighted sum of the...
The interval order polytope of a digraph (1995)
Rudolf Muller, Andreas S. Schulz
Abstract. We introduce the interval order polytope of a digraph D as the convex hull of interval order inducing arc subsets of D. Two general schemes for producing valid inequalities are presented....
Maurice Queyranne, Maurice Queyranne, Andreas S. Schulz, Andreas S. Schulz
We consider the problem of nonpreemptively scheduling a set of jobs with identical processing requirements (unit jobs) on parallel machines with nonstationary speeds. In addition to the case of...
0/1-Integer Programming: Optimization and Augmentation are Equivalent (1995)
Günter M. Ziegler, Andreas S. Schulz, Andreas S. Schulz, Robert Weismantel, Robert Weismantel, Gunter M. Ziegler
. For every family of sets F ` f0; 1g n the following problems are strongly polynomial time equivalent: given a feasible point x 0 2 F and a linear objective function c 2 ZZ n , ffl find a feasible...
The Interval Order Polytope of a Digraph (1995)
Rudolf M Uller, Rudolf Müller, Andreas S. Schulz, Andreas S. Schulz
We introduce the interval order polytope of a digraph D as the convex hull of interval order inducing arc subsets of D. Two general schemes for producing valid inequalities are presented. These...
0/1-Integer Programming: Optimization and Augmentation are Equivalent (1995)
Andreas S. Schulz, Robert Weismantel, Günter M. Ziegler
For every fixed set F ` f0; 1g n the following problems are strongly polynomial time equivalent: given a feasible point x 2 F and a linear objective function c 2 ZZ n , ffl find a feasible point x 2...
Facets of the Generalized Permutahedron of a Poset (1994)
Of A Poset, Annelie Von Arnim, Annelie Von Arnim, Andreas S. Schulz, Andreas S. Schulz
Given a poset P as a precedence relation on a set of jobs with processing time vector p, the generalized permutahedron perm(P; p) of P is defined as the convex hull of all job completion time vectors...
Polyhedral Approaches to Machine Scheduling (1994)
Maurice Queyranne, Maurice Queyranne, Andreas S. Schulz, Andreas S. Schulz
We provide a review and synthesis of polyhedral approaches to nonpreemptive machine scheduling problems. The choice of decision variables is the prime determinant of various formulations for such...
Polyhedral approaches to machine scheduling (1994)
Maurice Queyranne, Andreas S. Schulz
We provide a review and synthesis of polyhedral approaches to machine scheduling problems. The choice of decision variables is the prime determinant of various formulations for such problems....
Bounds on the Chvatal rank of polytopes in the 0/1-cube (1610)
Friedrich Eisenbrand, Andreas S. Schulz
Gomory's and Chvatal's cutting-plane procedure proves recursively the validity of linear inequalities for the integer hull of a given polyhedron. The Chvatal rank of the polyhedron is the...
Approximate Local Search in Combinatorial Optimization
Orlin, James B., Punnen, Abraham P., Schulz, Andreas S.
Local search algorithms for combinatorial optimization problems are in general of pseudopolynomial running time and polynomial-time algorithms are often not known for finding locally optimal...
Schulz, Andreas S., Shmoys, David B., Williamson, David P.
Increasing global competition, rapidly changing markets, and greater consumer awareness have altered the way in which corporations do business. To become more efficient, many industries have sought...
Schulz, Andreas S., Shmoys, David B., Williamson, David P.
Increasing global competition, rapidly changing markets, and greater consumer awareness have altered the way in which corporations do business. To become more efficient, many industries have sought...
Solving Project Scheduling Problems by Minimum Cut
Moehring, Rolf, Uetz, Marc, Stork, Frederik, Schulz, Andreas S.
In project scheduling, a set of precedence-constrained jobs has to be scheduled so as to minimize a given objective. In resource-constrained project scheduling, the jobs additionally compete for...
Selfish Routing in Capacitated Networks
Correa, Jose R., Schulz, Andreas S., Stier Moses, Nicolas E.
According to Wardrop's first principle, agents in a congested network choose their routes selfishly, a behavior that is captured by the Nash equilibrium of the underlying noncooperative game. A Nash...
Scheduling to Minimize Average Completion Time Revisited: Deterministic On-line Algorithms
Megow, Nicole, Schulz, Andreas S.
We consider the scheduling problem of minimizing the average weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive...
Computational Complexity, Fairness, and the Price of Anarchy of the Maximum Latency Problem
Correa, Jose R., Schulz, Andreas S., Stier Moses, Nicolas E.
We study the problem of minimizing the maximum latency of flows in networks with congestion. We show that this problem is NP-hard, even when all arc latency functions are linear and there is a single...
A geometric approach to the price of anarchy in nonatomic congestion games
Correa, José R., Schulz, Andreas S., Stier-Moses, Nicolás E.
We present a short, geometric proof for the price-of-anarchy results that have recently been established in a series of papers on selfish routing in multicommodity flow networks and on nonatomic...