Search costs in quadtrees and singularity perturbation asymptotics

Quadtrees constitute a classical data structure for storing and accessing collections of points in multidimensional space. It is proved that, in any dimension, the cost of a random search in a randomly grown quadtree has logarithmic mean and variance and is asymptotically ditributed as a normal variable. The limit distribution property extends to quadtrees of all dimensions a result only known so far to hold for binary search trees. The analysis is based on a technique of singularity perturbation that appears to be of some generality. For quadtrees, this technique is applied to linear differential equations satisfied by interventing bivariate generating functions This work was partly supported by the ESPRIT Basic Research Action No. 7141 (ALCOM II).     

Properties and applications of forests of quadtrees for pictorial data representation

Region representation as a quadtree data structure is a rich field in computer science with many different approaches. Forests of quadtrees offer space savings over regular quadtrees by concentrating the vital information [4, 5, 6]. They scavenge unused and unneeded space (i.e., node containing no information). This paper investigates several properties of forests of quadtrees which can be used to design manipulation algorithms for forest-quadtree data structure. In addition, the paper discusses the space saving and shows how the basic operations that can be performed on a quadtree can also be done on the more space efficient representation (a forest of quadtrees).     

Mathematical properties of EOQ models with special cost structure

An existence-uniqueness theorem is proved about a minimum cost order for a class of inventory models whose holding costs grow according to a stock level power law. The outcomes of Mingari Scarpello and Ritelli (2008) [1] are then extended to different environments: i.e., when the holding costs change during time generalizing a model available in Weiss (1982) [11], or with invariable holding costs but adopting a backordering strategy. Application cases are provided assuming several functional behaviors of demand versus the stock level.     

Dynamic lot-sizing model with demand time windows and speculative cost structure

We consider a deterministic lot-sizing problem with demand time windows, where speculative motive is allowed. Utilizing an untraditional decomposition principle, we provide an optimal algorithm that runs in O(nT³) time, where n is the number of demands and T is the length of the planning horizon.     

Optimal process control policies under a time-varying cost structure

Quality experts have recognized two types of quality costs resulting from failure of control; namely, internal and external failure costs of control. Explicitly considering the difference between internal and external failure costs in designing statistical process control procedures is especially important in today’s business environment because (1) inventory holding time is strategically kept very short because of the just-in-time philosophy, and (2) product values decrease at a very fast rate over time because of advances in technology and keen competition. In this paper, we develop a process control model under a time-varying cost structure, based on internal and external failure costs. Using the model, we also study the process control policies when the value of the product may decrease over time. We consider two forms of product perishability. The first is an exponential product value drop, and the second is a fixed life product life.     

Spying on the cost structure of naive bidding competitors via linear programming models

A linear programming model is constructed which enables a firm to estimate its competitor's cost structure when the competitor adheres to a non-randomized strategy. The existence of the model makes randomized bidding prudent apart from game theory considerations. The need for increased curriculum attention to optimal bidding is highlighted.     

On the average cost optimality equation and the structure of optimal policies for partially observable Markov decision processes

We consider partially observable Markov decision processes with finite or countably infinite (core) state and observation spaces and finite action set. Following a standard approach, an equivalent completely observed problem is formulated, with the same finite action set but with anuncountable state space, namely the space of probability distributions on the original core state space. By developing a suitable theoretical framework, it is shown that some characteristics induced in the original problem due to the countability of the spaces involved are reflected onto the equivalent problem. Sufficient conditions are then derived for solutions to the average cost optimality equation to exist. We illustrate these results in the context of machine replacement problems. Structural properties for average cost optimal policies are obtained for a two state replacement problem; these are similar to results available for discount optimal policies. The set of assumptions used compares favorably to others currently available.This research was supported in part by the Advanced Technology Program of the State of Texas, in part by the Air Force Office of Scientific Research under Grant AFOSR-86-0029, in part by the National Science Foundation under Grant ECS-8617860, and in part by the Air Force Office of Scientific Research (AFSC) under Contract F49620-89-C-0044.     

Efficiency distribution and the cost frontier

Efficiency measures derived from data envelopment analysis models are employed here to estimate the parametric forms of the efficiency distribution. Possible uses of this method in evaluating cost efficiency in a stochastic framework are also discussed. © 1998 John Wiley & Sons, Ltd.     

An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure

