bluuebunny/crossref_metadata_2025_split huggingface dataset:
Optimal Dynamic Auctions for Revenue Management
Authors: Vulcano Gustavo , van Ryzin Garrett , Maglaras Costis 
Published: January 2003

We analyze a dynamic auction, in which a seller with C units to sell faces a sequence of buyers separated into T time periods. Each group of buyers has independent, private values for a single unit. Buyers compete directly against each other within a period, as in a traditional auction, and indirectly with buyers in other periods through the opportunity cost of capacity assessed by the seller. The number of buyers in each period, as well as the individual buyers' valuations, are random. The model is a variation of the traditional single leg, multiperiod revenue management problem, in which consumers act strategically and bid for units of a fixed capacity over time. For this setting, we prove that dynamic variants of the first-price and second-price auction mechanisms maximize the seller's expected revenue. We also show explicitly how to compute and implement these optimal auctions. The optimal auctions are then compared to a traditional revenue management mechanism—in which list prices are used in each period together with capacity controls—and to a simple auction heuristic that consists of allocating units to each period and running a sequence of standard, multiunit auctions with fixed reserve prices in each period. The traditional revenue management mechanism is proven to be optimal in the limiting cases when there is at most one buyer per period, when capacity is not constraining, and asymptotically when the number of buyers and the capacity increases. The optimal auction significantly outperforms both suboptimal mechanisms when there are a moderate number of periods, capacity is constrained, and the total volume of sales is not too large. The benefit also increases when variability in the dispersion in buyers' valuations or in the number of buyers per period increases.
Solving Multi-Item Lot-Sizing Problems with an MIP Solver Using Classification and Reformulation
Authors: Wolsey Laurence A. 
Published: January 2003

Based on research on the polyhedral structure of lot-sizing models over the last 20 years, we claim that there is a nontrivial fraction of practical lot-sizing problems that can now be solved by nonspecialists just by taking an appropriate a priori reformulation of the problem, and then feeding the resulting formulation into a commercial mixed-integer programming solver. This claim uses the fact that many multi-item problems decompose naturally into a set of single-item problems with linking constraints, and that there is now a large body of knowledge about single-item problems. To put this knowledge to use, we propose a classification of lot-sizing problems (in large part single-item) and then indicate in a set of tables, what is known about a particular problem class and how useful it might be. Specifically, we indicate for each class (i) whether a tight extended formulation is known, and its size; (ii) whether one or more families of valid inequalities are known defining the convex hull of solutions, and the complexity of the corresponding separation algorithms; and (iii) the complexity of the corresponding optimization algorithms (which would be useful if a column generation or Lagrangian relaxation approach was envisaged). Three distinct multi-item lot-sizing instances are then presented to demonstrate the approach, and comparative computational results are presented. Finally, we also use the classification to point out what appear to be some of the important open questions and challenges.
Approximating Multiobjective Knapsack Problems
Authors: Erlebach Thomas , Kellerer Hans , Pferschy Ulrich 
Published: January 2003

For multiobjective optimization problems, it is meaningful to compute a set of solutions covering all possible trade-offs between the different objectives. The multiobjective knapsack problem is a generalization of the classical knapsack problem in which each item has several profit values. For this problem, efficient algorithms for computing a provably good approximation to the set of all nondominated feasible solutions, the Pareto frontier, are studied. For the multiobjective one-dimensional knapsack problem, a practical fully polynomial-time approximation scheme (FPTAS) is derived. It is based on a new approach to the single-objective knapsack problem using a partition of the profit space into intervals of exponentially increasing length. For the multiobjective m-dimensional knapsack problem, the first known polynomial-time approximation scheme (PTAS), based on linear programming, is presented.
Incumbent Entry into New Market Niches: The Role of Experience and Managerial Choice in the Creation of Dynamic Capabilities
Authors: King Andrew A. , Tucci Christopher L. 
Published: January 2003

Increasingly, technological innovation creates markets for new products and services. To survive, firms must respond to these new markets. How do firms develop the capabilities necessary to succeed in such changing conditions? Some suggest that experience with previous entry builds such capabilities. Others suggest that capabilities arise from experience producing and selling to existing markets. The role of managers is also debated. Some argue that experience with existing markets causes managers to miss entry opportunities. Others argue that managers enter new markets when their firm possesses the experience needed to compete effectively.In this paper, we explore these issues by investigating entry patterns in the disk-drive industry. We investigate the effect of experience in existing markets and experience with previous market entry. We find that experience in previous markets increased the probability that a firm would enter a new market. We show that this experience had greater value if the firm entered the new market. We infer that managers chose to enter these markets to obtain this increase in value.
Managing Demand and Sales Dynamics in New Product Diffusion Under Supply Constraint
Authors: Ho Teck-Hua , Savin Sergei , Terwiesch Christian 
Published: January 2003

