DC Field | Value | Language |
---|---|---|
dc.contributor.author | Ahn, Sungsoo | ko |
dc.contributor.author | SEO, YOUNGGYO | ko |
dc.contributor.author | Shin, Jinwoo | ko |
dc.date.accessioned | 2020-12-15T05:50:31Z | - |
dc.date.available | 2020-12-15T05:50:31Z | - |
dc.date.created | 2020-12-02 | - |
dc.date.created | 2020-12-02 | - |
dc.date.issued | 2020-07-15 | - |
dc.identifier.citation | Thirty-seventh International Conference on Machine Learning, ICML 2020, pp.122 - 132 | - |
dc.identifier.issn | 2640-3498 | - |
dc.identifier.uri | http://hdl.handle.net/10203/278489 | - |
dc.description.abstract | Designing efficient algorithms for combinatorial optimization appears ubiquitously in various scientific fields. Recently, deep reinforcement learning (DRL) frameworks have gained considerable attention as a new approach: they can automate the design of a solver while relying less on sophisticated domain knowledge of the target problem. However, the existing DRL solvers determine the solution using a number of stages proportional to the number of elements in the solution, which severely limits their applicability to large-scale graphs. In this paper, we seek to resolve this issue by proposing a novel DRL scheme, coined learning what to defer (LwD), where the agent adaptively shrinks or stretch the number of stages by learning to distribute the element-wise decisions of the solution at each stage. We apply the proposed framework to the maximum independent set (MIS) problem, and demonstrate its significant improvement over the current state-of-the-art DRL scheme. We also show that LwD can outperform the conventional MIS solvers on large-scale graphs having millions of vertices, under a limited time budget. | - |
dc.language | English | - |
dc.publisher | International Conference on Machine Learning | - |
dc.title | Learning What to Defer for Maximum Independent Sets | - |
dc.type | Conference | - |
dc.identifier.wosid | 000683178500014 | - |
dc.identifier.scopusid | 2-s2.0-85105139000 | - |
dc.type.rims | CONF | - |
dc.citation.beginningpage | 122 | - |
dc.citation.endingpage | 132 | - |
dc.citation.publicationname | Thirty-seventh International Conference on Machine Learning, ICML 2020 | - |
dc.identifier.conferencecountry | AU | - |
dc.identifier.conferencelocation | Virtual | - |
dc.contributor.localauthor | Shin, Jinwoo | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.