bluuebunny/crossref_metadata_2025_split huggingface dataset:
An Approach to Homotopy and Degree Theory
Authors: Garcia C. B. , Zangwill W. I. 
Published: October 2008

Spawned by Scarf's pioneering work on the calculation of fixed points, an entire new field in mathematical programming has emerged. A wide array of problems that can be posed as fixed point problems, such as problems involving equilibria, games, systems of equations, global optimization, and structural mechanics, have come into the purview of these new constructive techniques. Underlying these techniques are certain mathematical concepts from differential topology, more specifically degree theory (Brouwer) and homotopies. Usually, the mathematical machinery required for these concepts necessitates a keen familiarity with piecewise linear and/or differential topology. In this paper, the development is made by following the paths arising from an ordinary differential equation. The differential equation results from Cramer's rule for linear equations. The applicability and ease of our approach are shown by obtaining simple proofs of theorems in differential topology.
Necessary and Sufficient Conditions for Optimal Search Plans for Moving Targets
Authors: Stone Lawrence D. 
Published: October 2008

Let {Xt, t ≥ 0} be a stochastic process representing the motion of a target in Euclidean n-space. Search effort is applied at the rate m(t) > 0 for 0 ≤ t ≤ T, and it is assumed that this effort can be distributed as finely as desired over space. We seek an optimal search plan, i.e., an allocation of effort in time and space which maximizes the probability of detecting the target by time T. When the detection function is concave, theorem 1′ of this paper gives necessary and sufficient conditions for an optimal search plan for a class of target motion processes {Xt, t ≥ 0} which includes virtually any reasonable model of target motion. In the special case of a discrete-time target motion process and an exponential detection function, the necessary and sufficient conditions have the following intuitive interpretation: For t = 0, 1, 2, …, T, let g̃t, be the probability distribution of the target's location at time t given that the effort at all times before and after t failed to detect the target. The optimal plan allocates the effort for time t so as to maximize the probability of detecting a stationary target with distribution g̃t within the effort constraint m(t). This special case is a generalization of Brown's (Brown, S. S. 1978. Optimal search for a moving target in discrete space and time. Submitted for publication.) result for discrete time and space target motion.
Probabilistic Analysis of the Planar k-Median Problem
Authors: Fisher M. L. , Hochbaum D. S. 
Published: October 2008

We consider a problem in which we are given n points distributed randomly in a planar region of area A. We are asked to select K of the points to serve as centers so as to minimise the sum over the n points of the distance between each point and its closest center. This paper shows that the optimal value of this problem grows as [Formula: see text] almost everywhere. This result is used to study an aggregation heuristic that is a formalized version of aggregation methods frequently used for practical location problems. Given any prespecified ϵ > 0, the heuristic can be made to achieve ϵ-optimality almost everywhere. The running time is polynomial in n if K ≤ ln n and linear in n if K ≤ ln ln n. Since all previously proposed heuristics: require n2 time even if K = 1, the aggregation heuristic is dominant for problems with sufficiently small K. Although our main results are asymptotic for large n, the probability that they hold for finite n is known to exceed 1 − 2π−1/2(n − K)−2, which is nearly 1 even for moderate n − K.
The Discrete Sequential Search Problem with Nonrandom Cost and Overlook Probabilities
Authors: Wegener Ingo 
Published: October 2008

Suppose one object is hidden in the kth of n boxes with probability p(k). The boxes are to be searched sequentially. Associated with the jth search of box k is a cost c(j, k) and a conditional probability q(j, k) that the first j − 1 searches of box k are unsuccessful while the jth search is successful given that the object is hidden in box k. The problem is to minimize the expected cost of a strategy which at last surely finds the object. Without further assumptions we give necessary and sufficient conditions for the existence of admissible strategies with finite expected cost and the existence of optimal strategies. We give a procedure for the computation of an optimal strategy.
The Relaxation Method for Solving Systems of Linear Inequalities
Authors: Goffin J. L. 
Published: October 2008

The relaxation method for solving systems of inequalities is related both to subgradient optimization and to the relaxation methods used in numerical analysis. The convergence theory depends upon two condition numbers. The first one is used mostly for the study of the rate of geometric convergence. The second is used to define a range of values of the relaxation parameter which guarantees finite convergence. In the case of obtuse polyhedra, finite convergence occurs for any value of the relaxation parameter between one and two. Various relationships between the condition numbers and the concept of obtuseness are established.
Circular Cuts in a Network
Authors: Hu T. C. , Ruskey F. 
Published: October 2008

