Lexicographically minimizing axial motions for the Euclidean TSP

A variant of the Euclidean traveling salesman problem (TSP) is defined and studied. In the three-dimensional space, the objective function is to lexicographically minimize the x-moves, then the y-moves and finally the z-moves. The 2D and 3D cases are first studied and solved as a shortest path problem. Then the approach is generalized to the d-dimensional case.     

Half integer extreme points in the linear relaxation of the 2-edge-connected subgraph polyhedron

This paper studies the graphs for which the linear relaxation of the 2-connected spanning subgraph polyhedron has integer or half-integer extreme points. These graphs are called quasi-integer. For these graphs, the linear relaxation of the k-edge connected spanning subgraph polyhedron is integer for all k=4r, r≥1. The class of quasi-integer graphs is closed under minors and contains for instance the class of series-parallel graphs. We discuss some structural properties of graphs which are minimally non quasi-integer graphs, then we examine some basic operations which preserve the quasi-integer property. Using this, we show that the subdivisions of wheels are quasi-integer.     

A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem

This paper addresses a constrained two-dimensional (2D), non-guillotine restricted, packing problem, where a fixed set of small rectangles has to be placed into a larger stock rectangle so as to maximize the value of the rectangles packed. The algorithm we propose hybridizes a novel placement procedure with a genetic algorithm based on random keys. We propose also a new fitness function to drive the optimization. The approach is tested on a set of instances taken from the literature and compared with other approaches. The experimental results validate the quality of the solutions and the effectiveness of the proposed algorithm.     

Incremental Facility Location Problem and Its Competitive Algorithms

We consider the incremental version of the k-Facility Location Problem, which is a common generalization of the facility location and the k-median problems. The objective is to produce an incremental sequence of facility sets F ₁?F ₂?????F _n , where each F _k contains at most k facilities. An incremental facility sequence or an algorithm producing such a sequence is called c -competitive if the cost of each F _k is at most c times the optimum cost of corresponding k-facility location problem, where c is called competitive ratio. In this paper we present two competitive algorithms for this problem. The first algorithm produces competitive ratio 8α, where α is the approximation ratio of k-facility location problem. By recently result (Zhang, Theor. Comput. Sci. 384:126–135, 2007), we obtain the competitive ratio \(16+8\sqrt{3}+\epsilon\). The second algorithm has the competitive ratio Δ+1, where Δ is the ratio between the maximum and minimum nonzero interpoint distances. The latter result has its self interest, specially for the small metric space with Δ≤8α?1.     

Bounding the total domination subdivision number of a graph in terms of its order

The total domination subdivision number \(\mathrm{sd}_{\gamma _{t}}(G)\) of a graph G is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper we prove that \(\mathrm{sd}_{\gamma_{t}}(G)\leq \lfloor\frac{2n}{3}\rfloor\) for any simple connected graph G of order n≥3 other than K ₄. We also determine all simple connected graphs G with \(\mathrm{sd}_{\gamma_{t}}(G)=\lfloor\frac{2n}{3}\rfloor\).     

Error-correcting pooling designs associated with the dual space of unitary space and ratio efficiency comparison

In this paper, we construct a d ^z -disjunct matrix with subspaces in a dual space of Unitary space , then give its several properties. As the smaller the ratio efficiency is, the better the pooling design is. We compare the ratio efficiency of this construction with others, such as the ratio efficiency of the construction of set, the general space and the dual space of symplectic space. In addition, we find it smaller under some conditions. Supported by NSF of the Education Department of Hebei Province (2007127) and NSF of Hebei Normal University (L2004B04).     

Approximation algorithms for multicast routing in ad hoc wireless networks

Energy efficient multicast problem is one of important issues in ad hoc networks. In this paper, we address the energy efficient multicast problem for discrete power levels in ad hoc wireless networks. The problem of our concern is: given n nodes deployed over 2-D plane and each node v has l(v) transmission power levels and a multicast request (s,D) (clearly, when D is V∖{s}, the multicast request is a broadcast request), how to find a multicast tree rooted at s and spanning all destinations in D such that the total energy cost of the multicast tree is minimized. We first prove that this problem is NP-hard and it is unlikely to have an approximation algorithm with performance ratio ρlnn(ρ<1). Then, we propose a general algorithm for the multicast/broadcast tree problem. And based on the general algorithm, we propose an approximation algorithm and a heuristics for multicast tree problem. Especially, we also propose an efficient heuristic for broadcast tree problem. Simulations ensure our algorithms are efficient.     