We present a fully polynomial time approximation scheme (FPTAS) for a capacitated economic lot-sizing problem with a monotone cost structure. An FPTAS delivers a solution with a given relative error ɛ in time polynomial in the problem size and in 1/ɛ. Such a scheme was developed by van Hoesel and Wagelmans [8] for a capacitated economic lot-sizing problem with monotone concave (convex) production and backlogging cost functions. We omit concavity and convexity restrictions. Furthermore, we take advantage of a straightforward dynamic programming algorithm applied to a rounded problem.     

Optimizing cost flows by edge cost and capacity upgrade

We examine a network upgrade problem for cost flows. A budget can be distributed among the arcs of the network. An investment on each single arc can be used either to decrease the arc flow cost, or to increase the arc capacity, or both. The goal is to maximize the flow through the network while not exceeding bounds on the budget and on the total flow cost.

The problems are NP-hard even on series-parallel graphs. We provide an approximation algorithm on series-parallel graphs which, for arbitrary δ,>0, produces a solution which exceeds the bounds on the budget and the flow cost by factors of at most 1+δ and 1+, respectively, while the amount of flow is at least that of an optimum solution. The running time of the algorithm is polynomial in the input size and 1/(δ). In addition we give an approximation algorithm on general graphs applicable to problem instances with small arc capacities.     

Entropy, longevity and the cost of annuities

This paper presents an extension of the application of the concept of entropy to annuity costs. Keyfitz (1985) introduced the concept of entropy, and analysed this in the context of continuous changes in life expectancy. He showed that a higher level of entropy indicates that the life expectancy has a greater propensity to respond to a change in the force of mortality than a lower level of entropy. In other words, a high level of entropy means that further reductions in mortality rates would have an impact on measures like life expectancy. In this paper, we apply this to the cost of annuities and show how it allows the sensitivity of the cost of a life annuity contract to changes in longevity to be summarized in a single figure index.     

Quadratic cost flow and the conjugate gradient method

By introducing quadratic penalty terms, a convex non-separable quadratic network program can be reduced to an unconstrained optimization problem whose objective function is a piecewise quadratic and continuously differentiable function. A conjugate gradient method is applied to the reduced problem and its convergence is proved. The computation exploits the special network data structures originated from the network simplex method. This algorithmic framework allows direct extension to multicommodity cost flows. Some preliminary computational results are presented.     

A holding cost bound for the economic lot-sizing problem with time-invariant cost parameters

We show that in an optimal solution of the economic lot-sizing problem the total holding cost in an order interval is bounded from above by a quantity proportional to the setup cost and the logarithm of the number of periods in the interval. We present two applications of this result.     

The irregularity strength and cost of the union of cliques

Assign positive integer weights to the edges of a simple graph with no component isomorphic to K₁ or K₂, in such a way that the graph becomes irregular, i.e., the weight sums at the vertices become pairwise distinct. The minimum of the largest weights assigned over all such irregular assignments on the vertex-disjoint union of complete graphs is determined. The method of proof also yields the smallest possible total increase in the sum of edge weights in irregular asignments, called irregularity cost.     

Allocating the fixed cost as a complement of other cost inputs: A DEA approach

In cost allocation problem, traditional DEA approaches allocate the fixed cost among a group of decision making units (DMUs), and treat the allocated cost as an extra input of each DMU. If costs except for the fixed cost are regarded as inputs in the cost allocation problem, then it is obvious that the fixed cost is a complement of other inputs rather than an extra independent input. Therefore it is necessary to combine the allocated cost with other cost measures in cost allocation problem. Based on this observation, this paper investigates the relationship between the allocated cost and the DEA efficiency score and develops a DEA-based approach to allocate the fixed cost among various DMUs. An example of allocating advertising expenditure between a car manufacturer and its dealers is presented to illustrate the method proposed in this paper.     

Marginal cost price rule for homogeneous cost functions

Mirman and Tauman (1982) show that axioms of cost sharing, additivity, rescaling invariance, monotonicity, and consistency uniquely determine a price rule on the class of continuously differentiable cost problems as the Aumann-Shapley price mechanism. Here we prove that standard versions of these axioms determine uniquely the marginal cost price rule on the class of homogeneous and convex cost functions, which are, in addition, continuously differentiable. This result persists even if the cost functons are not required to be convex. Received: August 2001