A network consists of a set of nodes Vi (i = 1,…, n) with weights wi and a set of arcs connecting nodes Vi and Vj with arc capacity bij. The circular cut problem is to pick a subset of nodes containing V1 such that the total weight of the subset is less than a prescribed constant and the total arc capacity needed to separate the subset from the rest of the network is minimum. As special cases this problem reduces to the MAX-FLOW-MIN-CUT problem and to a 0-1 knapsack problem. In this paper we present techniques for reducing the size of the problem. This is done by reducing the number of cuts that need to be considered and by condensing certain nodes.
The Compensation Method Applied to a One-Product Production/Inventory Problem
Authors: Graves Stephen C. , Keilson Julian 
Published: October 2008

This paper considers a one-product, one-machine production/inventory problem. Demand requests for the product are governed by a Poisson process with demand size being an exponential random variable. The production facility may be in production or idle; while in production, the facility produces continuously at a constant rate. The objective is to minimize system costs consisting of setup costs, inventory holding costs, and backorder costs. Given a two-critical-number policy, the problem is analyzed as a constrained Markov process using the compensation method. A closed-form expression is found for system cost as a function of the policy parameters. This cost function may then be searched to find an optimal policy. The production/inventory problem is related to a server backlog process for an M/M/1 system in which the server departs when the system empties, and returns when the backlog exceeds a specified threshold. The application of the compensation method to this server backlog process is discussed.
On Team Guessing with Independent Information
Authors: Witsenhausen H. S. 
Published: October 2008

Team theory is the study of situations in which a set of cooperating agents, called a team, each with access to different data or information, attempt to optimize a common criterion, under rules which restrict communication between agents. Team theory is of interest in theoretical studies in economics, communication and control. A very simple example of a team situation is the following. Each of the team's n agents attempts to ascertain whether or not a certain random event E of probability ½ has occurred. Agent i must base his decision solely on the observation of random variable Ui and the team's goal is to minimize p̄ = n−1 ∑pi, where pi is the probability that agent i makes an error. The main result of this paper is to show that when the variables U1, …, Un are independent, this alone places a positive lower bound on p̄, no matter what the joint distribution of E and the data {Ui} may be. For each n the exact lower bound is determined: it is [Formula: see text] for n = 2, ¼ for n = 3 and as n goes to infinity it is asymptotic to [Formula: see text]
A Refinement Procedure for Computing Fixed Points Using Scarf's Primitive Sets
Authors: van der Heyden Ludo 
Published: October 2008

A fixed point of a function is a point that coincides with its image when applying the function. Fixed point computations originated with Scarf (Scarf, H. 1967. The approximation of fixed points of a continuous mapping. SIAM J. Appl. Math. 15 1328–1343.) who presented a finite combinatorial method for finding an approximate fixed point. The method is a systematic search through a sequence of combinatorial objects called primitive sets and provides a constructive proof for a theorem whose domain of applicability goes beyond fixed point computations. In this paper we present a refinement method for proving Scarf's theorem. A refinement method solves the main problem, as formulated in Scarf's theorem, by solving a succession of subproblems. A solution for a subproblem is an approximate solution for the main problem. It is also the starting point for solving a more refined subproblem whose solution we expect to have greater accuracy than the approximate solution we started with. Subproblems are solved continuously until a solution of sufficient accuracy has been found. An interesting feature of the refinement method is its possibly nonmonotonic behavior. The method sometimes regresses to a subproblem solved earlier. Several regressions may follow each other, but eventually the method returns to a forward mode. Index theoretic arguments enable us to characterize the points where the procedure behaves nonmonotonically. Finally, we relate our approach to that of Tuy (Tuy, H. 1979. Pivotal methods for computing equilibria: Unified approach and new restart algorithm. Math. Programming 16 210–227.) and establish that both methods coincide. We also show how Scarfs original method can be considered a special case of the refinement method presented here.
Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
Authors: Wolsey Laurence A. 
Published: October 2008

Recently it has been shown how various results on the behaviour of exact and approximate primal algorithms for certain discrete location problems can be obtained by studying the more general problem of maximising a submodular set function. Unfortunately, this more general model tells us little about an important aspect of the discrete location problems, their linear programming relaxations and the possible use of dual solutions in obtaining bounds. Here we examine a slightly more specialised model that again generalises the location problems of interest, but now also includes the continuous aspects of the problems missing from the earlier model, namely the problem: max{w(y): ∑j=1najyj ≤ b, 0 ≤ yj < 1} of maximising a real-valued nondecreasing piecewise linear, concave submodular function subject to a knapsack constraint. We show that a continuous greedy heuristic always attains at least (1 − e−1) × 100% of the optimal value, and that for the discrete problem an adapted greedy heuristic always attains 35% of the optimal value. Specialised to the capacitated and uncapacitated location problems these results permit us to strengthen earlier results, and to obtain new results on dual greedy heuristics.
Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method
Authors: Borgwardt Karl-Heinz 
Published: October 2008