A hybrid beam search looking-ahead algorithm for the circular packing problem

In this paper, we study the circular packing problem. Its objective is to pack a set of n circular pieces into a rectangular plate R of fixed dimensions L×W. Each piece’s type i, i=1,…,m, is characterized by its radius r _i and its demand b _i . The objective is to determine the packing pattern corresponding to the minimum unused area of R for the circular pieces placed. This problem is solved by using a hybrid algorithm that adopts beam search and a looking-ahead strategy. A node at a level ℓ of the beam-search tree contains a partial solution corresponding to the circles already placed inside R. Each node is then evaluated using a looking-ahead strategy, based on the minimum local-distance heuristic, by computing the corresponding complete solution. The nodes leading to the best solutions at level ℓ are then chosen for branching. A multi-start strategy is also considered in order to diversify the search space. The computational results show, on a set of benchmark instances, the effectiveness of the proposed algorithm.     

Semi-online scheduling on two uniform machines with the known largest size

This paper investigates semi-online scheduling on two uniform machines with the known largest size. Denote by s _j the speed of each machine, j=1,2. Assume 0<s ₁≤s ₂, and let s=s ₂/s ₁ be the speed ratio. First, for the speed ratio \(s\in [1,\sqrt{2}]\), we present an optimal semi-online algorithm \(\mathcal{LSMP}\) with the competitive ratio \(\mathrm{max}\{\frac {2(s+1)}{2s+1},s\}\). Second, we present a semi-online algorithm \(\mathcal{HSMP}\). And for \(s\in(\sqrt{2},1+\sqrt{3})\), the competitive ratio of \(\mathcal{HSMP}\) is strictly smaller than that of the online algorithm \(\mathcal{LS}\). Finally, for the speed ratio s≥s ^*≈3.715, we show that the known largest size cannot help us to design a semi-online algorithm with the competitive ratio strictly smaller than that of \(\mathcal{LS}\). Moreover, we show a lower bound for \(s\in(\sqrt{2},s^{*})\).     

Lower bounds and a tabu search algorithm for the minimum deficiency problem

An edge coloring of a graph G=(V,E) is a function c:E→ℕ that assigns a color c(e) to each edge e∈E such that c(e)≠c(e′) whenever e and e′ have a common endpoint. Denoting S _v (G,c) the set of colors assigned to the edges incident to a vertex v∈V, and D _v (G,c) the minimum number of integers which must be added to S _v (G,c) to form an interval, the deficiency D(G,c) of an edge coloring c is defined as the sum ∑ _v∈V D _v (G,c), and the span of c is the number of colors used in c. The problem of finding, for a given graph, an edge coloring with a minimum deficiency is NP-hard. We give new lower bounds on the minimum deficiency of an edge coloring and on the span of edge colorings with minimum deficiency. We also propose a tabu search algorithm to solve the minimum deficiency problem and report experiments on various graph instances, some of them having a known optimal deficiency.     

On sorting unsigned permutations by double-cut-and-joins

The problem of sorting unsigned permutations by double-cut-and-joins (SBD) arises when we perform the double-cut-and-join (DCJ) operations on pairs of unichromosomal genomes without the gene strandedness information. In this paper we show it is a NP-hard problem by reduction to an equivalent previously-known problem, called breakpoint graph decomposition (BGD), which calls for a largest collection of edge-disjoint alternating cycles in a breakpoint graph. To obtain a better approximation algorithm for the SBD problem, we made a suitable modification to Lin and Jiang’s algorithm which was initially proposed to approximate the BGD problem, and then carried out a rigorous performance analysis via fractional linear programming. The approximation ratio thus achieved for the SBD problem is $\frac{17}{12}+\epsilon \approx 1.4167 +\epsilon$ , for any positive ε.     

