Learning what to defer for maximum independent sets
- Title
- Learning what to defer for maximum independent sets
- Authors
- AHN, SUNGSOO; Seo, Younggyo; Shin, Jinwoo
- Date Issued
- 2020-06
- Publisher
- International Machine Learning Society (IMLS)
- 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-ofthe-art DRL scheme. We also show that LwD can outperform the conventional MIS solvers on largescale graphs having millions of vertices, under a limited time budget.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/109514
- Article Type
- Conference
- Citation
- 37th International Conference on Machine Learning, ICML 2020, page. 122 - 132, 2020-06
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.