DC FieldValueLanguage
dc.contributor.authorTomić, Milanen_US
dc.contributor.authorUrošević, Draganen_US
dc.date.accessioned2021-10-04T09:09:41Z-
dc.date.available2021-10-04T09:09:41Z-
dc.date.issued2021-07-01-
dc.identifier.isbn978-3-030-86432-3-
dc.identifier.issn1865-0929-
dc.identifier.urihttp://researchrepository.mi.sanu.ac.rs/handle/123456789/4666-
dc.description.abstractThe optimal seating chart problem is a graph partitioning problem with very practical use. It is the problem of finding an optimal seating arrangement for a wedding or a gala dinner. Given the number of tables available and the number of seats per table, the optimal seating arrangement is determined based on the guests’ preferences to seat or not to seat together with other guests at the same table. The problem is easily translated to finding an m-partitioning of a graph of n nodes, such that the number of nodes in each partition is less than or equal to the given upper limit c, and that the sum of edge weights in all partitions is maximized. Although it can be easily formulated as MILP, the problem is extremely difficult to solve even with relatively small instances, which makes it perfect to apply a heuristic method. In this paper, we present research of a novel descent-ascent method for the solution, with comparison to some of the already proposed techniques from the earlier works.en_US
dc.publisherSpringer Linken_US
dc.relation.ispartofseriesCommunications in Computer and Information Scienceen_US
dc.subjectGraph partitioning | Seating optimization | Simulated annealingen_US
dc.titleA Heuristic Approach in Solving the Optimal Seating Chart Problemen_US
dc.typeConference Paperen_US
dc.relation.conferenceMOTOR 2021 : International Conference on Mathematical Optimization Theory and Operations Research-
dc.identifier.doi10.1007/978-3-030-86433-0_19-
dc.identifier.scopus2-s2.0-85115852852-
dc.contributor.affiliationComputer Scienceen_US
dc.contributor.affiliationMathematical Institute of the Serbian Academy of Sciences and Arts-
dc.relation.firstpage271-
dc.relation.lastpage283-
dc.description.rankM33-
item.cerifentitytypePublications-
item.openairetypeConference Paper-
item.fulltextNo Fulltext-
item.grantfulltextnone-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
crisitem.author.orcid0000-0003-3607-6704-
Show simple item record

SCOPUSTM   
Citations

2
checked on Jul 12, 2024

Page view(s)

105
checked on May 9, 2024

Google ScholarTM

Check

Altmetric

Altmetric


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