On dual power assignment optimization for biconnectivity

Topology control is an important technology of wireless ad hoc networks to achieve energy efficiency and fault tolerance. In this paper, we study the dual power assignment problem for 2-edge connectivity and 2-vertex connectivity in the symmetric graphical model which is a combinatorial optimization problem from topology control technology.The problem is arisen from the following origin. In a wireless ad hoc network where each node can switch its transmission power between high-level and low-level, how can we establish a fault-tolerantly connected network topology in the most energy-efficient way? Specifically, the objective is to minimize the number of nodes assigned with high power and yet achieve 2-edge connectivity or 2-vertex connectivity.We addressed these optimization problems (2-edge connectivity and 2-vertex connectivity version) under the general graph model in (Wang et al. in Theor. Comput. Sci., 2008). In this paper, we propose a novel approximation algorithm, called Candidate Set Filtering algorithm, to compute nearly-optimal solutions. Specifically, our algorithm can achieve 3.67-approximation ratio for both 2-edge connectivity and 2-vertex connectivity, which improves the existing 4-approximation algorithms for these two cases.     

Constructing error-correcting pooling designs with symplectic space

We construct a family of error-correcting pooling designs with the incidence matrix of two types of subspaces of symplectic spaces over finite fields. We show that the new construction gives better ratio of efficiency compared with previously known three constructions associated with subsets of a set, its analogue over a vector space, and the dual spaces of a symplectic space.     

Improved floor-planning of graphs via adjacency-preserving transformations