The Bass diffusion model is a well-known parametric approach to estimating new product demand trajectory over time. This paper generalizes the Bass model by allowing for a supply constraint. In the presence of a supply constraint, potential customers who are not able to obtain the new product join the waiting queue, generating backorders and potentially reversing their adoption decision, resulting in lost sales. Consequently, they do not generate the positive “word-of-mouth” that is typically assumed in the Bass model, leading to significant changes in the new product diffusion dynamics. We study how a firm should manage its supply processes in a new product diffusion environment with backorders and lost sales. We consider a make-to-stock production environment and use optimal control theory to establish that it is never optimal to delay demand fulfillment. This result is interesting because immediate fulfillment may accelerate the diffusion process and thereby result in a greater loss of customers in the future. Using this result, we derive closed-form expressions for the resulting demand and sales dynamics over the product life cycle. We then use these expressions to investigate how the firm should determine the size of its capacity and the time to market its new product. We show that delaying a product launch to build up an initial inventory may be optimal and can be used as a substitute for capacity. Also, the optimal time to market and capacity increase with the coefficients of innovation and imitation in the adoption population. We compare our optimal capacity and time to market policies with those resulting from exogeneous demand forecasts in order to quantify the value of endogenizing demand.
Fair Queuing and Other Probabilistic Allocation Methods
Authors: Moulin Hervé , Stong Richard 
Published: January 2003

A server processes one job per unit of time and randomly schedules the jobs requested by a given set of users; each user may request a different number of jobs. Fair queuing (Shenker 1989) schedules jobs in successive round-robin fashion, where each agent receives one unit in each round until his demand is met and the ordering is random in each round. Fair queuing*, the reverse scheduling of fair queuing, serves first (with uniform probability) one of the users with the largest remaining demand. We characterize fair queuing* by the combination of lower composition—LC—(the scheduling sequence is history independent), demand monotonicity—DM—(increasing my demand cannot result in increased delay) and two equity axioms, equal treatment ex ante—ETEA (two identical demands give the same probability distribution of service) and equal treatment ex post—ETEP (two identical demands must be served in alternating fashion). The set of dual axioms (in which ETEA and ETEP are unchanged) characterizes fair queuing. We also characterize the rich family of methods satisfying LC, DM, and the familiar consistency—CSY—axiom. They work by fixing a standard of comparison (preordering) between a demand of xi units by agent i and one of xj units by agent j. The first job scheduled is drawn from the agents whose demand has the highest standard.
A Necessary and Sufficient Condition for Approachability
Authors: Spinat Xavier 
Published: January 2003

In the framework of two-person repeated games with vector payoffs, Blackwell defined the property of approachability and introduced a sufficient condition for it. He also proved that this condition is necessary in the case of convex sets. We generalize this result: A set is approachable if and only if it contains a set that satisfies Blackwell's condition.
Node-Capacitated Ring Routing
Authors: Frank András , Shepherd Bruce , Tandon Vivek , Végh Zoltán 
Published: January 2003

We consider the node-capacitated routing problem in an undirected ring network along with its fractional relaxation, the node-capacitated multicommodity flow problem. For the feasibility problem, Farkas' lemma provides a characterization for general undirected graphs, asserting roughly that there exists such a flow if and only if the so-called distance inequality holds for every choice of distance functions arising from nonnegative node weights. For rings, this (straightforward) result will be improved in two ways. We prove that, independent of the integrality of node capacities, it suffices to require the distance inequality only for distances arising from (0-1-2)-valued node weights, a requirement that will be called the double-cut condition. Moreover, for integer-valued node capacities, the double-cut condition implies the existence of a half-integral multicommodity flow. In this case there is even an integer-valued multicommodity flow that violates each node capacity by at most one. Our approach gives rise to a combinatorial, strongly polynomial algorithm to compute either a violating double-cut or a node-capacitated multicommodity flow. A relation of the problem to its edge-capacitated counterpart will also be explained.
A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow
Authors: Wayne Kevin D. 
Published: January 2003

We propose the first combinatorial solution to the generalized minimum cost flow problem (flow with losses and gains). Despite a rich history dating back to Kantorovich and Dantzig, until now, the only known way to solve the problem in polynomial-time was via general-purpose linear programming techniques. Polynomial combinatorial algorithms were previously known only for the version of our problem without costs. We design the first such algorithms for the version with costs. Our algorithms also find provably good solutions faster than optimal ones, providing the first strongly polynomial approximation schemes for the problem. Our techniques extend to optimize linear programs with two variables per inequality. Polynomial combinatorial algorithms were previously developed for testing the feasibility of such linear programs. We propose the first such methods for the optimization version.
Combining Problem Structure with Basis Reduction to Solve a Class of Hard Integer Programs
Authors: Louveaux Quentin , Wolsey Laurence A. 
Published: January 2003

