Data-driven approximations to NP-hard problems

Simple item page
dc.contributor.authorMilan, A.
dc.contributor.authorRezatofighi, S.
dc.contributor.authorGarg, R.
dc.contributor.authorDick, A.
dc.contributor.authorReid, I.
dc.contributor.conferenceThirty-first AAAI Conference on Artificial Intelligence (AAAI-17) (4 Feb 2017 - 9 Feb 2017 : San Francisco)
dc.date.issued2017
dc.description.abstractThere exist a number of problem classes for which obtaining the exact solution becomes exponentially expensive with increasing problem size. The quadratic assignment problem (QAP) or the travelling salesman problem (TSP) are just two examples of such NP-hard problems. In practice, approximate algorithms are employed to obtain a suboptimal solution, where one must face a trade-off between computational complexity and solution quality. In this paper, we propose to learn to solve these problem from approximate examples, using recurrent neural networks (RNNs). Surprisingly, such architectures are capable of producing highly accurate solutions at minimal computational cost. Moreover, we introduce a simple, yet effective technique for improving the initial (weak) training set by incorporating the objective cost into the training procedure. We demonstrate the functionality of our approach on three exemplar applications: marginal distributions of a joint matching space, feature point matching and the travelling salesman problem. We show encouraging results on synthetic and real data in all three cases.
dc.description.statementofresponsibilityAnton Milan, S. Hamid Rezatofighi, Ravi Garg, Anthony Dick, Ian Reid
dc.identifier.citationProceedings of the ... AAAI Conference on Artificial Intelligence. AAAI Conference on Artificial Intelligence, 2017, pp.1453-1459
dc.identifier.issn2159-5399
dc.identifier.issn2374-3468
dc.identifier.orcidGarg, R. [0000-0002-9422-8086]
dc.identifier.orcidDick, A. [0000-0001-9049-7345]
dc.identifier.orcidReid, I. [0000-0001-7790-6423]
dc.identifier.urihttp://hdl.handle.net/2440/115963
dc.language.isoen
dc.publisherAAAI
dc.relation.granthttp://purl.org/au-research/grants/arc/LP130100154
dc.relation.granthttp://purl.org/au-research/grants/arc/FL130100102
dc.relation.granthttp://purl.org/au-research/grants/arc/CE140100016
dc.relation.ispartofseriesAAAI Conference on Artificial Intelligence
dc.rightsCopyright © 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
dc.source.urihttps://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14700
dc.titleData-driven approximations to NP-hard problems
dc.typeConference paper
pubs.publication-statusPublished

Files

Collections

Computer Science publications
Australian Institute for Machine Learning publications