Packing trees in communication networks

Given an undirected edge-capacitated graph and given (possibly) different subsets of vertices, we consider the problem of selecting a maximum (weighted) set of Steiner trees, each tree spanning a subset of vertices, without violating the capacity constraints. This problem is motivated by applications in multicast communication networks. We give an integer linear programming (ILP) formulation for the problem, and observe that its linear programming (LP) relaxation is a fractional packing problem with exponentially many variables and a block (sub-)problem that cannot be solved in polynomial time. To this end, we take an r-approximate block solver (a weak block solver) to develop a (1−ε)/r-approximation algorithm for the LP relaxation. The algorithm has a polynomial coordination complexity for any ε∈(0,1). To the best of our knowledge, this is the first approximation result for fractional packing problems with only weak block solvers (with arbitrarily large approximation ratio) and a coordination complexity that is polynomial in the input size. This leads also to an approximation algorithm for the underlying tree packing problem. Finally, we extend our results to an important multicast routing and wavelength assignment problem in optical networks, where each Steiner tree is to be assigned one of a limited set of given wavelengths, so that trees crossing the same fiber are assigned different wavelengths. A preliminary version of this paper appeared in the Proceedings of the 1st Workshop on Internet and Network Economics (WINE 2005), LNCS, vol. 3828, pp. 688–697. Research supported by a MITACS grant for all the authors, an NSERC post doctoral fellowship for the first author, the NSERC Discovery Grant #5-48923 for the second and fourth author, NSERC Discovery Grant #15296 for the third author, the Canada Research Chair Program for the second author, and an NSERC industrial and development fellowship for the fourth author.     

ON THE EQUIVALENCE OF TWO VERSIONS OF THE PRESENT VALUE PROCEDURE

The central issue in equipment investment analysis is the selection of the best of two or more alternatives. A common procedure is to first assume that for each alternative there is an infinite stream of identical pieces of equipment. The present value of the associated infinite stream of revenues and costs is calculated. Then the alternative having the highest present value (where revenues are positive and costs are negative) is selected. The assumption of the infinite stream, though computationally desirable, is not very palatable to the decision maker. In this paper we show that the above procedure is equivalent to using a criterion which is definitely more appealing. The author has found this “equivalence” result to be helpful in teaching the basic concepts of the present value procedure. Also the result should be of interest to practitioners involved in equipment investment decision making.     

A Note on “Discrete Sequential Search with Group Activities”

This note comments on a paper published by Wagner and Davis [Decision Sciences (2001), 32(4), 557–573]. These authors present an integer‐programming model for the single‐item discrete sequential search problem with group activities. Based on their experiments, they conjecture that the problem can be solved as a linear program. In this note, we provide a counterexample for which the optimal value of the linear program they propose is different from the optimal value of the integer‐programming model, hence contradicting their conjecture for the specific linear program that they specify. To the best of our knowledge, the conjecture settled in this note was still an open question.     

Towards more productive industrial relations

The author suggests that a critical factor in bringing about an overall improvement in the UK's economic performance is an improvement in Industrial Relations—with the aim of achieving levels of productivity which match the best in the world. The article asks how this is to be done; what has gone wrong; and, more importantly, what can be done to improve the situation in the future.     

Managing learning and developing management

Dr Alan Mumford is best known in the UK for his pioneering work on managerial learning and board-level development in the corporate sector. After his early career in the construction industry, he worked as an internal management development adviser to a number of UK companies before leaving fifteen years ago to join International Management Centres Europe as a professor. Alan continues to advise as an independent consultant and to devote time to writing. A prolific author, his classic text Management Development: Strategies for Action recently appeared in its fourth edition published by the Institute of Personnel and Development, and his reflections on board-level and senior executive development in Learning at the Top (McGraw-Hill, 1995). Of greatest renown is his collaboration with Dr Peter Honey on developing the Learning Styles Questionnaire and the Manual of Learning Styles (Honey, 3rd edn, 1992) which have become the most frequently used diagnostic and development tools on UK corporate management development programnles. Jean Woodall interviewed Alan at his home in London.

Jean Woodall is Professor of Human Resource Development at Kingston University.     

The Event: An Underexamined Risk Concept

Some of the terms used in risk assessment and management are poorly and even contradictorily defined. One such term is “event,” which arguably describes the most basic of all risk‐related concepts. The author cites two contemporary textbook interpretations of “event” that he contends are incorrect and misleading. He then examines the concept of an event in A. N. Kolmogorov's probability axioms and in several more‐current textbooks. Those concepts are found to be too narrow for risk assessments and inconsistent with the actual usage of “event” by risk analysts. The author goes on to define and advocate linguistic definitions of events (as opposed to mathematical definitions)—definitions constructed from natural language. He argues that they should be recognized for what they are: the de facto primary method of defining events.     

