4C3 AN ADAPTIVE MEMORY LAGRANGIAN HEURISTIC ALGORITHM BASED ON THE SET COVERING APPROACH FOR THE MULTICUT PROBLEM
スポンサーリンク
概要
- 論文の詳細を見る
The multicut problem is one of the representative combinatorial optimization problems, which is known to be NP-hard when the number of terminal pairs is three or more. The multicut problem can be reduced to the set covering problem (SCP) by enumerating paths between each terminal pair and considering necessary edges to cut such paths. We propose a heuristic algorithm based on this idea, in which a Lagrangian heuristic algorithm with adaptive memory mechanism is used to obtain approximate solutions of SCP. The algorithm maintains a manageable number of paths because it is impractical to enumerate all paths between each terminal pair. Through computational experiments, we confirm the effectiveness of our algorithm.
- 一般社団法人日本機械学会の論文
- 2009-07-04
著者
-
ONO Takao
Department of Genetics, Institute for Developmental Research
-
Yagiura Mutsunori
Graduate School of Information Science, Nagoya University
-
Ono Takao
Department Of Communication Engineering Faculty Of Computer Science And System Engineering Okayama P
-
Kimoto Daisuke
NEC Corporation 2nd Computers Software Division
-
Hirata Tomio
Graduate School of Information Science Nagoya University
-
Hirata Tomio
Graduate School Of Engineering Nagoya University
-
Yagiura Mutsunori
Graduate School Of Information Science Nagoya University
-
Ono Takao
Department Of Biology Faculty Of Science Hirosaki University
関連論文
- Cloning and chromosomal mapping of the human gene of neuroglycan C (NGC), a neural transmembrane chondroitin sulfate proteoglycan with an EGF module
- 5B1 A GUIDED LOCAL SEARCH ALGORITHM BASED ON A FAST NEIGHBORHOOD SEARCH FOR THE IRREGULAR STRIP PACKING PROBLEM(Technical session 5B: Packing problem)
- Monopolar preparation of human lymphocytes for evaluation of the metaphase chromosome alignment
- 1C3 A HEURISTIC ALGORITHM FOR THE NODE CAPACITATED IN-TREE PACKING PROBLEM
- 4C3 AN ADAPTIVE MEMORY LAGRANGIAN HEURISTIC ALGORITHM BASED ON THE SET COVERING APPROACH FOR THE MULTICUT PROBLEM
- O-27. A new method of chromosome analysis in human diseases associated with the defects of chromosome assembly and segregation(Abstracts of the oral and poster presentations)
- O-20. Breakpoint analysis of a balanced translocation t(9;17)(q32;q12) associated with cleft lip and palate by FISH and DNA sequencing(Abstracts of the oral and poster presentations)
- Cytogenetic mapping of cosmid markers from a genomic library of the Chinese hamster by fluorescence in situ hybridization(Abstracts of the 48th Annual Meeting of the Society of Chromosome Research)
- Inapproximability of the Minimum Biclique Edge Partition Problem
- Inapproximability of the Edge-Contraction Problem(Discrete Mathematics and Its Applications)
- Key roles of condensins in mitotic chromosome assembly and segregation(The Society of Chromosome Research Award Lecture)
- Comparative gene mapping and chromosomal painting between the Chinese hamster and the mouse
- Refined Computations for Points of the Form 2kP Based on Montgomery Trick
- Karyotypes and Ag-NOR Variations in Japanese Vespertilionid Bats (Mammalia : Chiroptera)
- A Programming Language and its Implementation for a Mini-computer
- An Improved Algorithm for the Nearly Equitable Edge-Coloring Problem
- 3C1 AN LP-BASED ALGORITHM FOR SCHEDULING PREEMPTIVE AND/OR NON-PREEMPTIVE REAL-TIME TASKS
- On Approximation Algorithms for Coloring k-Colorable Graphs
- A Local Search Algorithm to Find a Scheduling Table for Real-Time Systems
- An LP-Based Algorithm for Scheduling Preemptive and/or Non-Preemptive Real-Time Tasks