Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Neural Computing and Applications
Erschienen in: Neural Computing and Applications 10/2018

19.09.2016 | Original Article

A restart local search algorithm for solving maximum set k-covering problem

verfasst von: Yiyuan Wang, Dantong Ouyang, Minghao Yin, Liming Zhang, Yonggang Zhang

Erschienen in: Neural Computing and Applications | Ausgabe 10/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The maximum set k-covering problem (MKCP) is a famous combinatorial optimization problem with widely many practical applications. In our work, we design a restart local search algorithm for solving MKCP, which is called RNKC. This algorithm effectively makes use of several advanced ideas deriving from the random restart mechanism and the neighborhood search method. RNKC designs a new random restart method to deal with the serious cycling problem of local search algorithms. Thanks to the novel neighborhood search method that allows a neighborhood exploration of as many feasible search areas as possible, the RNKC can obtain some greatly solution qualities. Comprehensive results on the classical instances show that the RNKC algorithm competes very favorably with a famous commercial solver CPLEX. In particular, it discovers some improved and great results and matches the same solution quality for some instances.
Vorheriger Artikel The use of local radial point interpolation method for solving two-dimensional linear fractional cable equation
Nächster Artikel Economic load dispatch problems with valve-point loading using natural updated harmony search

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
1.
Saha B, Getoor L (2009) On maximum coverage in the streaming model & application to multi-topic blog-watch. SDM 9:697–708
2.
Bautista J, Pereira J (2006) Modeling the problem of locating collection areas for urban waste management. An application to the metropolitan area of Barcelona. Omega 34(6):617–629CrossRef
3.
Chierichetti F, Kumar R, Tomkins A (2010) Max-cover in map-reduce. In: Proceedings of the 19th international conference on World wide web. ACM, 2010: 231–240
4.
Yu H, Yuan D (2013) Set coverage problems in a one-pass data stream. In: Proceedings of the 2013 SIAM international conference on data mining, pp 758-766
5.
Stergiou S, Tsioutsiouliklis K (2015) Set cover at web scale. In: Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, 2015: 1125–1133
6.
Dasgupta A, Ghosh A, Kumar R et al (2007) The discoverability of the web. In: Proceedings of the 16th international conference on World Wide Web. ACM, 2007: 421–430
7.
Yiyuan W, Jianan W (2016) An effective local search algorithm for a special hitting set problem. Transylv Rev 24(80):1–12
8.
Michael RG, David SJ (1979) Computers and intractability: a guide to the theory of NP-completeness. WH Free. Co., San FrMATH
9.
Li X, Yin M (2016) A particle swarm inspired cuckoo search algorithm for real parameter optimization. Soft Comput 20(4):1389–1413CrossRef
10.
Li X, Li M (2015) Multiobjective local search algorithm-based decomposition for multiobjective permutation flow shop scheduling problem. IEEE Trans Eng Manage 62(4):544–557CrossRef
11.
Zhang X, Li X, Wang J (2016) Local search algorithm with path relinking for single batch-processing machine scheduling problem. Neural Comput Appl. doi:10.​1007/​s00521-016-2339-z
12.
Li X, Yin M (2014) Self-adaptive constrained artificial bee colony for constrained numerical optimization. Neural Comput Appl 24(3–4):723–734CrossRef
13.
Li X, Wang J, Yin M (2014) Enhancing the performance of cuckoo search algorithm using orthogonal learning method. Neural Comput Appl 24(6):1233–1247CrossRef
14.
Li X, Zhang J, Yin M (2014) Animal migration optimization: an optimization algorithm inspired by animal migration behavior. Neural Comput Appl 24(7–8):1867–1877CrossRef
15.
Gao J, Wang JN, Yin MH (2015) Experimental analyses on phase transitions in compiling satisfiability problems. Sci China Inf Sci 58(3):1–11CrossRef
16.
17.
18.
Zhou Y, Zhang H, Li R et al (2016) Two local search algorithms for partition vertex cover problem. J Comput Theor Nanosci 13(1):743–751CrossRef
19.
20.
Marques-Silva JP, Sakallah KA (1999) GRASP: a search algorithm for propositional satisfiability. IEEE Trans Comput 48(5):506–521MathSciNetCrossRef
21.
Laguna M, Marti R (1999) GRASP and path relinking for 2-layer straight line crossing minimization. Inf J Comput 11(1):44–52CrossRefMATH
22.
Houck CR, Joines JA, Kay MG (1996) Comparison of genetic algorithms, random restart and two-opt switching for solving large location-allocation problems. Comput Oper Res 23(6):587–596CrossRefMATH
23.
Shin K, Jung J, Lee S et al (2015) BEAR: block elimination approach for random walk with restart on large graphs. In: Proceedings of the 2015 ACM SIGMOD international conference on management of data. ACM, 2015: 1571–1585
24.
Datta T, Srinidhi N, Chockalingam A et al (2010) Random-restart reactive tabu search algorithm for detection in large-MIMO systems. Commun Lett IEEE 14(12):1107–1109CrossRef
25.
26.
27.
28.
Ruizhi L, Shuli H, Yiyuan W, Minghao Y, A local search algorithm with tabu strategy and perturbation mechanism for generalized vertex cover problem. Neural Comput Appl. doi:10.​1007/​s00521-015-2172-9
29.
Cai S, Su K (2013) Local search for Boolean Satisfiability with configuration checking and subscore. Artif Intell 204:75–98CrossRefMATH
30.
Wang Y, Cai S, Yin M (2016) Two efficient local search algorithms for maximum weight clique problem. Thirtieth AAAI Conf Artif Intell, pp 805–811
31.
Wang Y, Yin M, Ouyang D et al (2016) A novel local search algorithm with configuration checking and scoring mechanism for the set k-covering problem. Int Trans Oper Res. doi:10.​1111/​itor.​12280 MATH
32.
Beasley JE (1990) OR-Library: distributing test problems by electronic mail. J Oper Res Soc 41(11):1069–1072CrossRef
33.
Balas E, Ho A (1980) Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study. Springer, Berlin HeidelbergMATH
34.
35.
36.
Gao C, Yao X, Weise T et al (2015) An efficient local search heuristic with row weighting for the unicost set covering problem. Eur J Oper Res 246(3):750–761MathSciNetCrossRefMATH
37.
Wang Y, Ouyang DT, Zhang L et al (1007) A novel local search for unicost set covering problem using hyperedge configuration checking and weight diversity. Sci China Inf Sci 2015:10
38.
Xia Z, Wang X, Sun X et al (2016) A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data. IEEE Trans Parallel Distrib Syst 27(2):340–352CrossRef
39.
40.
Zhangjie F, Xingming S, Qi L et al (2015) Achieving efficient cloud search services: multi-keyword ranked search over encrypted cloud data supporting parallel computing. IEICE Trans Commun 98(1):190–200
41.
Ren YJ, Shen J, Wang J et al (2015) Mutual verifiable provable data auditing in public cloud storage. J Internet Technol 16(2):317–323
42.
Tinghuai MA, Jinjuan Z, Meili T et al (2015) Social network and tag sources based augmenting collaborative recommender system. IEICE Trans Inf Syst 98(4):902–910
43.
Wen X, Shao L, Xue Y et al (2015) A rapid learning algorithm for vehicle classification. Inf Sci 295:395–406CrossRef
44.
45.
Xia Z, Wang X, Sun X et al (2014) Steganalysis of least significant bit matching using multi-order differences. Secur Commun Networks 7(8):1283–1291CrossRef
Metadaten
Titel
A restart local search algorithm for solving maximum set k-covering problem
verfasst von
Yiyuan Wang
Dantong Ouyang
Minghao Yin
Liming Zhang
Yonggang Zhang
Publikationsdatum
19.09.2016
Verlag
Springer London
Erschienen in
Neural Computing and Applications / Ausgabe 10/2018
Print ISSN: 0941-0643
Elektronische ISSN: 1433-3058
DOI
https://doi.org/10.1007/s00521-016-2599-7

Weitere Artikel der Ausgabe 10/2018

Neural Computing and Applications 10/2018 Zur Ausgabe

Original Article

Three-tier neural model for service provisioning over collaborative flying ad hoc networks

Original Article

The use of local radial point interpolation method for solving two-dimensional linear fractional cable equation

Original Article

Weighted pseudo-anti-periodic SICNNs with mixed delays

Original Article

A novel multilayer AAA model for integrated applications

Original Article

Estimation of nearshore wave transmission for submerged breakwaters using a data-driven predictive model

Original Article

A Hopfield neural network with multi-compartmental activation