References of "RAIRO : Operations Research = Recherche Opérationnelle"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailApproximation algorithms for the design of SDH/SONET networks
Brauner, Nadia; Crama, Yves ULg; Finke, Gerd et al

in RAIRO : Operations Research = Recherche Opérationnelle (2003), 37(4, OCT-DEC), 235-247

In this paper, a graph partitioning problem that arises in the design of SONET/SDH networks is defined and formalized. Approximation algorithms with performance guarantees are presented. To solve this ... [more ▼]

In this paper, a graph partitioning problem that arises in the design of SONET/SDH networks is defined and formalized. Approximation algorithms with performance guarantees are presented. To solve this problem efficiently in practice, fast greedy algorithms and a tabu-search method are proposed and analyzed by means of an experimental study. [less ▲]

Detailed reference viewed: 67 (6 ULg)
Full Text
Peer Reviewed
See detailApproximation algorithms for integer covering problems via greedy column generation
Crama, Yves ULg; Van de Klundert, Joris

in RAIRO : Operations Research = Recherche Opérationnelle (1994), 28

Many combinatorial optimization problems can be formulated as covering problems. In some cases, this covering formulation is not polynomial in the input size of the original problem. In order to solve the ... [more ▼]

Many combinatorial optimization problems can be formulated as covering problems. In some cases, this covering formulation is not polynomial in the input size of the original problem. In order to solve the problem approximately one can apply the greedy algorithm to the covering formulation. In this case, the column generation subproblem is to determine which column the greedy algorithm chooses. This problem might be NP-hard in itself. We propose a modification of the greedy algorithm in which the column generation subproblem is solved approximately, within a factor α. We derive upper bounds for the worst case ratio of this algorithm and related polynomial approximation algorithms. [less ▲]

Detailed reference viewed: 16 (1 ULg)