Approximating the chromatic index of multigraphs

It is well known that if G is a multigraph then χ′(G)≥χ′^*(G):=max {Δ(G),Γ(G)}, where χ′(G) is the chromatic index of G, χ′^*(G) is the fractional chromatic index of G, Δ(G) is the maximum degree of G, and Γ(G)=max {2|E(G[U])|/(|U|−1):U⊆V(G),|U|≥3, |U| is odd}. The conjecture that χ′(G)≤max {Δ(G)+1,⌈Γ(G)⌉} was made independently by Goldberg (Discret. Anal. 23:3–7, 1973), Anderson (Math. Scand. 40:161–175, 1977), and Seymour (Proc. Lond. Math. Soc. 38:423–460, 1979). Using a probabilistic argument Kahn showed that for any c>0 there exists D>0 such that χ′(G)≤χ′^*(G)+c χ′^*(G) when χ′^*(G)>D. Nishizeki and Kashiwagi proved this conjecture for multigraphs G with χ′(G)>⌊(11Δ(G)+8)/10⌋; and Scheide recently improved this bound to χ′(G)>⌊(15Δ(G)+12)/14⌋. We prove this conjecture for multigraphs G with $\chi'(G)>\lfloor\Delta(G)+\sqrt{\Delta(G)/2}\rfloor$\chi'(G)>\lfloor\Delta(G)+\sqrt{\Delta(G)/2}\rfloor , improving the above mentioned results. As a consequence, for multigraphs G with $\chi'(G)>\Delta(G)+\sqrt {\Delta(G)/2}$\chi'(G)>\Delta(G)+\sqrt {\Delta(G)/2} the answer to a 1964 problem of Vizing is in the affirmative.     

Strongly 2-shape-sortability of vector partitions

Partitioning points optimally in ℝ¹ have been well studied. Hwang et al. (2003) first extended the optimal partitioning problems from ℝ¹ to ℝ^d. In particular, they studied the “sortability” of some partition properties. They also constructed examples to show that some partition properties, like Disjoint and Cone disjoint, are not sortable under some constraints 핊. In this note we construct a more concise example than theirs and also prove that another partition property, Nonpenetrating, is not sortable under 핊.     

Business Ethics through Meditation: The Ethical ‘I,’ the Ethical ‘You,’ the Ethical ‘We’⋆

Environmentalists have been criticizing the ethics of business people concerning the natural environment. Citing Thomas Berry as an example, this paper attempts to bring his three abstract values (presence, subjectivity, and communion) closer to the understanding of the average business person through meditation. The introduction describes business ethics in terms of relationships to the individual, or the ethical ‘I’ to the natural environment, or the ethical ‘You’ and to interpersonal relationships, or the ethical ‘We.’ Meditation is also defined, according to Webster's Third New International Dictionary (1986), as a meditative experience together with a period of reflection and small-group discussion. More specifically, meditation takes on three forms. Part one describes nondiscursive meditation in the context of what Berry means by presence. The problem addressed here is how to meet and cultivate the ethical ‘I.’ Part two will deal with semidiscursive meditation in the context of what Berry means by subjectivity, or the ethical ‘I’ in relation to the earth. The earth then becomes the ethical ‘You.’ Part three will deal with Berry's definition of communion, or the ethical ‘We.’ The practice of discursive meditation gradually leads to what Thomas Berry calls a renewed ‘visionary experience.’ The article concludes with a redefinition of business ethics in terms of our relationships to ourselves, as human persons, to the earth as our living environment, and to each other as members of the human community. The redefinition of our relationships through meditation is ‘visionary,’ or a new ‘paradigm,’ that, hopefully, will lead to the renewed ethical practice that other environmentalists are also advocating, for example, Arnold Berleant. This revised version was published online in July 2006 with corrections to the Cover Date.     

Point sets in the unit square and large areas of convex hulls of subsets of points

In this paper generalizations of Heilbronn’s triangle problem to convex hulls of j points in the unit square [0,1]² are considered. By using results on the independence number of linear hypergraphs, for fixed integers k≥3 and any integers n≥k a deterministic o(n ^6k−4) time algorithm is given, which finds distributions of n points in [0,1]² such that, simultaneously for j=3,…,k, the areas of the convex hulls determined by any j of these n points are Ω((log n)^1/(j−2)/n ^{(j−1)/(j−2)}).     

Priority algorithms for the subset-sum problem

