Russian doll search for the Steiner triple covering problem

被引：6
|
作者：
Ostergard, Patric R. J. [1 ]
Vaskelainen, Vesa P. [1 ]
机构：
[1] Aalto Univ, Dept Commun & Networking, Aalto 00076, Finland
来源：
OPTIMIZATION LETTERS | 2011年 / 5卷 / 04期
基金：
芬兰科学院;
关键词：
Hitting set problem; Russian doll search; Set covering problem; Steiner triple system;
D O I：
10.1007/s11590-010-0225-7
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
Russian doll search is applied to finding maximum independent sets in hypergraphs, focusing on a particular subproblem of the hitting set problem, the Steiner triple covering problem. An instance denoted A (135) is solved considerably faster with Russian doll search than with integer linear programming and a state-of-the-art optimization tool (using otherwise a similar established approach to split the problem into subproblems). In addition, the improvement in speed makes it possible to carry out a search proving that all optimal solutions for A (135) are isomorphic.
引用
收藏
页码：631 / 638
页数：8
相关论文
共 50 条
  • [1] Russian doll search for the Steiner triple covering problem
    Patric R. J. Östergård
    Vesa P. Vaskelainen
    Optimization Letters, 2011, 5 : 631 - 638
  • [2] Maximum weight relaxed cliques and Russian Doll Search revisited
    Gschwind, Timo
    Irnich, Stefan
    Podlinski, Isabel
    DISCRETE APPLIED MATHEMATICS, 2018, 234 : 131 - 138
  • [3] An implementation of harmony search algorithm to the set covering problem
    Lin, Geng
    2015 11TH INTERNATIONAL CONFERENCE ON NATURAL COMPUTATION (ICNC), 2015, : 200 - 204
  • [4] The 3-way flower intersection problem for Steiner triple systems
    Amjadi, Hanieh
    Soltankhah, Nasrin
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2020, 22 (01)
  • [5] STEINER TRIPLE ALGEBRAS
    Gardner, B. J.
    ACTA MATHEMATICA UNIVERSITATIS COMENIANAE, 2021, 90 (01): : 27 - 42
  • [6] A Binary Cuckoo Search Algorithm for Solving the Set Covering Problem
    Soto, Ricardo
    Crawford, Broderick
    Olivares, Rodrigo
    Barraza, Jorge
    Johnson, Franklin
    Paredes, Fernando
    BIOINSPIRED COMPUTATION IN ARTIFICIAL SYSTEMS, PT II, 2015, 9108 : 88 - 97
  • [7] A variable neighborhood search algorithm for the multimode set covering problem
    Fabio Colombo
    Roberto Cordone
    Guglielmo Lulli
    Journal of Global Optimization, 2015, 63 : 461 - 480
  • [8] A variable neighborhood search algorithm for the multimode set covering problem
    Colombo, Fabio
    Cordone, Roberto
    Lulli, Guglielmo
    JOURNAL OF GLOBAL OPTIMIZATION, 2015, 63 (03) : 461 - 480
  • [9] Harmony Search Algorithm for Solving Set-Covering Problem
    Salas, Juan
    Crawford, Broderick
    Soto, Ricardo
    Gomez Rubio, Alvaro
    Jaramillo, Adrian
    Mansilla Villablanca, Sebastian
    Olguin, Eduardo
    TRENDS IN APPLIED KNOWLEDGE-BASED SYSTEMS AND DATA SCIENCE, 2016, 9799 : 917 - 930
  • [10] Enumerating Steiner triple systems
    Heinlein, Daniel
    Ostergard, Patric R. J.
    JOURNAL OF COMBINATORIAL DESIGNS, 2023, 31 (10) : 479 - 495
12345