Improved Dynamic Programming in Connection with an FPTAS for the Knapsack Problem

A vector merging problem is introduced where two vectors of length n are merged such that the k-th entry of the new vector is the minimum over of the -th entry of the first vector plus the sum of the first k – + 1 entries of the second vector. For this problem a new algorithm with O(n log n) running time is presented thus improving upon the straightforward O(n ²) time bound.The vector merging problem can appear in different settings of dynamic programming. In particular, it is applied for a recent fully polynomial time approximation scheme (FPTAS) for the classical 0–1 knapsack problem by the same authors.     

On Shortest k-Edge-Connected Steiner Networks in Metric Spaces

Given a set of points P in a metric space, let l(P) denote the ratio of lengths between the shortest k-edge-connected Steiner network and the shortest k-edge-connected spanning network on P, and let r = inf l(P) P for k 1. In this paper, we show that in any metric space, r 3/4 for k 2, and there exists a polynomial-time -approximation for the shortest k-edge-connected Steiner network, where = 2 for even k and = 2 + 4/(3k) for odd k. In the Euclidean plane, and .     

Local Optimality and Its Application on Independent Sets for k-claw Free Graphs

Given a graph G = (V,E), we define the locally optimal independent sets asfollows. Let S be an independent set and T be a subset of V such that S T = and (S) T, where (S) is defined as the neighbor set of S. A minimum dominating set of S in T is defined as T_D(S) T such that every vertex of S is adjacent to a vertex inTD(S) and TD(S) has minimum cardinality. An independent setI is called r-locally optimal if it is maximal and there exists noindependent set S V\I with |ID (S)| r such that|S| >|I (S)|.In this paper, we demonstrate that for k-claw free graphs ther-locally optimal independent sets is found in polynomial timeand the worst case is bounded by , where I and I* are a locally optimal and an optimal independent set,respectively. This improves the best published bound by Hochbaum (1983) bynearly a factor of two. The bound is proved by LP duality and complementaryslackness. We provide an efficientO(|V|^r+3) algorithm to find an independent set which is notnecessarily r-locally optimal but is guarantteed with the above bound. Wealso present an algorithm to find a r-locally optimal independent set inO(|V|^r(k-1)+3) time.     

An Edge-Splitting Algorithm in Planar Graphs

For a multigraph G = (V, E), let s V be a designated vertex which has an even degree, and let _G (V – s) denote min{c _G(X) | Ø X V – s}, where c _G(X) denotes the size of cut X. Splitting two adjacent edges (s, u) and (s, v) means deleting these edges and adding a new edge (u, v). For an integer k, splitting two edges e ₁ and e ₂ incident to s is called (k, s)-feasible if _G(V – s) k holds in the resulting graph G. In this paper, we prove that, for a planar graph G and an even k or k = 3 with k _G (V – s), there exists a complete (k, s)-feasible splitting at s such that the resulting graph G is still planar, and present an O(n ³ log n) time algorithm for finding such a splitting, where n = |V|. However, for every odd k 5, there is a planar graph G with a vertex s which has no complete (k, s)-feasible and planarity-preserving splitting. As an application of this result, we show that for an outerplanar graph G and an even integer k the problem of optimally augmenting G to a k-edge-connected planar graph can be solved in O(n ³ log n) time.     

Efficient Heuristics for Orientation Metric and Euclidean Steiner Tree Problems

We consider Steiner minimum trees (SMT) in the plane, where only orientations with angle , 0 i – 1 and an integer, are allowed. The orientations define a metric, called the orientation metric, , in a natural way. In particular, ₂ metric is the rectilinear metric and the Euclidean metric can beregarded as metric. In this paper, we provide a method to find an optimal SMT for 3 or 4 points by analyzing the topology of SMT's in great details. Utilizing these results and based on the idea of loop detection first proposed in Chao and Hsu, IEEE Trans. CAD, vol. 13, no. 3, pp. 303–309, 1994, we further develop an O(n²) time heuristic for the general SMT problem, including the Euclidean metric. Experiments performed on publicly available benchmark data for 12 different metrics, plus the Euclidean metric, demonstrate the efficiency of our algorithms and the quality of our results.     