Let G=(V,E) and G′=(V′,E′) be two graphs, an adjacency-preserving transformation from G to G′ is a one-to-many and onto mapping from V to V′ satisfying the following: (1) Each vertex v∈V in G is mapped to a non-empty subset \(\mathcal{A}(v)\subset V'\) in G′. The subgraph induced by \(\mathcal{A}(v)\) is a connected subgraph of G′; (2) if u≠v∈V, then \(\mathcal{A}(u)\cap\mathcal{A}(v)=\emptyset\); and (3) two vertices u and v are adjacent to each other in G if and only if subgraphs induced by \(\mathcal{A}(u)\) and \(\mathcal{A}(v)\) are connected in G′.In this paper, we study adjacency-preserving transformations from plane triangulations to irreducible triangulations (which are internally triangulated, with four exterior vertices and no separating triangles). As one shall see, our transformations not only preserve adjacency well, but also preserve the endowed realizers of plane triangulations well in the endowed transversal structures of the image irreducible triangulations, which may be desirable in some applications.We then present such an application in floor-planning of plane graphs. The expected grid size of the floor-plan of our linear time algorithm is improved to \((\frac{5n}{8}+O(1))\times (\frac{23n}{24}+O(1))\), though the worst case grid size bound of the algorithm remains \(\lfloor\frac{2n+1}{3}\rfloor\times(n-1)\), which is the same as the algorithm presented in Liao et al. (J. Algorithms 48:441–451, 2003).     

Separating sublinear time computations by approximate diameter

We study the problem of separating sublinear time computations via approximating the diameter for a sequence S=p ₁ p ₂ ⋅⋅⋅ p _n of points in a metric space, in which any two consecutive points have the same distance. The computation is considered respectively under deterministic, zero error randomized, and bounded error randomized models. We obtain a class of separations using various versions of the approximate diameter problem based on restrictions on input data. We derive tight sublinear time separations for each of the three computation models via proving that computation with O(n ^r ) time is strictly more powerful than that with O(n ^r−ε ) time, where r and ε are arbitrary parameters in (0,1) and (0,r) respectively. We show that, for any parameter r∈(0,1), the bounded error randomized sublinear time computation in time O(n ^r ) cannot be simulated by any zero error randomized sublinear time algorithm in o(n) time or queries; and the same is true for zero error randomized computation versus deterministic computation.     

Human Resource Development in Asia – Thriving on dynamism & change: Reflections from 2006 Asian HRD conference

This article discusses the experiences of the conference management team and the host (Universiti Putra Malaysia -UPM) of the Fifth Asian Conference of the Academy of Human Resource Development, held in Putrajaya, Malaysia from 2 to 5 December 2006. In reviewing the conference, the following sub-topics are used for organizing the contents of the article: HRD in Malaysia; conference theme & overview; participations/country representations and paper streams; keynote addresses; conference assessment; and conclusions. At the end, brief perspectives of the next Asian HRD conference to be held in China are also provided.     

An almost four-approximation algorithm for maximum weight triangulation

We consider the following planar maximum weight triangulation (MAT) problem: given a set of n points in the plane, find a triangulation such that the total length of edges in triangulation is maximized. We prove an $\Omega(\sqrt{n})$ lower bound on the approximation factor for several heuristics: maximum greedy triangulation, maximum greedy spanning tree triangulation and maximum spanning tree triangulation. We then propose the Spoke Triangulation algorithm, which approximates the maximum weight triangulation for points in general position within a factor of almost four in O(nlog?n) time. The proof is simpler than the previous work. We also prove that Spoke Triangulation approximates the maximum weight triangulation of a convex polygon within a factor of two.     

Saudization (Localization) – A critical review

Abstract

This paper introduces the concept of Saudization and critically reviews its existing and potential impacts and consequences. It identifies that Saudization has positively contributed to reducing the overall percentage of foreign labor. However, there have been some difficulties, such as a decline in competitiveness among regional business companies with respect to a business friendly environment, and reduced direct foreign investment, which influenced the reduction of the tax on foreign investors. Saudization should place importance on skill development among Saudi nationals by strengthening educational and vocational training, and providing time-specific incentives, rather than relying only on a quota system. Saudization should be implemented more through market forces and incentives. Collecting comprehensive information on the nature and magnitude of Saudi unemployment could be a first step in developing appropriate Saudization policies. This paper suggests appropriate coordination and consultation between the government, the private sector and the public at large, so that any policies on Saudization become more easily acceptable and executable in both the public and private sector.     

Fixed-parameter tractability of anonymizing data by suppressing entries

A popular model for protecting privacy when person-specific data is released is k -anonymity. A dataset is k-anonymous if each record is identical to at least (k−1) other records in the dataset. The basic k-anonymization problem, which minimizes the number of dataset entries that must be suppressed to achieve k-anonymity, is NP-hard and hence not solvable both quickly and optimally in general. We apply parameterized complexity analysis to explore algorithmic options for restricted versions of this problem that occur in practice. We present the first fixed-parameter algorithms for this problem and identify key techniques that can be applied to this and other k-anonymization problems.     

Efficient algorithms for the max k -vertex cover problem

Given a graph  \(G(V,E)\) of order  \(n\) and a constant \(k \leqslant n\) , the max  \(k\) -vertex cover problem consists of determining  \(k\) vertices that cover the maximum number of edges in  \(G\) . In its (standard) parameterized version, max  \(k\) -vertex cover can be stated as follows: “given  \(G,\) \(k\) and parameter  \(\ell ,\) does  \(G\) contain  \(k\) vertices that cover at least  \(\ell \) edges?”. We first devise moderately exponential exact algorithms for max  \(k\) -vertex cover, with time-complexity exponential in  \(n\) but with polynomial space-complexity by developing a branch and reduce method based upon the measure-and-conquer technique. We then prove that, there exists an exact algorithm for max  \(k\) -vertex cover with complexity bounded above by the maximum among  \(c^k\) and  \(\gamma ^{\tau },\) for some \(\gamma < 2,\) where  \(\tau \) is the cardinality of a minimum vertex cover of  \(G\) (note that \({\textsc {max}}\,\) k \({\textsc {\!-vertex cover}}{} \notin \mathbf{FPT}\) with respect to parameter  \(k\) unless \(\mathbf{FPT} = \mathbf{W[1]}\) ), using polynomial space. We finally study approximation of max  \(k\) -vertex cover by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch-up on polynomial inapproximability, by providing algorithms achieving, with worst-case running times importantly smaller than those needed for exact computation, approximation ratios unachievable in polynomial time.