Almost optimal solutions for bin coloring problems

In this paper we study two interesting bin coloring problems: Minimum Bin Coloring Problem (MinBC) and Online Maximum Bin Coloring Problem (OMaxBC), motivated from several applications in networking. For the MinBC problem, we present two near linear time approximation algorithms to achieve almost optimal solutions, i.e., no more than OPT+2 and OPT+1 respectively, where OPT is the optimal solution. For the OMaxBC problem, we first introduce a deterministic 2-competitive greedy algorithm, and then give lower bounds for any deterministic and randomized (against adaptive offline adversary) online algorithms. The lower bounds show that our deterministic algorithm achieves the best possible competitive ratio. The research of this paper was partially supported by an NSF CAREER award CCF-0546509.     

Efficient Algorithms and Implementations for Optimizing the Sum of Linear Fractional Functions,with Applications

This paper presents an improved algorithm for solving the sum of linear fractional functions (SOLF) problem in 1-D and 2-D. A key subproblem to our solution is the off-line ratio query (OLRQ) problem, which asks to find the optimal values of a sequence of m linear fractional functions (called ratios), each ratio subject to a feasible domain defined by O(n) linear constraints. Based on some geometric properties and the parametric linear programming technique, we develop an algorithm that solves the OLRQ problem in O((m+n)log (m+n)) time. The OLRQ algorithm can be used to speed up every iteration of a known iterative SOLF algorithm, from O(m(m+n)) time to O((m+n)log (m+n)), in 1-D and 2-D. Implementation results of our improved 1-D and 2-D SOLF algorithm have shown that in most cases it outperforms the commonly-used approaches for the SOLF problem. We also apply our techniques to some problems in computational geometry and other areas, improving the previous results.This research was supported in part by the National Science Foundation under Grant CCR-9623585.The research of this author was supported in part by National Science Foundation under grant CCF-0430366.Grant-in-Aid of Ministry of Science, Culture and Education of Japan, No. 10780274.The research of this author was supported in part by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Scientific Researchon Priority Areas     

A 2-approximation for the preceding-and-crossing structured 2-interval pattern problem