Augmenting a Submodular and Posi-modular Set Function by a Multigraph

Given a finite set V and a set function , we consider the problem of constructing an undirected multigraph G = (V,E) such that the cut function together has value at least 2 for all non-empty and proper subsets of V. If f is intersecting submodular and posi-modular, and satisfies the tripartite inequality, then we show that such a multigraph G with the minimum number of edges can be found in time, where is the time to compute the value of f(X) for a subset .     

Circadian Rhythm and the Business Person

Each human being has an internal timekeeping mechanism. To date, over 100 so-called circadian rhythms have been detected. Perhaps the most significant is body temperature. There is an apparent connection between this rhythm and the efficiency with which we do things in the course of the working day. Within individuals, patterns have been discovered which give credence to the popular notions of a morning or an afternoon person, and so on. Our memory changes from morning to afternoon: short-term memory is stronger in the morning, and long-term memory stronger in the afternoon; in schools, morning students have higher grades than students who have other time-of-day preferences. Therefore, a strong case can be made in support of flexible time schedules. It is reported that productivity went up on the introduction of such a scheme. Employee stress has been seen to decline also. When flextime was offered, parents with small children took advantage of the benefit as well as unmarried employees. The only drawback is ensuring that, with so many individual variations in preferences, the needs of the company are fully met. If such a scheme can be devised, however, the research suggests that productivity and efficiency will increase.     

Codes of conduct in Hong Kong organisations

This paper first reviews the literature on the role of codes of conduct for organisations in Hong Kong in their attempts to manage increasingly complex ethical problems and issues. It shows that, although valuable foundations exist upon which to build, research and understanding of the subject is at it's embryonic stage. Social Psychology literature is examined to investigate what lessons those concerned with the study of ethics may learn and the work of Hofstede, as seminal in the area of work-related values, is emphasised in this context.Following Hofstede's proposals for strategies for operationalizing¹ constructs about human values, a content analysis² was conducted on a pilot sample of codes provided by Hong Kong organisations. The results show three clearly identified clusters of organisations with common formats. The first group, described as Foreign Legal, emphasises legal compliance, has criteria for invoking penalties and consists of foreign-owned, large multinational organisations. Companies in the second cluster have codes which, except in the case of a couple of larger organisations, mainly follow the Independent Commission Against Corruption's (ICAC) standard format. The third cluster, described as the Bank Network, also appear to largely conform to a format: the Hong Kong Banking Association's guidelines.Further analysis conducted here of the Hong Kong codes indicates the important role of emic teleological values³, such as trust and reputation, amongst indigenous organisations, rather than the amorality suggested by an earlier study (Dolecheck and Bethke, 1990). These results support the proposition that Hong Kong ethical perspectives are culture bound⁴, as there appear to be different emphases than revealed in an American study (Stevens, 1994), which identified an emphasis in the US codes upon introverted organisational issues and a failure to espouse deontological values⁵.The conclusion is that designing a research programme on business values in Hong Kong requires reference to studies of values in cross-cultural psychology generally and to Hofstede's work in particular. It also supports the need for indigenous research and models in this field which avoid the ethnocentrism inherent in much Western theory and research.     

Center and Distinguisher for Strings with Unbounded Alphabet

Consider two sets and of strings of length L with characters from an unbounded alphabet , i.e., the size of is not bounded by a constant and has to be taken into consideration as a parameter for input size. A closest string s* of is a string that minimizes the maximum of Hamming¹ distance(s, s*) over all string s : s . In contrast, a farthest string t* from maximizes the minimum of Hamming distance(t*,t) over all elements t: t . A distinguisher of from is a string that is close to every string in and far away from any string in . We obtain polynomial time approximation schemes to settle the above problems.     

