On the approximability of the minimum strictly fundamental cycle basis problem

We consider the problem of finding a strictly fundamental cycle basis of minimum weight in the cycle space associated with an undirected connected graph G, where a nonnegative weight is assigned to each edge of G and the total weight of a basis is defined as the sum of the weights of all the cycles in the basis. Several heuristics have been proposed to tackle this NP-hard problem, which has some interesting applications. In this paper we show that this problem is APX-hard, even when restricted to unweighted graphs, and hence does not admit a polynomial-time approximation scheme, unless P=NP. Using a recent result on the approximability of lower-stretch spanning trees (Elkin et al. (2005) [7]), we obtain that the problem is approximable within O(log²nloglogn) for arbitrary graphs. We obtain tighter approximability bounds for dense graphs. In particular, the problem restricted to complete graphs admits a polynomial-time approximation scheme.     

Approximation algorithms for the minimum rainbow subgraph problem

We consider the minimum rainbow subgraph problem (MRS): given a graph G, whose edges are coloured with p colours. Find a subgraph F⊆G of G of minimum order and with p edges such that each colour occurs exactly once. For graphs with maximum degree Δ(G) there is a greedy polynomial-time approximation algorithm for the MRS problem with an approximation ratio of Δ(G). In this paper we present a polynomial-time approximation algorithm with an approximation ratio of for Δ≥2.     

New scaling algorithms for the assignment and minimum mean cycle problems

In this paper we suggest new scaling algorithms for the assignment and minimum mean cycle problems. Our assignment algorithm is based on applying scaling to a hybrid version of the recentauction algorithm of Bertsekas and the successive shortest path algorithm. The algorithm proceeds by relaxing the optimality conditions, and the amount of relaxation is successively reduced to zero. On a network with 2n nodes,m arcs, and integer arc costs bounded byC, the algorithm runs in O( m log(nC)) time and uses very simple data structures. This time bound is comparable to the time taken by Gabow and Tarjan's scaling algorithm, and is better than all other time bounds under thesimilarity assumption, i.e.,C = O(n ^k ) for somek. We next consider the minimum mean cycle problem. Themean cost of a cycle is defined as the cost of the cycle divided by the number of arcs it contains. Theminimum mean cycle problem is to identify a cycle whose mean cost is minimum. We show that by using ideas of the assignment algorithm in an approximate binary search procedure, the minimum mean cycle problem can also be solved in O( m lognC) time. Under the similarity assumption, this is the best available time bound to solve the minimum mean cycle problem.     

Exact algorithms for the Hamiltonian cycle problem in planar graphs

We construct an exact algorithm for the Hamiltonian cycle problem in planar graphs with worst case time complexity , where c is some fixed constant that does not depend on the instance. Furthermore, we show that under the exponential time hypothesis, the time complexity cannot be improved to .     

Greedy Differencing Edge-Contraction heuristic for the Max-Cut problem

The Max-Cut problem is a classical NP-hard problem where the objective is to partition the nodes of an edge-weighted graph in a way that maximizes the sum of edges between the parts. We present a greedy heuristic for solving Max-Cut that combines an Edge-Contraction heuristic with the Differencing Method. We compare the heuristic’s performance to other greedy heuristics using a large and diverse set of problem instances.     

Genetic algorithms for the 2-page book drawing problem of graphs

The minimisation of edge crossings in a book drawing of a graph is one of the important goals for a linear VLSI design, and the 2-page crossing number of a graph provides an upper bound for the standard planar crossing number. We design genetic algorithms for the 2-page drawings, and test them on the benchmark test suits, Rome graphs and Random Connected Graphs. We also test some circulant graphs, and get better results than previously presented in the literature. Moreover, we formalise three conjectures for certain kinds of circulant graphs,supported by our experimental results.     

Geometric algorithms for the minimum cost assignment problem

We consider the minimum-cost λ-assignment problem, which is equivalent to the minimum-weight one-to-many matching problem on a complete bipartite graph Γ = (A, B), where A and B have n and k nodes (n ? k), respectively. Formulating the problem geometrically, we given an O(kn + k^2.5n^0.5 log^1.5 n) time randomized algorithm, which is better than the existing O(kn² + n² log n) time algorithm if n > k log k.     

Approximated algorithms for the minimum dilation triangulation problem

The complexity status of the minimum dilation triangulation (MDT) problem for a general point set is unknown. Therefore, we focus on the development of approximated algorithms to find high quality triangulations of minimum dilation. For an initial approach, we design a greedy strategy able to obtain approximate solutions to the optimal ones in a simple way. We also propose an operator to generate the neighborhood which is used in different algorithms: Local Search, Iterated Local Search, and Simulated Annealing. Besides, we present an algorithm called Random Local Search where good and bad solutions are accepted using the previous mentioned operator. For the experimental study we have created a set of problem instances since no reference to benchmarks for these problems were found in the literature. We use the sequential parameter optimization toolbox for tuning the parameters of the SA algorithm. We compare our results with those obtained by the OV-MDT algorithm that uses the obstacle value to sort the edges in the constructive process. This is the only available algorithm found in the literature. Through the experimental evaluation and statistical analysis, we assess the performance of the proposed algorithms using this operator.     

