{"id":16581,"date":"2024-09-20T12:23:48","date_gmt":"2024-09-20T10:23:48","guid":{"rendered":"https:\/\/is.ijs.si\/?p=16581"},"modified":"2025-03-26T13:17:51","modified_gmt":"2025-03-26T12:17:51","slug":"solving-hard-optimization-problems-of-packing-covering-and-tiling-via-clique-search","status":"publish","type":"post","link":"https:\/\/is.ijs.si\/?p=16581","title":{"rendered":"Solving hard optimization problems of packing, covering, and tiling via clique search"},"content":{"rendered":"\n<p>Sandor Szabo and Bogdan Zavalnij<\/p>\n<p><strong>Abstract<\/strong><br \/>In the paper we propose to convert NP-hard combinato-<br \/>rial optimization problems of packing, covering, and tiling<br \/>types into maximum or \ud835\udc58-clique problems. The key step is<br \/>to come up with a tactically constructed auxiliary graph<br \/>whose maximum or \ud835\udc58-cliques correspond to the sought com-<br \/>binatorial structure. As an example, we will consider the<br \/>problem of packing a given cube by copies of a brick. The<br \/>aim of the paper is two fold to illustrate the modeling power<br \/>and the feasibility of the clique approach. Since theoretical<br \/>tools are not readily available to study the effectiveness of<br \/>the solution of the resulting clique problems we will carry<br \/>out carefully conducted numerical experiments.<\/p>\n<p>\u00a0<\/p>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/is.ijs.si\/wp-content\/uploads\/2024\/10\/IS2024_-_SIKDD_2024_paper_9-1.pdf\" type=\"application\/pdf\" style=\"width:100%;height:600px\" aria-label=\"Embed of IS2024_-_SIKDD_2024_paper_9-1.\"><\/object><a id=\"wp-block-file--media-9a1f34ff-e86c-4c28-9bf3-b1432f9f069d\" href=\"https:\/\/is.ijs.si\/wp-content\/uploads\/2024\/10\/IS2024_-_SIKDD_2024_paper_9-1.pdf\">IS2024_-_SIKDD_2024_paper_9-1<\/a><a href=\"https:\/\/is.ijs.si\/wp-content\/uploads\/2024\/10\/IS2024_-_SIKDD_2024_paper_9-1.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-9a1f34ff-e86c-4c28-9bf3-b1432f9f069d\">Download<\/a><\/div>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":29,"featured_media":24966,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[109,102],"tags":[],"class_list":["post-16581","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-doi-sikdd-2024","category-papers"],"_links":{"self":[{"href":"https:\/\/is.ijs.si\/index.php?rest_route=\/wp\/v2\/posts\/16581","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/is.ijs.si\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/is.ijs.si\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/is.ijs.si\/index.php?rest_route=\/wp\/v2\/users\/29"}],"replies":[{"embeddable":true,"href":"https:\/\/is.ijs.si\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=16581"}],"version-history":[{"count":3,"href":"https:\/\/is.ijs.si\/index.php?rest_route=\/wp\/v2\/posts\/16581\/revisions"}],"predecessor-version":[{"id":25001,"href":"https:\/\/is.ijs.si\/index.php?rest_route=\/wp\/v2\/posts\/16581\/revisions\/25001"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/is.ijs.si\/index.php?rest_route=\/wp\/v2\/media\/24966"}],"wp:attachment":[{"href":"https:\/\/is.ijs.si\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=16581"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/is.ijs.si\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=16581"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/is.ijs.si\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=16581"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}