On Integrality, Stability and Composition of Dicycle Packings and Covers

Given a digraph D, the minimum integral dicycle cover problem (known also as the minimum feedback arc set problem) is to find a minimum set of arcs that intersects every dicycle; the maximum integral dicycle packing problem is to find a maximum set of pairwise arc disjoint dicycles. These two problems are NP-complete.Assume D has a 2-vertex cut. We show how to derive a minimum dicycle cover (a maximum dicycle packing) for D, by composing certain covers (packings) of the corresponding pieces. The composition of the covers is simple and was partially considered in the literature before. The main contribution of this paper is to the packing problem. Let be the value of a minimum integral dicycle cover, and * () the value of a maximum (integral) dicycle packing. We show that if = then a simple composition, similar to that of the covers, is valid for the packing problem. We use these compositions to extend an O(n³) (resp., O(n⁴)) algorithm for finding a minimum integral dicycle cover (resp., packing) from planar digraphs to K_3,3-free digraphs (i.e., digraphs not containing any subdivision of K_3,3).However, if , then such a simple composition for the packing problem is not valid. We show, that if the pieces satisfy, what we call, the stability property, then a simple composition does work. We prove that if = * holds for each piece, then the stability property holds as well. Further, we use the stability property to show that if = * holds for each piece, then = * holds for D as well.     

Context in the Risk Assessment of Digital Systems

As the use of digital computers for instrumentation and control of safety-critical systems has increased, there has been a growing debate over the issue of whether probabilistic risk assessment techniques can be applied to these systems. This debate has centered on the issue of whether software failures can be modeled probabilistically. This paper describes a context-based approach to software risk assessment that explicitly recognizes the fact that the behavior of software is not probabilistic. The source of the perceived uncertainty in its behavior results from both the input to the software as well as the application and environment in which the software is operating. Failures occur as the result of encountering some context for which the software was not properly designed, as opposed to the software simply failing randomly. The paper elaborates on the concept of error-forcing context as it applies to software. It also illustrates a methodology which utilizes event trees, fault trees, and the Dynamic Flowgraph Methodology (DFM) to identify error-forcing contexts for software in the form of fault tree prime implicants.     

A Further Improved Approximation Algorithm for Breakpoint Graph Decomposition

Breakpoint graph decomposition is a crucial step in all recent approximation algorithms for SORTING BY REVERSALS, which is one of the best-known algorithmic problems in computational molecular biology. Caprara and Rizzi recently improved the approximation ratio for breakpoint graph decomposition from to + 1.4348 + , for any positive . In this paper, we extend the techniques of Caprara and Rizzi and incorporate a balancing argument to further improve the approximation ratio to + 1.4193 + , for any positive . These improvements imply improved approximation results for SORTING BY REVERSALS for almost all random permutations.     

Division of Labour and the Locus of Inventive Activity

This paper argues that modularity of knowledge andtechnologies has important implications for the locusof inventive activities. This is because modularityallows for a separation of the innovation process intwo main activities: The production of basic(standardised) modules, and their combination toproduce variants of technologies or product designsthat are better suited to the special needs ofindividual users or markets. This gives rise to adivision of labour whereby the production of moduleswill be performed by specialised upstream suppliers(who enjoy economies of scale), while the combinationof modules will be performed by firms furtherdownstream or by the users themselves. We then suggestthat this pattern can explain a variety of phenomenasuch as why users co-produce their innovations, andhow small regions can support innovative activitydespite the apparent efficiency advantage of largerregions.     

Working with a Community in Crisis: Sustaining and Strengthening the Portland,Maine Seafood Industry

