1,721,118 research outputs found
Improved Approximation for Breakpoint Graph Decomposition and Sorting by Reversals
Full text linkSorting by Reversals (SBR) is one of the most widely studied models of genome rearrangements in computational molecular biology. At present, 3/2 is the best known approximation ratio achievable in polynomial time for SBR. A very closely related problem, called Breakpoint Graph Decomposition (BGD), calls for a largest collection of edge disjoint cycles in a suitably-defined graph. It has been shown that for almost all instances SBR is equivalent to BGD, in the sense that any solution of the latter corresponds to a solution of the former having the same value. In this paper, we show how to improve the approximation ratio achievable in polynomial time for BGD, from the previously known to \frac{33}{23}+\eps for any \eps>0. Our result uses the best known approximation algorithms for Stable Set on graphs with maximum degree 4 as well as for Set Packing where the maximum size of a set is 6. Any improvement in the ratio achieved by these approximation algorithms will yield an automatic improvement of our result
On the 2-Dimensional Knapsack Problem
No full textWe address the two-dimensional Knapsack Problem (2KP), aimed at packing a maximum-prot subset of rectangles selected from a given set into another rectangle. We consider the natural relaxation of 2KP given by the one-dimensional KP with item weights equal to the rectangle areas, proving the worst-case performance of the associated upper bound, and present and compare computationally four exact algorithms based on the above relaxation, showing their eectiveness
Robustness in train timetabling
No full textWe propose a Lagrangian-based heuristic approach to obtain robust solutions to the Train Timetabling Problem (TTP) on a corridor (i.e. a single one-way line connecting two major stations). Roughly speaking, we define a solution to be robust if it allows to avoid delay propagation as much as possible. In particular, in the planning phase that we are considering the aim is to build timetables characterized by buffer times that can be used to absorb possible delays occurring at an operational level. In the TTP, we are given a set of stations S along the corridor, a set of trains T, and for each train an ideal timetable (i.e. the timetable suggested by the Train Operator). In the nominal TTP the aim is to change the ideal timetables for the trains as little as possible, while satisfying the track capacity constraints consisting of: - departure constraints (imposing a minimum headway between two consecutive departures from a station); - arrival constraints (imposing a minimum headway between two consecutive arrivals at a station); - overtaking constraints (avoiding overtaking between consecutive stations, since we are considering a single one-way line)
Uncommon Dantzig-Wolfe Reformulation for the Temporal Knapsack Problem
No full textWe study a natural generalization of the knapsack problem, in which each item exists only for a given time interval. One has to select a subset of the items (as in the classical case), guaranteeing that for each time instant, the set of existing selected items has total weight no larger than the knapsack capacity. We focus on the exact solution of the problem, noting that prior to our work, the best method was the straightforward application of a general-purpose solver to the natural integer linear programming formulation. Our results indicate that much better results can be obtained by using the same general-purpose solver to tackle a nonstandard Dantzig-Wolfe reformulation in which subproblems are associated with groups of constraints. This is also interesting because the more natural Dantzig-Wolfe reformulation of single constraints performs extremely poorly in practice
- …