Recently Aardal et al. (2000) have successfully solved some small, difficult, equality-constrained integer programs by using basis reduction to reformulate the problems as inequality-constrained integer programs in a different space. Here, we adapt their method to solve integer programs that are larger but have special structure. The practical problem motivating this work is a variant of the market share problem. More formally, the problem can be viewed as finding a matrix X ∈ ℤmn+ satisfying XA = C, BX = D, where A, B, C, D are matrices of compatible dimensions, and the approach requires us to find a reduced basis of the lattice ℒ = {X ∈ ℤm×n: XA = 0, BX = 0}. The main topic of this paper is a study of the lattice ℒ. It is shown that an integer basis of ℒ can be obtained by taking the Kronecker product of vectors from integer bases of two much smaller lattices. Furthermore, the resulting basis is a reduced basis if the integer bases of the two small lattices are reduced bases and a suitable ordering is chosen. Finally, some limited computational results are presented showing the benefits of making use of the problem structure.
The Stable Allocation (or Ordinal Transportation) Problem
Authors: Baïou Mourad , Balinski Michel 
Published: January 2003

The stable allocation problem generalizes the 0,1 stable matching problems (one-to-one, one-to-many, and many-to-many) to the allocation of real valued hours or quantities. A strongly polynomial algorithm proves the existence of “stable allocations.” The set of stable allocations is shown to be a distributive lattice in general, but in the “nondegenerate” case it is a complete linear order. Indeed, in the generic case, when a problem is “strongly nondegenerate,” there exists a single stable allocation. A simple algorithm finds “row-optimal” and “column-optimal” stable allocations, given any stable allocation. When a problem is nondegenerate it finds all stable allocations.
Minimizing Service and Operation Costs of Periodic Scheduling
Authors: Bar-Noy Amotz , Bhatia Randeep , Naor Joseph (Seffi) , Schieber Baruch 
Published: January 2003

We study the problem of scheduling activities of several types under the constraint that, at most, a fixed number of activities can be scheduled in any single time slot. Any given activity type is associated with a service cost and an operating cost that increases linearly with the number of time slots since the last service of this type. The problem is to find an optimal schedule that minimizes the long-run average cost per time slot. Applications of such a model are the scheduling of maintenance service to machines, multi-item replenishment of stock, and minimizing the mean response time in Broadcast Disks. Broadcast Disks recently gained a lot of attention because they were used to model backbone communications in wireless systems, Teletext systems, and Web caching in satellite systems. The first contribution of this paper is the definition of a general model that combines into one several important previous models. We prove that an optimal cyclic schedule for the general problem exists, and we establish the NP-hardness of the problem. Next, we formulate a nonlinear program that relaxes the optimal schedule and serves as a lower bound on the cost of an optimal schedule. We present an efficient algorithm for finding a near-optimal solution to the nonlinear program. We use this solution to obtain several approximation algorithms. (1) A 9/8 approximation for a variant of the problem that models the Broadcast Disks application. The algorithm uses some properties of “Fibonacci sequences.” Using this sequence, we present a 1.57-approximation algorithm for the general problem. (2) A simple randomized algorithm and a simple deterministic greedy algorithm for the problem. We prove that both achieve approximation factor of 2. To the best of our knowledge this is the first worst-case analysis of a widely used greedy heuristic for this problem.
Cost Allocation for a Tree Network with Heterogeneous Customers
Authors: Granot Daniel , Kuipers Jeroen , Chopra Sunil 
Published: January 2003

We analyze a cost allocation problem which could naturally arise from a situation wherein a tree network T = (N ∪ {0}, E), serving heterogeneous customers, has to be constructed. The customers, located at N, require some service from a central supplier, located at vertex 0. The customers have heterogeneous preferences for the level or quality of service received from the central supplier. We formulate the above cost allocation problem as a cooperative game, referred to as an extended tree game. The extended tree game is a proper extension of Megiddo's (1978) tree game, wherein all the customers have identical preferences regarding the level of service received. We prove that an extended tree game is convex, and we show that its Shapley value can be computed in 𝒪(p|N|) time, where p is the number of distinct preference levels. We further provide a complete facial description of the core polytope of an extended tree game, and demonstrate that even when there are only two classes of customers, the number of nonredundant core constraints could be exponential in |N|. Nevertheless, we are able to construct an 𝒪(p|N|) algorithm to check the core membership of an arbitrary cost allocation, which can be used to construct an 𝒪(p|N|3) combinatorial algorithm to compute the nucleolus of an extended tree game. Finally, we show that the complements of the facet-defining coalitions for the core are all connected in an auxiliary tree graph with node set N.
Erratum: The Stable Allocation (or Ordinal Transportation) Problem
Authors: Baïou Mourad , Balinski Michel 
Published: January 2003