This paper is concerned with the average number of pivot steps of the Simplex Method which are required to solve linear programming problems of the following kind: [Formula: see text] We investigate a certain variant of the Simplex Method, which is particularly suited for theoretical considerations. For every pair (m, n) (m ≥ n) we introduce probability spaces whose random samples are the linear programming problems of the above mentioned type. The vectors ai, v are supposed to be distributed independently, identically and symmetrically under rotations on a bounded subset of ℝn. We deduce upper and lower bounds for the expectation values of the number of steps required in phase II of the Simplex Method. The evaluation of these bounds yields the following result for m → ∞ and for fixed n: (1) The expectation values become O(m1/(n−1)). (2) There exists a distribution whose expectation values increase like m1/(n−1). (3) For any distribution which satisfies our conditions the expectation values tend to infinity. (4) For every ϵ > 0 there are distributions whose expectation values become O(mϵ).
The Economics of Matching: Stability and Incentives
Authors: Roth Alvin E. 
Published: October 2008

This paper considers some game-theoretic aspects of matching problems and procedures, of the sort which involve matching the members of one group of agents with one or more members of a second, disjoint group of agents, ail of whom have preferences over the possible resulting matches. The main focus of this paper is on determining the extent to which matching procedures can be designed which give agents the incentive to honestly reveal their preferences, and which produce stable matches. Two principal results are demonstrated. The first is that no matching procedure exists which always yields a stable outcome and gives players the incentive to reveal their true preferences, even though procedures exist which accomplish either of these goals separately. The second result is that matching procedures do exist, however, which always yield a stable outcome and which always give all the agents in one of the two disjoint sets of agents the incentive to reveal their true preferences.
Stationary Policies in Dynamic Programming Models Under Compactness Assumptions
Authors: Schäl Manfred 
Published: October 2008

The present work deals with the usual stationary decision model of dynamic programming. The imposed convergence condition on the expected total rewards is so general that both the negative (unbounded) case and the positive (unbounded) case are included. However, the gambling model studied by Dubins and Savage is not covered by the present model. In addition to the convergence condition, a continuity and compactness condition is imposed. The main result states that the supremum of the expected total rewards under all stationary policies is equal to the supremum under all (possibly randomized and non-Markovian) policies.
On Random Binary Trees
Authors: Brown Gerald G. , Shubert Bruno O. 
Published: October 2008

A widely used class of binary trees is studied in order to provide information useful in evaluating algorithms based on this storage structure. A closed form counting formula for the number of binary trees with n nodes and height k is developed and restated as a recursion more useful computationally. A generating function for the number of nodes given height is developed and used to find the asymptotic distribution of binary trees. An asymptotic probability distribution for height given the number of nodes is derived based on equally likely binary trees. This is compared with a similar result for general trees. Random binary trees (those resulting from a binary tree sorting algorithm applied to random strings of symbols) are counted in terms of the mapping of permutations of n symbols to binary trees of height k. An explicit formula for this number is given with an equivalent recursive definition for computational use. A generating function is derived for the number of symbols given height. Lower and upper bounds on random binary tree height are developed and shown to approach one another asymptotically as a function of n, providing a limiting expression for the expected height. The random binary trees are examined further to provide expressions for the expectations of the number of vacancies at each level, the distribution of vacancies over all levels, the comparisons required for insertion of a new random symbol, the fraction of nodes occupied at a particular level, the number of leaves, the number of single vacancies at each level, and the number of twin vacancies at each level. A random process is defined for the number of symbols required to grow a tree exceeding any given height. Finally, an appendix is given with sample tabulations and figures of the distributions.
The Temporal Development of Strategy: Patterns in the U.K. Insurance Industry
Authors: Webb David , Pettigrew Andrew 
Published: October 2008