Greedy algorithms are simple, but their relative power is not well understood. The priority framework (Borodin et al. in Algorithmica 37:295–326, 2003) captures a key notion of “greediness” in the sense that it processes (in some locally optimal manner) one data item at a time, depending on and only on the current knowledge of the input. This algorithmic model provides a tool to assess the computational power and limitations of greedy algorithms, especially in terms of their approximability. In this paper, we study priority algorithm approximation ratios for the Subset-Sum Problem, focusing on the power of revocable decisions, for which the accepted data items can be later rejected to maintain the feasibility of the solution. We first provide a tight bound of α≈0.657 for irrevocable priority algorithms. We then show that the approximation ratio of fixed order revocable priority algorithms is between β≈0.780 and γ≈0.852, and the ratio of adaptive order revocable priority algorithms is between 0.8 and δ≈0.893. A preliminary version of this paper appeared in the Proceedings of COCOON 2007, LNCS 4598, pp. 504–514.     

Finding longest increasing and common subsequences in streaming data

We present algorithms and lower bounds for the Longest Increasing Subsequence (LIS) and Longest Common Subsequence (LCS) problems in the data-streaming model. To decide if the LIS of a given stream of elements drawn from an alphabet αbet has length at least k, we discuss a one-pass algorithm using O(k log αbetsize) space, with update time either O(log k) or O(log log αbetsize); for αbetsize = O(1), we can achieve O(log k) space and constant-time updates. We also prove a lower bound of Ω(k) on the space requirement for this problem for general alphabets αbet, even when the input stream is a permutation of αbet. For finding the actual LIS, we give a ⌈log (1 + 1/ɛ)-pass algorithm using O(k^1+ɛlog αbetsize) space, for any ɛ > 0. For LCS, there is a trivial Θ(1)-approximate O(log n)-space streaming algorithm when αbetsize = O(1). For general alphabets αbet, the problem is much harder. We prove several lower bounds on the LCS problem, of which the strongest is the following: it is necessary to use Ω(n/ρ²) space to approximate the LCS of two n-element streams to within a factor of ρ, even if the streams are permutations of each other. A preliminary version of this paper appears in the Proceedings of the 11th International Computing and Combinatorics Conference (COCOON'05), August 2005, pp. 263–272.     

Morals, Ethics, and Integrity: How Codes of Conduct Contribute to Ethical Adult Education Practice

This article examines the similarities and differences in the concepts or in the usage of the terms “integrity”, “morals” and “ethics” to provide a framework for understanding why these concepts are the foundation of professional ethics and to promote a more thoughtful consideration of the need for codes of ethics for the field of adult education. The article reviews the original interpretations of these terms by the classic philosophers whose works are fundamental for a greater appreciation of contemporary ethics.     

Upper paired-domination in claw-free graphs

A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The maximum cardinality of a minimal paired-dominating set of G is the upper paired-domination number of G, denoted by Γ_pr(G). We establish bounds on Γ_pr(G) for connected claw-free graphs G in terms of the number n of vertices in G with given minimum degree δ. We show that Γ_pr(G)≤4n/5 if δ=1 and n≥3, Γ_pr(G)≤3n/4 if δ=2 and n≥6, and Γ_pr(G)≤2n/3 if δ≥3. All these bounds are sharp. Further, if n≥6 the graphs G achieving the bound Γ_pr(G)=4n/5 are characterized, while for n≥9 the graphs G with δ=2 achieving the bound Γ_pr(G)=3n/4 are characterized.     

Approximation algorithms and hardness results for labeled connectivity problems

Let G=(V,E) be a connected multigraph, whose edges are associated with labels specified by an integer-valued function ℒ:E→ℕ. In addition, each label ℓ∈ℕ has a non-negative cost c(ℓ). The minimum label spanning tree problem (MinLST) asks to find a spanning tree in G that minimizes the overall cost of the labels used by its edges. Equivalently, we aim at finding a minimum cost subset of labels I⊆ℕ such that the edge set {e∈E:ℒ(e)∈I} forms a connected subgraph spanning all vertices. Similarly, in the minimum label s – t path problem (MinLP) the goal is to identify an s–t path minimizing the combined cost of its labels. The main contributions of this paper are improved approximation algorithms and hardness results for MinLST and MinLP.     

Zeit und Zeitgeist in der Betriebswirtschaftslehre — dargestellt am Beispiel der betriebswirtschaftlichen Flexibilitätsdiskussion

Zusammenfassung  Gegenstand des vorliegenden Beitrags ist die Untersuchung der über 80 Jahre andauernden Flexibilit?tsdiskussion in der deutschen Betriebswirtschaftslehre. Eine quantitative und qualitative Analyse dieser Diskussion macht deutlich, dass die Zeit (bzw. die im Zeitablauf feststellbaren Entwicklungen oder Ereignisse) sowie der Zeitgeist (als Gesamtheit der eine Epoche kennzeichnenden Auffassungen, Ideen und Lebensformen) erkl?rende Variablen einer wissenschaftlichen Diskussion und ihrer Ergebnisse sein k?nnen. Schon der relativ lange Zeitraum der wissenschaftlichen Behandlung l?sst das Flexibilit?tsthema als „L?ngsschnittstichprobe“ zur Prüfung der oben genannten Hypothese geeignet erscheinen. So wird gezeigt werden, dass die Flexibilit?tsdiskussion durch externe Ereignisse ausgel?st wurde und im Zeitablauf immer wieder „neu“ an Dynamik gewonnen und sich an jeweils vorherrschende Themen und Probleme — den „Zeitgeist“ — ausgerichtet hat. Am Ende der Untersuchung stehen die folgenden Erkenntnisse:

A New delay control method for real-time flows

This paper presents a novel control algorithm to decrease the worst-case delay bound for high rate homogeneous and heterogeneous real-time flows when the network traffic load becomes heavy. The algorithm is adaptive based on the instantaneous network situations. It employs a generalized form of traditional (σ,ρ) regulator called the generalized (σ,ρ,λ) regulator that operates like the (σ,ρ) regulator under the normal network traffic load situation, but provides more regulations for the heavy network traffic load situation. For a set of real-time flows, we can show that D _rg ≤D _g where D _rg and D _g are the worst-case delay bounds with the (σ,ρ,λ) regulator and the (σ,ρ) regulator respectively. More specifically, we have developed a set of formulas to set the parameters for the new regulator so as to reduce the worst-case delay bounds for the real-time flows. We can prove that there exists a threshold input rate ρ^* such that D _rg = D _g for ρ≤ρ^* and D _rg < D _g for ρ > ρ^*. When the average input rate of real-time flows is very high, the generalized regulator can effectively control the delay. The extensive experiment data match our theoretical results. The part of this paper has been appeared in The 23 ^rd IEEE International Conference on Distributed Computing Systems, 2003. The work is supported by CityU strategic grant Nos: 7001777 and 7001709 and CityU ARP Project No. 9610027. H. Wang was partially supported by National Natural Science Foundation of China (10471088, 60572126) and CityU strategic grant no. 7001709. Wanqing Tu is now with Department of Computer Science, The Hong Kong University of Science and Technology. Clear Water Bay, New Territories, Kowloon, Hong Kong.     

From Bureaucracy to Debureaucratization?

More than previous mild recessions, the current global crisis calls into question the merits of a model that held sway for almost three decades. Celebrated in the nineties in a “National Bestseller”, which even President Clinton considered to be a “blueprint” “for all officials to read”, the book—Reinventing Government—preached the reform of government in private sector ways. In stark contrast to Bureaucracy, which they considered “Bankrupt”. Authors Osborne and Gaebler (1993) promoted Debureaucratization, which they summed up as decentralization, deregulation, downsizing and outsourcing. It is time to revisit the assumptions of the Osborne-Gaebler model that has demonstrably failed. More than the model, however, the ways of its promotion in the market of ideas invites a word of caution. It prompted simplistic distortions, which typically followed from superficial analyses of Weber’s seminal opus (Timsit 2008:864–875). This paper reconsiders these two contrasting models, though not in “black” and “white”. Rather, the two are explored in dialectical terms, as outcomes of shifting ideologies, often taken to extremes.     

On the upper total domination number of Cartesian products of graphs

In this paper we continue the investigation of total domination in Cartesian products of graphs first studied in (Henning, M.A., Rall, D.F. in Graphs Comb. 21:63–69, 2005). A set S of vertices in a graph G is a total dominating set of G if every vertex in G is adjacent to some vertex in S. The maximum cardinality of a minimal total dominating set of G is the upper total domination number of G, denoted by Γ _t (G). We prove that the product of the upper total domination numbers of any graphs G and H without isolated vertices is at most twice the upper total domination number of their Cartesian product; that is, Γ _t (G)Γ _t (H)≤2Γ _t (G □ H). Research of M.A. Henning supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

Integer-magic spectra of sun graphs

Let A be a non-trivial Abelian group. A graph G=(V,E) is A-magic if there exists a labeling f:E→A∖{0} such that the induced vertex set labeling f ⁺:V→A, defined by f ⁺(v)=∑f(uv) where the sum is over all uv∈E, is a constant map. The integer-magic spectrum of a graph G is the set IM(G)={k∈ℕ∣G is ℤ _k -magic}. A sun graph is obtained from an n-cycle, by attaching paths to each pair of adjacent vertices in the cycle. In this paper, we investigate the integer-magic spectra of some sun graphs. Dedicated to Prof. Frank K. Hwang, on the occasion of his 65th birthday. Supported by Faculty Research Grant, Hong Kong Baptist University.     

A combinatorial theorem on labeling squares with points and its application

In this paper, we present a combinatorial theorem on labeling disjoint axis-parallel squares of edge length two using points. Given an arbitrary set of disjoint axis-parallel squares of edge length two, we show that if we label points on the boundary of all squares (one for each square) and define a distance label graph such that there is an edge between any two labeling points if and only if their L_∞-distance is at most 1 − ε (0 < ε < 1), then the maximum connected component of the graph contains Θ(1/ε) vertices, which is tight. With this theorem we present a new and simple factor-(3 + ε) approximation for labeling points with axis-parallel squares under the slider model. This research is supported by NSF CARGO Grant DMS-0138065.     

Hardness of <Emphasis Type="Italic">k</Emphasis>-Vertex-Connected Subgraph Augmentation Problem

Given a k-connected graph G=(V,E) and V ^′⊂V, k-Vertex-Connected Subgraph Augmentation Problem (k-VCSAP) is to find S⊂V∖V ^′ with minimum cardinality such that the subgraph induced by V ^′∪S is k-connected. In this paper, we study the hardness of k-VCSAP in undirect graphs. We first prove k-VCSAP is APX-hard. Then, we improve the lower bound in two ways by relying on different assumptions. That is, we prove no algorithm for k-VCSAP has a PR better than O(log (log n)) unless P=NP and O(log n) unless NP⊆DTIME(n ^{O(log log n)}), where n is the size of an input graph.     

Hamiltonicity of hypercubes with a constraint of required and faulty edges

Let R and F be two disjoint edge sets in an n-dimensional hypercube Q _n . We give two constructing methods to build a Hamiltonian cycle or path that includes all the edges of R but excludes all of F. Besides, considering every vertex of Q _n incident to at most n−2 edges of F, we show that a Hamiltonian cycle exists if (A) |R|+2|F|≤2n−3 when |R|≥2, or (B) |R|+2|F|≤4n−9 when |R|≤1. Both bounds are tight. The analogous property for Hamiltonian paths is also given. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. Lih-Hsing Hsu’s research project is partially supported by NSC 95-2221-E-233-002. Shu-Chung Liu’s research project is partially supported by NSC 90-2115-M-163-003 and 95-2115-M-163-002. Yeong-Nan Yeh’s research project is partially supported by NSC 95-2115-M-001-009.     

On optimal placement of relay nodes for reliable connectivity in wireless sensor networks

The paper addresses the relay node placement problem in two-tiered wireless sensor networks. Given a set of sensor nodes in Euclidean plane, our objective is to place minimum number of relay nodes to forward data packets from sensor nodes to the sink, such that: 1) the network is connected, 2) the network is 2-connected. For case one, we propose a (6+ε)-approximation algorithm for any ε > 0 with polynomial running time when ε is fixed. For case two, we propose two approximation algorithms with (24+ε) and (6/T+12+ε), respectively, where T is the ratio of the number of relay nodes placed in case one to the number of sensors. We further extend the results to the cases where communication radiuses of sensor nodes and relay nodes are different from each other.     