Heuristic algorithms for a complex parallel machine scheduling problem

In this work we present a new scheduling model for parallel machines, which extends the multiprocessor scheduling problem with release times for minimizing the total tardiness, and also extends the problem of vehicle routing with time windows. This new model is motivated by a resource allocation problem, which appears in the service sector. We present two class of heuristic algorithms for the solution of the problem, the first class is a class of greedy algorithms, the second class is based on the solutions of linear assignment problems. Furthermore we give a rescheduling algorithm, which improves a given feasible solution of the problem. This research has been supported by the Hungarian National Foundation for Scientific Research, Grant T046405.     

简单图圈基长度的最大值

图的圈基是图的一个重要结构,一个圈基的长度是该圈基中所有圈的长度之和,本讲座了简单图的圈基长度的最大值,得到了如下结果：设基圈数为k,顶点数为n的简单图的圈基长度最大值为C^*,i)若k≥4且n ≥k 2时,C^*-kn;Ⅱ）若k=2,3,则对任意n≥4,C^*=kn-1,Ⅲ）若n(n≥5）为奇数,则对k(k≥4）的所有可能值,C^*=kn。     

On the existence of cycle frames and almost resolvable cycle systems

Suppose H is a complete m-partite graph K_m(n₁,n₂,…,n_m) with vertex set V and m independent sets G₁,G₂,…,G_m of n₁,n₂,…,n_m vertices respectively. Let G={G₁,G₂,…,G_m}. If the edges of λH can be partitioned into a set C of k-cycles, then (V,G,C) is called a k-cycle group divisible design with index λ, denoted by (k,λ)-CGDD. A (k,λ)-cycle frame is a (k,λ)-CGDD (V,G,C) in which C can be partitioned into holey 2-factors, each holey 2-factor being a partition of V?G_i for some G_i∈G. Stinson et al. have resolved the existence of (3,λ)-cycle frames of type g^u. In this paper, we show that there exists a (k,λ)-cycle frame of type g^u for k∈{4,5,6} if and only if , , u≥3 when k∈{4,6}, u≥4 when k=5, and (k,λ,g,u)≠(6,1,6,3). A k-cycle system of order n whose cycle set can be partitioned into (n−1)/2 almost parallel classes and a half-parallel class is called an almost resolvable k-cycle system, denoted by k-ARCS(n). Lindner et al. have considered the general existence problem of k-ARCS(n) from the commutative quasigroup for . In this paper, we give a recursive construction by using cycle frames which can also be applied to construct k-ARCS(n)s when . We also update the known results and prove that for k∈{3,4,5,6,7,8,9,10,14} there exists a k-ARCS(2kt+1) for each positive integer t with three known exceptions and four additional possible exceptions.     

The formulae and algorithms for Lagrange-power basis transformation and Lagrange-Newton transformation

The interpolation polynomials based on Lagrange, Newton and power basis play important roles in applied mathematics, computing method and many other emerging applications. In this paper, we present some coordinate transformation formulae and algorithms as demonstrated below. Firstly, we put forward the formulae of the Lagrange-power basis transformation and its inverse transformation, and as a byproduct, we provide a new method to arrive at the inversion of the Vandermonde matrix. Secondly, we give the formulae of Lagrange-Newton transformation and its inverse transformation. Moreover, we construct related algorithms of Lagrange-power basis transformation, Lagrange-Newton transformation and their inverse transformations.     

Using genetic algorithms for the coordinated scheduling problem of a batching machine and two-stage transportation

This paper considers a coordinated scheduling problem. For the first-stage transportation there is a crane available to transport the product from the warehouse to a batching machine. For the second-stage transportation there is a vehicle available to deliver the completed jobs from the machine shop floor to the customer. The coordinated scheduling problem of production and transportation deals with sequencing the transportation of the jobs and combining them into batches to be processed. The problem of minimizing the sum of the makespan and the total setup cost was proven by Tang and Gong [1] to be strongly NP-hard. This paper proposes two genetic algorithm (GA) approaches for this scheduling problem, with different result representations. The experimental results demonstrate that a regular GA and a modified GA (MGA) can find near-optimal solutions within an acceptable amount of computational time. Among the two proposed metaheuristic approaches, the MGA is superior to the GA both in terms of computing time and the quality of the solution.     

An asymptotic solution to the cycle decomposition problem for complete graphs

Let m₁,m₂,…,mt be a list of integers. It is shown that there exists an integer N such that for all n?N, the complete graph of order n can be decomposed into edge-disjoint cycles of lengths m₁,m₂,…,mt if and only if n is odd, 3?mi?n for i=1,2,…,t, and . In 1981, Alspach conjectured that this result holds for all n, and that a corresponding result also holds for decompositions of complete graphs of even order into cycles and a perfect matching.     

Variable neighborhood search for minimum cost berth allocation

The berth allocation problem is to allocate space along the quayside to incoming ships at a container terminal in order to minimize some objective function. We consider minimization of total costs for waiting and handling as well as earliness or tardiness of completion, for all ships. We assume ships can arrive at any given time, i.e., before or after the berths become available. The resulting problem, which subsumes several previous ones, is expressed as a linear mixed 0–1 program. As it turns out to be too time-consuming for exact solution of instances of realistic size, a Variable Neighborhood Search (VNS) heuristic is proposed, and compared with Multi-Start (MS), a Genetic Search algorithm (GA) and a Memetic Search algorithm (MA). VNS provides optimal solutions for all instances solved to optimality in a previous paper of the first two authors and outperforms MS, MA and GA on large instances.     

Rank-two update algorithms for the minimum volume enclosing ellipsoid problem

We consider the problem of computing a (1+ε)-approximation to the minimum volume enclosing ellipsoid (MVEE) of a given set of m points in R ⁿ . Based on the idea of sequential minimal optimization (SMO) method, we develop a rank-two update algorithm. This algorithm computes an approximate solution to the dual optimization formulation of the MVEE problem, which updates only two weights of the dual variable at each iteration. We establish that this algorithm computes a (1+ε)-approximation to MVEE in O(mn ³/ε) operations and returns a core set of size O(n ²/ε) for ε∈(0,1). In addition, we give an extension of this rank-two update algorithm. Computational experiments show the proposed algorithms are very efficient for solving large-scale problem with a high accuracy.     

Modified algorithms for the minimum volume enclosing axis-aligned ellipsoid problem

Consider the problem of computing a (1+?)-approximation to the minimum volume axis-aligned ellipsoid (MVAE) enclosing a set of m points in Rⁿ. We first provide an extension and improvement to algorithm proposed in Kumar and Y?ld?r?m (2008) [5] (the KY algorithm) for the MVAE problem. The main challenge of the MVAE problem is that there is no closed form solution in the line search step (beta). Therefore, the KY algorithm proposed a certain choice of beta that leads to their complexity and core set results in solving the MVAE problem. We further analyze the line search step to derive a new beta, relying on an analysis of up to the fourth order derivative. This choice of beta leads to the improved complexity and core set results. The second modification is given by incorporating “away steps” into the first one at each iteration, which obtains the same complexity and core set results as the first one. In addition, since the second modification uses the idea of “dropping points”, it has the potential to compute smaller core sets in practice. Some numerical results are given to show the efficiency of the modified algorithms.     

Experimental evaluation of simulated annealing algorithms for the time-cost trade-off problem

This paper evaluates variants of a simulated annealing algorithm which solve the total cost minimization problem in activity networks in the case that discrete time-cost execution modes are allowed on the project activities. This problem is a special case of the well known discrete time-cost trade-off problem (DTCTP). Based on a sample of randomly generated activity networks, formal tests of statistical significance are utilized to test both the quality of solutions and the time efficiency of algorithms versus problem factors. A procedure issued from the extreme values statistics is also applied on problem instances in order to determine, on the one hand, the confidence interval estimate of the optimum solution for each algorithm and, on the other hand, when to stop the running of an algorithm.     

Two phase algorithms for the bi-objective assignment problem

In this paper, we present several algorithms for the bi-objective assignment problem. The algorithms are based on the two phase method, which is a general technique to solve multi-objective combinatorial optimisation (MOCO) problems.     

An ensemble of discrete differential evolution algorithms for solving the generalized traveling salesman problem

In this paper, an ensemble of discrete differential evolution algorithms with parallel populations is presented. In a single populated discrete differential evolution (DDE) algorithm, the destruction and construction (DC) procedure is employed to generate the mutant population whereas the trial population is obtained through a crossover operator. The performance of the DDE algorithm is substantially affected by the parameters of DC procedure as well as the choice of crossover operator. In order to enable the DDE algorithm to make use of different parameter values and crossover operators simultaneously, we propose an ensemble of DDE (eDDE) algorithms where each parameter set and crossover operator is assigned to one of the parallel populations. Each parallel parent population does not only compete with offspring population generated by its own population but also the offspring populations generated by all other parallel populations which use different parameter settings and crossover operators. As an application area, the well-known generalized traveling salesman problem (GTSP) is chosen, where the set of nodes is divided into clusters so that the objective is to find a tour with minimum cost passing through exactly one node from each cluster. The experimental results show that none of the single populated variants was effective in solving all the GTSP instances whereas the eDDE performed substantially better than the single populated variants on a set of problem instances. Furthermore, through the experimental analysis of results, the performance of the eDDE algorithm is also compared against the best performing algorithms from the literature. Ultimately, all of the best known averaged solutions for larger instances are further improved by the eDDE algorithm.