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.     

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.     

Finding a Length-Constrained Maximum-Density Path in a Tree

Let T = (V,E,w) be an undirected and weighted tree with node set V and edge set E, where w(e) is an edge weight function for e E. The density of a path, say e₁, e₂,..., e_k, is defined as ^k_{i = 1} w(e_i)/k. The length of a path is the number of its edges. Given a tree with n edges and a lower bound L where 1 L n, this paper presents two efficient algorithms for finding a maximum-density path of length at least L in O(nL) time. One of them is further modified to solve some special cases such as full m-ary trees in O(n) time.     

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.     

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.     

A New Fully Polynomial Time Approximation Scheme for the Knapsack Problem

A fully polynomial time approximation scheme (FPTAS) is presented for the classical 0-1 knapsack problem. The new approach considerably improves the necessary space requirements. The two best previously known approaches need O(n + 1/³) and O(n · 1/) space, respectively. Our new approximation scheme requires only O(n + 1/²) space while also reducing the running time.     

On the adjacent vertex-distinguishing total chromatic numbers of the graphs with Δ (G) = 3

Let be a simple graph and T(G) be the set of vertices and edges of G. Let C be a k-color set. A (proper) total k-coloring f of G is a function such that no adjacent or incident elements of T(G) receive the same color. For any , denote . The total k-coloring f of G is called the adjacent vertex-distinguishing if for any edge . And the smallest number of colors is called the adjacent vertex-distinguishing total chromatic number of G. In this paper, we prove that for all connected graphs with maximum degree three. This is a step towards a conjecture on the adjacent vertex-distinguishing total coloring. MSC: 05C15     

Optimal Augmentation of a 2-Vertex-Connected Multigraph to a k-Edge-Connected and 3-Vertex-Connected Multigraph

Given an undirected multigraph G = (V, E) and two positive integers and k, we consider the problem of augmenting G by the smallest number of new edges to obtain an -edge-connected and k-vertex-connected multigraph. In this paper, we show that the problem can be solved in Õ(mn²) time for any fixed and k = 3 if an input multigraph G is 2-vertex-connected, where n = |V| and m is the number of pairs of adjacent vertices in G.     

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.     

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.     

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.     

Power Assignment for <Emphasis Type="Italic">k</Emphasis>-Connectivity in Wireless Ad Hoc Networks

The problem Min-Power k-Connectivity seeks a power assignment to the nodes in a given wireless ad hoc network such that the produced network topology is k-connected and the total power is the lowest. In this paper, we present several approximation algorithms for this problem. Specifically, we propose a 3k-approximation algorithm for any k, a (k + 12H (k)) -approximation algorithm for k(2k–1) n where n is the network size, a (k+2(k + 1)/2) -approximation algorithm for 2 k7, a 6-approximation algorithm for k = 3, and a 9-approximation algorithm for k = 4.This work is supported in part by Hong Kong Research Grant Council under grant No. CityU 1149/04E.This work is partially supported by NSF CCR-0311174.     

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 .     

Inverse Polymatroidal Flow Problem

Let D = (V, A) be a directed graph, for each vertex v V, let ⁺(v) and ^– (v) denote the sets of arcs leaving and entering v, and be intersecting families on ⁺(v) and ^–(v), respectively, and and be submodular functions on intersecting pairs. A flow f : A R is feasible if

Are g.p.a. and ethics related?

This article reports results of a study of some 200 college-aged students at California State University. Ethical values are measured using a subset of the well-known and frequently used Rokeach Value Survey. Using nonparametric statistical analysis, four value measures, and four different consistent tests of significance and probability, the research data, perhaps disappointedly for many observers including the authors, reveal that there is no relationship between college grade point average and student ethics. Statistical analysis was done on g.p.a. splits of less than 3.0 versus 3.0 or more and also on g.p.a. data for 2.5 or less versus 3.5 or more. In all cases, there are no significant relationships between high or low grade point averages and scores on ethical value rankings.     

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.     

On the Tightness of the Alternating-Cycle Lower Bound for Sorting by Reversals

We give a theoretical answer to a natural question arising from a few years of computational experiments on the problem of sorting a permutation by the minimum number of reversals, which has relevant applications in computational molecular biology. The experiments carried out on the problem showed that the so-called alternating-cycle lower bound is equal to the optimal solution value in almost all cases, and this is the main reason why the state-of-the-art algorithms for the problem are quite effective in practice. Since worst-case analysis cannot give an adequate justification for this observation, we focus our attention on estimating the probability that, for a random permutation of n elements, the above lower bound is not tight. We show that this probability is low even for small n, and asymptotically (1/n⁵), i.e., O(1/n⁵) and (1/n⁵). This gives a satisfactory explanation to empirical observations and shows that the problem of sorting by reversals and its alternating-cycle relaxation are essentially the same problem, with the exception of a small fraction of pathological instances, justifying the use of algorithms which are heavily based on this relaxation. From our analysis we obtain convenient sufficient conditions to test if the alternating-cycle lower bound is tight for a given instance. We also consider the case of signed permutations, for which the analysis is much simpler, and show that the probability that the alternating-cycle lower bound is not tight for a random signed permutation of m elements is asymptotically (1/m²).     

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.     

Polynomial Primal-Dual Affine Scaling Algorithms in Semidefinite Programming

Two primal-dual affine scaling algorithms for linear programming are extended to semidefinite programming. The algorithms do not require (nearly) centered starting solutions, and can be initiated with any primal-dual feasible solution. The first algorithm is the Dikin-type affine scaling method of Jansen et al. (1993b) and the second the classical affine scaling method of Monteiro et al. (1990). The extension of the former has a worst-case complexity bound of O(₀nL) iterations, where ₀ is a measure of centrality of the the starting solution, and the latter a bound of O(₀nL²) iterations.