A note on fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges

In the paper “Fault-free Mutually Independent Hamiltonian Cycles in Hypercubes with Faulty Edges” (J. Comb. Optim. 13:153–162, 2007), the authors claimed that an n-dimensional hypercube can be embedded with (n−1−f)-mutually independent Hamiltonian cycles when f≤n−2 faulty edges may occur accidentally. However, there are two mistakes in their proof. In this paper, we give examples to explain why the proof is deficient. Then we present a correct proof. This work was supported in part by the National Science Council of the Republic of China under Contract NSC 95-2221-E-233-002.     

Fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges

Two Hamiltonian paths are said to be fully independent if the ith vertices of both paths are distinct for all i between 1 and n, where n is the number of vertices of the given graph. Hamiltonian paths in a set are said to be mutually fully independent if two arbitrary Hamiltonian paths in the set are fully independent. On the other hand, two Hamiltonian cycles are independent starting at v if both cycles start at a common vertex v and the ith vertices of both cycles are distinct for all i between 2 and n. Hamiltonian cycles in a set are said to be mutually independent starting at v if any two different cycles in the set are independent starting at v. The n-dimensional hypercube is widely used as the architecture for parallel machines. In this paper, we study its fault-tolerant property and show that an n-dimensional hypercube with at most n−2 faulty edges can embed a set of fault-free mutually fully independent Hamiltonian paths between two adjacent vertices, and can embed a set of fault-free mutually independent Hamiltonian cycles starting at a given vertex. The number of tolerable faulty edges is optimal with respect to a worst case. An extended abstract of this paper appeared in Proceedings of the 2006 International Conference on Innovative Computing, Information and Control (ICICIC), pp. 288–292, IEEE Computer Society Press.     

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 cubic 2-independent Hamiltonian connected graphs

A graph G=(V,E) is Hamiltonian connected if there exists a Hamiltonian path between any two vertices in G. Let P ₁=(u ₁,u ₂,…,u _|V|) and P ₂=(v ₁,v ₂,…,v _|V|) be any two Hamiltonian paths of G. We say that P ₁ and P ₂ are independent if u ₁=v ₁,u _|V|=v _|V|, and u _i ≠v _i for 1<i<|V|. A cubic graph G is 2-independent Hamiltonian connected if there are two independent Hamiltonian paths between any two different vertices of G. A graph G is 1-Hamiltonian if G−F is Hamiltonian for any F⊆V∪E with |F|=1. A graph G is super 3^*-connected if there exist i internal disjoint paths spanning G for i=1,2,3. It is proved that every super 3^*-connected graph is 1-Hamiltonian. In this paper, we prove that every cubic 2-independent Hamiltonian connected graph is also 1-Hamiltonian. We present some cubic 2-independent Hamiltonian connected graphs that are super 3^*-connected, some cubic 2-independent Hamiltonian connected graphs that are not super 3^*-connected, some super 3^*-connected graphs that are not 2-independent Hamiltonian connected, and some cubic 1-Hamiltonian graphs that are Hamiltonian connected but neither 2-independent Hamiltonian connected nor super 3^*-connected. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. This work was supported in part by the National Science Council of the Republic of China under Contract NSC 94-2213-E-233-011.     

On the Sequential Selection Problem*

Kwan and Yuan [13] considered the sequential selection problem in which an employer should arrange the sequence of interviews with job applicants to fill a position. In this note, it is shown that their selection problem would be alternately interpreted as an optimal search problem or, more specifically, a discrete search problem with a stationary target. A more generalized version of the ordering problem is proposed which explicitly considers the time value of money. Also, the optimality of the ordering strategy in the generalized problem is proven by the pair-wise exchange method, which is simpler than the induction hypothesis-based proof. The sequention selection problem is shown to be a special case of the general ordering problem where the discount rate is zero.     

On the total {k}-domination number of Cartesian products of graphs

Let γ _t ^{k}(G) denote the total {k}-domination number of graph G, and let denote the Cartesian product of graphs G and H. In this paper, we show that for any graphs G and H without isolated vertices, . As a corollary of this result, we have for all graphs G and H without isolated vertices, which is given by Pak Tung Ho (Util. Math., 2008, to appear) and first appeared as a conjecture proposed by Henning and Rall (Graph. Comb. 21:63–69, 2005). The work was supported by NNSF of China (No. 10701068 and No. 10671191).     

