{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T05:47:36Z","timestamp":1757310456067},"reference-count":0,"publisher":"Association for the Advancement of Artificial Intelligence (AAAI)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AAAI"],"abstract":"<jats:p>\n      \n        We present a fast local search algorithm that finds an improved solution (if there is any) in the k-exchange neighborhood of the given solutionto an instance of Weighted Feedback Arc Set in Tournaments. More precisely,given an arc weighted tournament T on n vertices and a feedback arc set  F (a set of arcs whose deletion from T turns it into a directed acyclic graph), our algorithm  decides in time O(2o(k) n log n) if there is a feedback arc set of smaller weight and that differs from F in at most k arcs. To our knowledge this is the first algorithm searching the k-exchange neighborhood of an NP-complete problem that runs in (parameterized) subexponential time. Using this local search algorithm for  Weighted Feedback Arc Set in Tournaments, we obtain subexponential time algorithms for a local search variant of Kemeny Ranking \u2014 a problem in social choice theory and of One-Sided Cross Minimization \u2014 a problem in graph drawing.\n      \n    <\/jats:p>","DOI":"10.1609\/aaai.v24i1.7557","type":"journal-article","created":{"date-parts":[[2022,9,13]],"date-time":"2022-09-13T05:16:22Z","timestamp":1663046182000},"page":"65-70","source":"Crossref","is-referenced-by-count":10,"title":["Fast Local Search Algorithm for Weighted Feedback Arc Set in Tournaments"],"prefix":"10.1609","volume":"24","author":[{"given":"Fedor","family":"Fomin","sequence":"first","affiliation":[]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[]}],"member":"9382","published-online":{"date-parts":[[2010,7,3]]},"container-title":["Proceedings of the AAAI Conference on Artificial Intelligence"],"original-title":[],"link":[{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/download\/7557\/7418","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/download\/7557\/7418","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,13]],"date-time":"2022-09-13T05:16:23Z","timestamp":1663046183000},"score":1,"resource":{"primary":{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/7557"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7,3]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2010,7,15]]}},"URL":"https:\/\/doi.org\/10.1609\/aaai.v24i1.7557","relation":{},"ISSN":["2374-3468","2159-5399"],"issn-type":[{"value":"2374-3468","type":"electronic"},{"value":"2159-5399","type":"print"}],"subject":[],"published":{"date-parts":[[2010,7,3]]}}}