The 2-interval pattern problem over its various models and restrictions was proposed by Vialette (2004) for the application of RNA secondary structure prediction. We present an O(n ³logn)-time 2-approximation algorithm for the problem of finding a largest { < ,-structured subset of 2-intervals given an input 2-interval set of size n. This greatly improves the previous best approximation ratio of 6 by Crochemore et al. (2005).     

An Improved Randomized Approximation Algorithm for Max TSP

We present an O(n³)-time randomized approximation algorithm for the maximum traveling salesman problem whose expected approximation ratio is asymptotically , where n is the number of vertices in the input (undirected) graph. This improves the previous best.Part of work done while visiting City University of Hong Kong.     

A Profitability Evaluation of America's Best Hospitals, 2000–2008

Each year U.S. News and World Report evaluates more than 5,000 U.S. hospitals, of which approximately 3% are considered the best hospitals in America, and hospital profitability has emerged as a business objective for these hospitals. This study investigates the profitability performance of the best (highest quality) hospitals in the United States. A 9‐year longitudinal investigation of profitability for the best hospitals in the United States is conducted. The results offer evidence that the primary drivers of hospital profitability are the case mix index and daily bed capacity. In terms of hospital profitability, there appears to be a tradeoff between these two factors. Finally, caution must be used when ranking U.S. News and World Report Honor Roll hospitals, in terms of profitability and performance.     

Modeling the Dose Response Relationship of Waterborne Acanthamoeba

This study developed dose response models for determining the probability of eye or central nervous system infections from previously conducted studies using different strains of Acanthamoeba spp. The data were a result of animal experiments using mice and rats exposed corneally and intranasally to the pathogens. The corneal inoculations of Acanthamoeba isolate Ac 118 included varied amounts of Corynebacterium xerosis and were best fit by the exponential model. Virulence increased with higher levels of C. xerosis. The Acanthamoeba culbertsoni intranasal study with death as an endpoint of response was best fit by the beta‐Poisson model. The HN‐3 strain of A. castellanii was studied with an intranasal exposure and three different endpoints of response. For all three studies, the exponential model was the best fit. A model based on pooling data sets of the intranasal exposure and death endpoint resulted in an LD₅₀ of 19,357 amebae. The dose response models developed in this study are an important step towards characterizing the risk associated with free‐living amoeba like Acanthamoeba in drinking water distribution systems. Understanding the human health risk posed by free‐living amoeba will allow for quantitative microbial risk assessments that support building design decisions to minimize opportunities for pathogen growth and survival.     

Improving Risk-Based Decision Making for Terrorism Applications

How can we best allocate limited defensive resources to reduce terrorism risks? Dillon et al.'s Antiterrorism Risk-Based Decision Aid (ARDA) system provides a useful point of departure for addressing this crucial question by exhibiting a real-world system that calculates risk reduction scores for different portfolios of risk-reducing countermeasures and using them to rank-order different possible risk mitigation alternatives for Navy facilities. This comment points out some potential limitations of any scoring system that does not take into account risk externalities, interdependencies among threats, uncertainties that are correlated across targets, and attacker responses to alternative allocations of defensive resources. In at least some simple situations, allocations based on risk reduction scores and comparisons can inadvertently increase risks by providing intelligent attackers with valuable information, or they can fail to reduce risks as effectively as nonscoring, optimization-based approaches. These limitations of present scoring methods present exciting technical challenges and opportunities for risk analysts to develop improved methods for protecting facilities and infrastructure against terrorist threats.     

Multiple hypernode hitting sets and smallest two-cores with targets

The multiple weighted hitting set problem is to find a subset of nodes in a hypergraph that hits every hyperedge in at least m nodes. We extend the problem to a notion of hypergraphs with so-called hypernodes and show that, for m=2, it remains fixed-parameter tractable (FPT), parameterized by the number of hyperedges. This is accomplished by a nontrivial extension of the dynamic programming algorithm for hypergraphs. The algorithm might be interesting for certain assignment problems, but here we need it as a tool to solve another problem motivated by network analysis: A d-core of a graph is a subgraph in which every vertex has at least d neighbors. We give an FPT algorithm that computes a smallest 2-core including a given set of target vertices, where the number of targets is the parameter. This FPT result is best possible in the sense that no FPT algorithm for 3-cores can be expected.     

Manufacturing productivity

The general theory of engineering systems suggests that to produce desired order (to make a machine that works, to reduce the entropy, or even to improve productivity) the agent needs access to sources of (i) information, or useful messages; (ii) energy, or motivation; (iii) resources, including skills. A manufacturing economy, being an engineering system, obeys the same rules, so that an objective examination of 11 of them may be instructive. Since Belgium has no native energy and very few native resources, her post-1968 success in raising her productivity suggests significant improvement in her information systems. The author suggests what this improvement may have been.     

SMALL PANELS OF EXPERTS IN DICHOTOMOUS CHOICE SITUATIONS*

This paper analyzes an expert resolution problem under an uncertain dichotomous choice situation. The experts share a common system of norms and therefore they all prefer the alternative that best suits their purpose. The selection of such an alternative is referred to as a correct choice. Our analysis of optimal decision rules for panels of independent experts is pursued for n-member decision-making bodies, n≤ 5. The suggested optimality criterion is the maximization of the probability of the panel's making the correct choice. Within our framework, this criterion is equivalent to the more common criterion of expected-utility maximization. For three-member panels of experts, the expert resolution problem is solved and illustrated by means of a medical application. For four-member panels, we list the three relevant decision rules, specify the conditions for all possible rankings of these rules, and, finally, present an extended consulting application. We conclude by listing seven relevant decision rules in the case of five-member decision-making bodies.     

Investment and planning in R & D

When planning investment in R & D the required resources must be available—including intellectual resources. Ideally all the issues should be clear: and the R & D programme itself should be the most direct route to the objective, avoiding costly lavishness that may divert attention and effort. Innovation involves using intellectual capital and resources to their best advantage, for commercially worthwhile technical progress in industry. Planning is one of the ‘tools’ and both R & D and investment are ‘materials’ of progress. In this paper, the author examines the many implications behind this statement.     

Towards flexible organizations: A multidimensional design

The author considers one way by which the readiness, willingness, and ability of organizations to change themselves can be increased. Specifically, he considers how organizations can be designed to be more flexible and, therefore, more capable of being changed and changing themselves. Flexibility does not guarantee adaptability but it is essential for it.     

Are we going towards a society of “activity” or “work”?*

Abstract. The aim of the article is to discuss the perspective of a decline in dependent work - which Dahrendorf and Braverman had argued was coming - either due to an emerging society of “activities” or a process of work “degradation”. Why did such a scenario not prove to be realistic? The author shows from which concepts such a downgrading stems and points out the responsibility of approaches that do not see work as a social activity and see technology as a deus ex machina. As a matter of fact, the western world is not experiencing a dissolution but, rather, a persistent (if not growing) importance of work. The author sketches the great technical and organizational transformation in the ongoing production patterns and work schemes in contemporary society. He maintains that these processes, decreasing the homogeneity and increasing the heterogeneity of work, make a society of “works” more likely than one of “activities”.