DC FieldValueLanguage
dc.contributor.authorUrošević, Draganen
dc.contributor.authorAlghoul, Yiad Ibrahim Yousefen
dc.contributor.authorAmirgaliyeva, Zhaziraen
dc.contributor.authorMladenović, Nenaden
dc.date.accessioned2020-05-01T20:13:52Z-
dc.date.available2020-05-01T20:13:52Z-
dc.date.issued2019-01-01en
dc.identifier.isbn978-3-030-22628-2en
dc.identifier.issn0302-9743en
dc.identifier.urihttp://researchrepository.mi.sanu.ac.rs/handle/123456789/1761-
dc.description.abstractHaving defined a complete bipartite graph G, with weights associated with both vertices and edges, the Bipartite Quadratic Programming problem (BQP) consists in selecting a subgraph that maximizes the sum of the weights associated with the chosen vertices and the edges that connect them. Applications of the BQP arise in mining discrete patterns from binary data, approximation of matrices by rank-one binary matrices, computation of the cut-norm of a matrix, etc. In addition, BQP is also known in the literature under different names such as maximum weighted induced subgraph, maximum weight bi-clique and maximum cut on bipartite graphs. Since the problem is NP-hard, many heuristic methods have been proposed in the literature to solve it. In this paper, we apply the recent Less is more approach, whose basic idea is to design a heuristic as simple as possible, i.e., a method that uses a minimum number of ingredients but provides solutions of better quality than the current state-of-the-art. To reach that goal, we propose a simple hybrid heuristic based on Tabu search, that uses two neighborhood structures and relatively simple rule for implementation of short-term memory operation. In addition, a simple rule for calculation of tabu list length is introduced. Computational results were compared favorably with the current state-of-the-art heuristics. Despite its simplicity, our heuristic was able to find 6 new best known solutions on very well studied test instances.en
dc.publisherSpringer Link-
dc.relation174010-
dc.relation44006-
dc.relationGrant Number BR05236839 “Development of information technologies and systems for stimulation of personality’s sustainable development as one of the bases of development of digital Kazakhstan”-
dc.relationMinistry of Education and Science, Republic of Kazakhstan, project no. AP05133090-
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en
dc.subjectBipartite quadratic programming | Discrete optimization | Graphs | Tabu search | Variable neighborhood searchen
dc.titleLess is more: Tabu search for bipartite quadratic programming problemen
dc.typeConference Paperen
dc.relation.conference18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019; Ekaterinburg; Russian Federation-
dc.identifier.doi10.1007/978-3-030-22629-9_27en
dc.identifier.scopus2-s2.0-85067649782en
dc.relation.firstpage390en
dc.relation.lastpage401en
dc.relation.volume11548 LNCSen
dc.description.rankM33-
item.grantfulltextnone-
item.cerifentitytypePublications-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.openairetypeConference Paper-
item.fulltextNo Fulltext-
crisitem.author.orcid0000-0003-3607-6704-
crisitem.author.orcid0000-0001-6655-0409-
Show simple item record

SCOPUSTM   
Citations

3
checked on Mar 28, 2024

Page view(s)

316
checked on Mar 29, 2024

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.