An incorrect version of this paper was printed in Mathematics of Operations Research, Vol. 27, No. 3, August 2002, pp. 485–503 . The paper is reprinted correctly below. The stable allocation problem generalizes the 0,1 stable matching problems (one-to-one, one-to-many, and many-to-many) to the allocation of real valued hours or quantities. A strongly polynomial algorithm proves the existence of “stable allocations.” The set of stable allocations is shown to be a distributive lattice in general, but in the “nondegenerate” case it is a complete linear order. Indeed, in the generic case, when a problem is “strongly nondegenerate,” there exists a single stable allocation. A simple algorithm finds “row-optimal” and ”column-optimal” stable allocations, given any stable allocation. When a problem is nondegenerate it finds all stable allocations.
The Complexity of Generic Primal Algorithms for Solving General Integer Programs
Authors: Schulz Andreas S. , Weismantel Robert 
Published: January 2003

Primal methods constitute a common approach to solving (combinatorial) optimization problems. Starting from a given feasible solution, they successively produce new feasible solutions with increasingly better objective function value until an optimal solution is reached. From an abstract point of view, an augmentation problem is solved in each iteration. That is, given a feasible point, these methods find an augmenting vector, if one exists. Usually, augmenting vectors with certain properties are sought to guarantee the polynomial running time of the overall algorithm. In this paper, we show that one can solve every integer programming problem in polynomial time provided one can efficiently solve the directed augmentation problem. The directed augmentation problem arises from the ordinary augmentation problem by splitting each direction into its positive and its negative part and by considering linear objectives on these parts. Our main result states that in order to get a polynomial-time algorithm for optimization it is sufficient to efficiently find, for any linear objective function in the positive and negative part, an arbitrary augmenting vector. This result also provides a general framework for the design of polynomial-time algorithms for specific combinatorial optimization problems. We demonstrate its applicability by considering the min-cost flow problem, by giving a novel algorithm for linear programming over unimodular spaces, and by providing a different proof that for 0/1-integer programming an efficient algorithm solving the ordinary augmentation problem suffices for efficient optimization. Our main result also implies that directed augmentation is at least as hard as optimization. In other words, for an NP-hard problem already the task of finding a directed augmenting vector in polynomial time is hopeless, unless P = NP. We illustrate this kind of consequence with the help of the knapsack problem.
Chessboard Distributions and Random Vectors with Specified Marginals and Covariance Matrix
Authors: Ghosh Soumyadip , Henderson Shane G. 
Published: January 2003

There is a growing need for the ability to specify and generate correlated random variables as primitive inputs to stochastic models.Moti vated by this need, several authors have explored the generation of random vectors with specified marginals, together with a specified covariance matrix, through the use of a transformation of a multivariate normal random vector (the NORTA method). A covariance matrix is said to be feasible for a given set of marginal distributions if a random vector exists with these characteristics. We develop a computational approach for establishing whether a given covariance matrix is feasible for a given set of marginals. The approach is used to rigorously establish that there are sets of marginals with feasible covariance matrix that the NORTA method cannot match. In such cases, we show how to modify the initialization phase of NORTA so that it will exactly match the marginals, and approximately match the desired covariance matrix. An important feature of our analysis is that we show that for almost any covariance matrix (in a certain precise sense), our computational procedure either explicitly provides a construction of a random vector with the required properties, or establishes that no such random vector exists.
Exotic Options for Interruptible Electricity Supply Contracts
Authors: Kamat Rajnish , Oren Shmuel S. 
Published: January 2003

This paper presents the design and pricing of financial contracts for the supply and procurement of interruptible electricity service. While the contract forms and pricing methodology have broader applications, the focus of this work is on electricity market applications, which motivate the contract structures and price process assumptions. In particular, we propose a new contract form that bundles simple forwards with exotic call options that have two exercise points with different strike prices. Such options allow hedging and valuation of supply curtailment risk, while explicitly accounting for the notification lead time before curtailment. The proposed instruments are priced under the traditional GBM price process assumption and under the more realistic assumption (for electricity markets) of a mean reverting price process with jumps. The latter results employ state-of-the-art Fourier transforms techniques.