On backbone coloring of graphs

Let G be a graph and H a subgraph of G. A backbone-k-coloring of (G,H) is a mapping f: V(G)→{1,2,…,k} such that |f(u)−f(v)|≥2 if uv∈E(H) and |f(u)−f(v)|≥1 if uv∈E(G)\E(H). The backbone chromatic number of (G,H) is the smallest integer k such that (G,H) has a backbone-k-coloring. In this paper, we characterize the backbone chromatic number of Halin graphs G=T∪C with respect to given spanning trees T. Also we study the backbone coloring for other special graphs such as complete graphs, wheels, graphs with small maximum average degree, graphs with maximum degree 3, etc.     

The Relationship Between Sustained Success and Donations for an Athletic Department with a Premier Football Program

Anecdotal discussions regarding donor contributions to athletic departments have long placed considerable emphasis on the success of the departments’ athletic programs. Among the most visible sports is football. The purpose of this study was to explore one high profile athletic department’s level of financial gifts and donations related to the performance of the university’s prestigious football program. The following data were collected for each year over an 11 year period (1998 thru 2008): the football team’s winning percentage; total money raised from donors; number of donors making contributions; number of contributions; and average size of each contribution. The researchers found that the only linier relationship that existed with the team’s winning percentage was a negative relationship between winning and the average size of each contribution (p < .05; R ² = .682).