A crisis in the commercial fishing industry jeopardized long term survival of the Port of Portland, the second largest seaport in New England and a significant contributor to Maines economic health. The State of Maine Department of Marine Resources and the City of Portland wanted to find a solution such that industry stakeholders would self-organize, define the industrys future, and create and implement a viable strategy. The consultant conceptualized the project using complexity theory because this theory reflected the deep, complex, community inter-relationships and also provided the opportunity to integrate activities and outcomes across all phases of the project.     

Religious Business Ethics as Interpretation: A Jewish Perspective

This paper examines the method of Jewish business ethics. MichaelWalzer, in his work, Interpretation and Social Criticism (1987), suggeststhree common and important approaches to moral philosophy. He labels thesethe path of discovery, the path of invention, and the path ofinterpretation. The first part of this paper argues that Jewish businessethics is best thought of in terms of interpretation. Without question, thereligious ethicist immediately recognizes Walzers metaphor of the moralworld as a home occupied by a single family over many generations... as his own. Ethical arguments from a Jewish perspective must of necessityhave a lived-in quality and always make reference to and are based on thememory-laden objects and artifacts. The second part of the paper exploressome of the implications of Jewish business ethics as interpretation.     

Mind Engineering for Value-Based Order

This paper tries to trace the background of the modern business paradigm. A business mind dominating the social mind has been the root cause of unethicality in an order, according to this paper. The solution could come from the liberation of the social mind through a process of mind engineering at the individual level. The paper suggests an active mechanism to inculcate values through a systematic process of mind engineering.     

A comparative study of U.S. and Iraqi students

This study uses a sample comprised of U.S. students and Iraqi students to determine if differences occur over ethical perceptions based on cultural/demographic issues. Irrespective of demographics, the results of this study indicate significant cultural differences between Iraqi students and American students with regard to selected ethical issues concerning graduate education. Specifically the differences occurred in the students' perceptions of winning is everything, selling one's soul, logic before emotion, and pander to professors. Iraqi students consistently viewed these beliefs as more necessary for success in their graduate education than did their American counterparts.     

On Approximability of Boolean Formula Minimization

For a Boolean function given by a Boolean formula (or a binary circuit) S we discuss the problem of building a Boolean formula (binary circuit) of minimal size, which computes the function g equivalent to , or -equivalent to , i.e., . In this paper we prove that if P NP then this problem can not be approximated with a good approximation ratio by a polynomial time algorithm.     

Acccounting and Volksgeist – Teritorial Claims on Accounting Regulation

In this paper, it is argued that international diversityin the rules governing corporate accountability is afunction of the desire to preserve local jurisdictionsby maintaining national distinctiveness. Successiveattempts at regulatory harmonisation in Europe havemet considerable resistance, starting with Savignysappeal to the spirit of the people (Volksgeist)and ending with the notion of subsidiarity. In thispaper, territorial claims on regulation are exploredin the context of the rules governing asset revaluation,where there are still almost as many required methodsof accounting in the European Union as there aremember states. The paper rejects the conventionalexplanation that such differences are culture-bound,and instead suggests that the continued existence ofnational rules in accounting reflects the pursuit ofautonomy by individual states and the self-interestof national regulators.     

On Combinatorial Approximation of Covering 0-1 Integer Programs and Partial Set Cover

The problems dealt with in this paper are generalizations of the set cover problem, min{cx | Ax b, x {0,1}ⁿ}, where c Q₊ⁿ, A {0,1}^{m × n}, b 1. The covering 0-1 integer program is the one, in this formulation, with arbitrary nonnegative entries of A and b, while the partial set cover problem requires only m–K constrains (or more) in Ax b to be satisfied when integer K is additionall specified. While many approximation algorithms have been recently developed for these problems and their special cases, using computationally rather expensive (albeit polynomial) LP-rounding (or SDP-rounding), we present a more efficient purely combinatorial algorithm and investigate its approximation capability for them. It will be shown that, when compared with the best performance known today and obtained by rounding methods, although its performance comes short in some special cases, it is at least equally good in general, extends for partial vertex cover, and improves for weighted multicover, partial set cover, and further generalizations.