On Comparing Alternative Advertising Policies of Pulsation*

In this paper, five alternative advertising policies that belong to the advertising pulsation class are compared analytically for linear and concave response functions using a modified version of the Vidale-Wolfe model. The results of the research show that (1) For both linear and concave response functions, advertising pulsing/maintenance policy dominates advertising pulsing policy but is dominated by the Uniform Advertising Policy. For convex response functions, the order of dominance is reversed. (2) For linear response functions, uniform advertising policy dominates the impulse advertising policy but is dominated by the chattering advertising policy. (3) For concave response functions, uniform advertising policy dominates both the impulse advertising policy and the chattering advertising policy. (4) For convex response functions, chattering advertising policy dominates both the advertising pulsing policy and the impulse advertising policy. The Vidale-Wolfe model is estimated using the well-known Lydia Pinkham data. Optimality analysis shows that the company was overadvertising about half of the time studied. Overadvertising seems to have produced appreciable gain in sales and created significant barriers to competitive entry at a little cost in terms of foregone profits.     

On the Rank-Based Selection Strategy for the Group Interview Problem*

For the so-called group interview problem in which several groups of choice alternatives are presented sequentially to the decision maker, the optimal selection strategy is derived that minimizes the expected rank of the selected choice or purchased product. For the case in which the sequence of groups can be rearranged by the decision maker, a simple heuristic procedure is proposed for obtaining a near-optimal sequence of groups, and the performance of the heuristic procedure in a Monte Carlo simulation is accessed. According to the heuristic procedure, the consumer is advised to visit smaller stores first and then move to larger stores later to increase the likelihood of finding a better product. Finally, the optimal selection strategy and the heuristic procedure are compared with those proposed by Chun, Moskowitz, and Plante (1993) and the problem of locating a new store in an area where there are several competing stores is discussed. The optimal selection strategy and the heuristic procedure can be applied to many sequential decision problems such as the consumer search and purchase process.     

Target-guided algorithms for the container pre-marshalling problem

The container pre-marshalling problem (CPMP) aims to rearrange containers in a bay with the least movement effort; thus, in the final layout, containers are piled according to a predetermined order. Previous researchers, without exception, assumed that all the stacks in a bay are functionally identical. Such a classical problem setting is reexamined in this paper. Moreover, a new problem, the CPMP with a dummy stack (CPMPDS) is proposed. At terminals with transfer lanes, a bay includes a row of ordinary stacks and a dummy stack. The dummy stack is actually the bay space that is reserved for trucks. Therefore, containers can be shipped out from the bay. During the pre-marshalling process, the dummy stack temporarily stores containers as an ordinary stack. However, the dummy stack must be emptied at the end of pre-marshalling. In this paper, target-guided algorithms are proposed to handle both the classical CPMP and new CPMPDS. All the proposed algorithms guarantee termination. Experimental results in terms of the CPMP show that the proposed algorithms surpass the state-of-the-art algorithm.     

On Sampling Error in Market Share Estimates*

The relative error in the usual estimator of a brand's market share is reformulated in terms of marketing parameters. Such error is shown to be influenced in an important way by market penetration, as well as by variation in brand and product category volume. Of particular interest is the result that the relative error does not depend on the actual share level. Using data from a marketing research firm that supplies share estimates to the health products industry, we find that the relative error may be substantial even when a large sample is available. An upper bound on this relative error is obtained using marketing parameters that can frequently be measured using industry data and a company's internal records, thus reducing the level of judgmental input required in the planning of sample surveys.     

On Inventory Abatement via Manufacturing Randomness Reductions*

Under a continuous improvement framework, the policy of abating inventory via reductions in manufacturing randomness is considered. To explore this policy, a model of a real-world production-inventory system is developed, tested, and studied. The results suggest that manufacturing randomness reductions, even substantial ones, may not necessarily lead to inventory abatement, and paradoxically may lead sometimes to an inventory increase. In these cases, however, manufacturing randomness reductions will translate into higher customer service levels.     