Much writing in the field of strategic management remains an exercise in comparative statics. Cross-sectional research designs are combined with the static metaphors of contingency thinking to analyse the fit between the positioning and resource base of the firm and its performance in differing environments. However, the inadequacies of this tradition are increasingly recognised even by scholars who have created it (Porter 1991). Strategy can no longer be conceived through the static language of states or positions and must now be understood as an innovation contest where the bureaucratic and inflexible will not survive.This paper takes up the challenge to explore the dynamics of industry and firm strategy development. The empirical focus of the paper is the U.K. insurance industry in a period of upheaval between 1990 and 1996. By means of an innovative cross-correlational time series analysis, we are able to show the ebb and flow of strategic change in the industry and the patterns of initiation and imitation as certain firms lead areas of strategy and others follow. These findings are interrogated and interpreted by drawing on and developing theoretical ideas from three literatures which historically have not talked to one another. These are the literatures on innovation, institutionalism, and contextualism.The empirical results show firms pursuing multiple strategies at one point in time and also altering the strategic agenda over time. A cross-correlational analysis of nine firms in the U.K. insurance industry reveals the existence of leaders and laggards in the development of a variety of strategic initiatives. Theoretically the paper examines the mixture of external conditions and internal context and processes which contribute to the development of early and later adopters of strategies in an industry over time.
The Coevolution of New Organizational Forms in the Fashion Industry: A Historical and Comparative Study of France, Italy, and the United States
Authors: Djelic Marie-Laure , Ainamo Antti 
Published: October 2008

In many industries, the contemporary context of acute environmental dislocation shows the limits of traditional organizational recipes. In direct response to environmental challenges, companies are experimenting with new organizational solutions. While flexibility, or the capacity to redefine organizational form to follow changing purposes, is undeniably a common trend, these experiments otherwise differ greatly. Diversity is such, in fact, that it is difficult to clearly identify and define a unique organizational paradigm for the future. To explore the connection between environmental dislocation and organizational transformations, we adopt a historical and comparative perspective. Our empirical base of evidence is the luxury fashion industry in three countries, France, Italy, and the United States. For many years, this industry was defined by stable environmental conditions, and a craft model of organization remained dominant. We show that, over a more recent period, increasing environmental turbulence has brought about a redefinition of the rules of the game. A common response has been for organizations to move towards greater flexibility or modularity and to experiment with network forms. However, we also show that the paths or trajectories leading to organizational flexibility have varied significantly across countries, reflecting historical legacies and institutional constraints. We identify in fact three different network forms in that industry, which represent national ideal types—the “umbrella holding” company in France, the “flexible embedded network” in Italy, and the “virtual organization” in the United States. We argue that the process of change in the luxury fashion industry has been one of coevolution, where environmental transformation and organizational change have fed upon each other through time. Pioneer firms in the luxury fashion industry originally devised organizational solutions within the bounds set by nationally defined constraints and opportunities. Becoming institutionalized, these early solutions in turn shaped the environment for individual organizations and organizational populations, creating new sets of opportunities and constraints. In a path-dependent manner, different models of organization and national competitiveness thus emerged. In conclusion, we are brought to question the likelihood of full and stable convergence towards a unique organizational form or paradigm. There appears to be, in each national context, a process of construction of new organizational solutions that starts from local foundations. Embedded as they are in powerful historical and institutional legacies, organizational differences are there to stay, we believe, beyond the period of transition and acute environmental dislocation.
Argumentation Rationality of Management Decisions
Authors: v. Werder Axel 
Published: October 2008

This article is concerned with the assessment of the substantiation of management decisions in practice. The necessity for this undertaking derives from the fact that to be successful, management must choose the right extent of analysis for preparing major decisions. Testing this hypothesis requires the ability to measure the thoroughness of a decision preparation and to relate different levels of thoroughness to the success of the decision outcomes. In this paper, the author first presents the conceptual framework of argumentation rationality which makes it possible to measure the thoroughness of a decision preparation—or in other words, the soundness of reasons given for the decision.For a concrete-trial usage, the concept is then combined with the methodology of account analysis introduced by Lewin (Lewin 1996, Lewin and Hunter 1996, Hunter 1999) for the research project on “New Organization Forms in the Information Age” (NOFIA). The arguments given explicitly in the accounts express rationales for management decisions and thus give hints on the intensity of the decision preparation. Using a simplified version of the measuring concept which assesses the argumentation rationality on three selected rationality determinants (pro/contra relation, depth of arguments, and breadth of arguments), two different types of rationality analyses are carried out to illustrate the fruitfulness of the approach. First, on the basis of 16 accounts concerning an important strategic decision of Daimler-Benz made in 1985 (becoming an integrated technology group), the arguments discussed during that time are identified and structured for assessing the substantiation of decision preparation. The developed structure of reasoning not only allows a formal evaluation, but in addition offers starting points for a substantial discussion of the change action. Secondly, 138 accounts from the German automotive industry of the years 1990–1997 are analyzed in order to identify first typical patterns of management argumentation. Based on the available empirical foundation, four types of reasoning are isolated, which differ characteristically with respect to the considered rationality determinants. The paper closes with a perspective on significant questions for further elaborating as well as employing the concept in future research.