On sorting by 3-bounded transpositions

Heath and Vergara [Sorting by short block moves, Algorithmica 28 (2000) 323-352] proved the equivalence between sorting by 3-bounded transpositions and sorting by correcting skips and correcting hops. This paper explores various algorithmic as well as combinatorial aspects of correcting skips/hops, with the aim of understanding 3-bounded transpositions better.We show that to sort any permutation via correcting hops and skips, ⌊n/2⌋ correcting skips suffice. We also present a tighter analysis of the approximation algorithm of Heath and Vergara, and a possible simplification. Along the way, we study the class H_n of those permutations of S_n which can be sorted using correcting hops alone, and characterize large subsets of this class. We obtain a combinatorial characterization of the set G_n⊆S_n of all correcting-hop-free permutations, and describe a linear-time algorithm to optimally sort such permutations. We also show how to efficiently sort a permutation with a minimum number of correcting moves.     

Improving the algorithm of Bafna and Pevzner for the problem of sorting by transpositions: a practical approach

In computational biology, genome rearrangements is a field in which we investigate the combinatorial problem of sorting by transpositions. This problem consists in finding the minimum number of transpositions (mutational event) that transform a chromosome into another. Bafna and Pevzner [SIAM J. 11 (2) (1998) 224–240] proposed a 1.5-approximation algorithm to solve this problem, using a structure called cycle graph. In this work, we first present results that allowed us to implement their algorithm, maintaining the 1.5-approximation ratio. The present implementation runs in O(n³) time complexity, noting that we created a data structure to store the cycle graph in memory in O(n) time complexity. The results obtained from the program allowed us to propose heuristics, that further improved the performance of the original algorithm. Comparing our experimental results with the best results published so far, we achieved better performance. Besides, we developed a program to visualize the cycle graphs and the transpositions indicated by the algorithm. This work targets to contribute for discovering the complexity of the problem of sorting by transpositions, which remains open.     

An approximation algorithm for the pickup and delivery vehicle routing problem on trees

This paper presents an approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot where there are two types of demands, pickup demand and delivery demand. Customers are located on nodes of the tree, and each customer has a positive demand of pickup and/or delivery.Demands of customers are served by a fleet of identical vehicles with unit capacity. Each vehicle can serve pickup and delivery demands. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. In each tour, a vehicle begins at the depot with certain amount of goods for delivery, visits a subset of the customers in order to deliver and pick up goods and returns to the depot. At any time during the tour, a vehicle must always satisfy the capacity constraint, i.e., at any time the sum of goods to be delivered and that of goods that have been picked up is not allowed to exceed the vehicle capacity. We propose a 2-approximation algorithm for the problem.     

A branch and bound algorithm for the maximum clique problem

We present a branch and bound algorithm for the maximum clique problem in arbitrary graphs. The main part of the algorithm consists in the determination of upper bounds by graph colorings. Using a modification of a known graph coloring method called DSATUR we simultaneously derive lower and upper bounds for the clique number.

---

Zusammenfassung Wir stellen einen Branch and Bound Algorithmus für das Maximum Clique Problem in einem beliebigen Graphen vor. Das Hauptaugenmerk richtet sich dabei auf die Bestimmung oberer Schranken mit Hilfe von Färbungen von Graphen. Es wird eine Modifikation einer bekannten Färbungsmethode, genannt DSATUR, verwendet, mit der sich gleichzeitig obere und untere Schranken für die Cliquezahl erstellen lassen.

     

An approximation result for free discontinuity functionals by means of non‐local energies

We approximate, in the sense of Γ‐convergence, free discontinuity functionals with linear growth by a sequence of non‐local integral functionals depending on the average of the gradient on small balls. The result extends to a higher dimension what is already proved in (Ann. Mat. Pura Appl. 2007; 186 (4): 722–744), where there is the proof of the general one‐dimensional case, and in (ESAIM Control Optim. Calc. Var. 2007; 13 (1):135–162), where the n‐dimensional case with ?=Id is treated. Moreover, we investigate whether it is possible to approximate a given free discontinuity functional by means of non‐local energies. Copyright © 2008 John Wiley & Sons, Ltd.