On the Repeated Test-Retest Reliability of the End-User Computing Satisfaction Instrument: A Comment*

This comment extends the test-retest reliability of the end-user computing satisfaction (EUCS) instrument by Torkzadeh and Doll [10]. Whereas Torkzadeh and Doll [10] reportedstability for two hour and two week EUCS test-retest reliability, we investigate the test-retest reliability of the EUCS instrument at two points in time, separated by a two yearinterval. We assess the end user computing satisfaction of personal computer, as well as mainframe, administrative end users in a large public organization. The results of the repeated test-retest using differing application platforms add further support for the reliability of the EUCS measure and highlight some areas of concern for managers of information systems.     

L(j,k)- and circular L(j,k)-labellings for the products of complete graphs

Let j and k be two positive integers with j≥k. An L(j,k)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between labels of any two adjacent vertices is at least j, and the difference between labels of any two vertices that are at distance two apart is at least k. The minimum range of labels over all L(j,k)-labellings of a graph G is called the λ _j,k -number of G, denoted by λ _j,k (G). A σ(j,k)-circular labelling with span m of a graph G is a function f:V(G)→{0,1,…,m−1} such that |f(u)−f(v)| _m ≥j if u and v are adjacent; and |f(u)−f(v)| _m ≥k if u and v are at distance two apart, where |x| _m =min {|x|,m−|x|}. The minimum m such that there exists a σ(j,k)-circular labelling with span m for G is called the σ _j,k -number of G and denoted by σ _j,k (G). The λ _j,k -numbers of Cartesian products of two complete graphs were determined by Georges, Mauro and Stein ((2000) SIAM J Discret Math 14:28–35). This paper determines the λ _j,k -numbers of direct products of two complete graphs and the σ _j,k -numbers of direct products and Cartesian products of two complete graphs. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. This work is partially supported by FRG, Hong Kong Baptist University, Hong Kong; NSFC, China, grant 10171013; and Southeast University Science Foundation grant XJ0607230.     

On Extending Russell and Krajewski's Algorithm for Economic Purchase Order Quantities*

Russell and Krajewski presented an optimal purchase order quantity algorithm that considered the effect of the transportation rate structure for less-than-truckload (LTL) shipments. The authors applied the Russell and Krajewski algorithm to a variety of freight classes and lengths-of-haul. Anomalous cases were found in which the freight rate schedule, when used with the suggested algorithm, resulted in incorrect order size decisions. In this comment, the authors consider the impact of these anomalies on the optimal order quantity and associated total costs. A procedure is presented to adjust the Russell and Krajewski algorithm to arrive at the optimal purchase order quantity and the lowest total annual cost.     

Key Characteristics of the Large Innovating Firm*

Large innovating firms are a major source of the world's technology, and in the 20th century have shown great resilience in absorbing successive waves of radical innovations. The key characteristics of these firms derive from the properties of their innovative activities. First, given the specific, differentiated and cumulative nature of technological development, the range of possible choices about both product and processed technologies open to the firm depends on its accumulated competence. Second, given functional and professional specialization, the implementation of technological choices requires organization and orchestration across disciplinary, functional and divisional boundaries. Third, given cumulative development and uncertainty, the improvement of these competences requires continuous and collective learning. Fourth, in the light of these characteristics, systems for allocating resources must take into account the benefits of learning by doing, as well as the benefits of outcomes. As a consequence, the technical function in large firms involves not just the implementation of innovations, but also the definition of appropriate divisional objectives and boundaries, the exploration of radical technologies, and the formation of technological expectations about the future.     

Generalizing the Announced Price Increase Problem*

This paper generalizes the announced price increase problem to consider a variety of practical concerns arising out of applications ranging from foreign exchange fluctuations to upper limits on the purchase of discounted supermarket items. These include limitations on the amount that can be purchased at the old price and/or on the length of the grace period, within which buyers may take advantage of this lower price. These constraints give rise to 16 possible situations. For each situation purchasing and inventory decision rules are developed. A numerical example is discussed to highlight the main features of the models.