This paper proposes a new method for probabilistic analysis of online algorithms that is based on the notion of stochastic dominance. We develop the method for the Online Bin Coloring problem introduced by Krumke et al. Using methods for the stochastic comparison of Markov chains we establish...

We consider the problem to price (digital) items in order to maximize the revenue obtainable from a set of bidders. We suggest a natural monotonicity constraint on bundle prices, show that the problem remains NP-hard, and we derive a PTAS. We also discuss a special case, the highway pricing problem.

We consider a revenue maximization problem where we are selling a set of m items, each of which available in a certain quantity (possibly unlimited) to a set of n bidders. Bidders are single minded, that is, each bidder requests exactly one subset, or bundle of items. Each bidder has a valuation...

We present first constant performance guarantees for preemptive stochastic scheduling to minimize the sum of weighted completion times. For scheduling jobs with release dates on identical parallel machines we derive policies with a guaranteed performance ratio of 2 which matches the currently...

We study the problem of minimizing the makespan on m parallel machines. We introduce a very large-scale neighborhood of exponential size (in the number of machines) that is based on a matching in a complete graph. The idea is to partition the jobs assigned to the same machine into two sets. This...

Increasing interest has recently been shown in analyzing the worst-case behavior of local search algorithms. In particular, the quality of local optima and the time needed to find the local optima by the simplest form of local search has been studied. This paper deals with worst-case performance...

We consider a Stackelberg pricing problem in directed networks:Tariffs (prices) have to be defined by an operator, the leader, for a subset of the arcs. Clients, the followers, choose paths to route their demand through the network selfishly and independently of each other, on the basis of...

We consider a scheduling problem where a set of jobs is distributed over parallel machines. The processing time of any job is dependent on the usage of a scarce renewable resource, e.g., personnel. An amount of k units of that resource can be allocated to the jobs at any time, and the more of...

We study the problem of scheduling maintenance services. Given is a set of mmachines and integral cost-coefficients ai and bi for each machine i (1 i m). Timeis discretized into unit-length periods; in each period at most one machine can beserviced at a given service cost bi. The operating...

This paper is concerned with polynomial time approximations schemes for the generalized geometric problems with geographic clustering. We illustrate the approach on the generalized traveling salesman problem which is also known as Group-TSP or TSP with neighborhoods. We prove that under the...