乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:17:23Z","timestamp":1740143843688,"version":"3.37.3"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"name":"Norwegian Research Foundation","award":["274526d"]},{"name":"Swarnajayanti Fellowship","award":["DST\/SJF\/MSA-01\/2017-18"]},{"DOI":"10.13039\/100009935","name":"IFCAM","doi-asserted-by":"crossref","award":["MA\/IFCAM\/18\/39"],"id":[{"id":"10.13039\/100009935","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["715744, 819416"],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006475","name":"Bergens Forskningsstiftelse","doi-asserted-by":"publisher","award":["810564"],"id":[{"id":"10.13039\/501100006475","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2021,4,30]]},"abstract":"\n A\n tournament<\/jats:italic>\n is a directed graph\n T<\/jats:italic>\n such that every pair of vertices is connected by an arc. A\n feedback vertex set<\/jats:italic>\n is a set\n S<\/jats:italic>\n of vertices in\n T<\/jats:italic>\n such that\n T<\/jats:italic>\n \u2212\n S<\/jats:italic>\n is acyclic. We consider the Feedback Vertex Set problem in tournaments. Here, the input is a tournament\n T<\/jats:italic>\n and a weight function\n w<\/jats:italic>\n :\n V<\/jats:italic>\n (\n T<\/jats:italic>\n ) \u2192 N, and the task is to find a feedback vertex set\n S<\/jats:italic>\n in\n T<\/jats:italic>\n minimizing\n w<\/jats:italic>\n (\n S<\/jats:italic>\n ) = \u2211\n \n v\u2208S<\/jats:italic>\n <\/jats:sub>\n w<\/jats:italic>\n (\n v<\/jats:italic>\n ). Rounding optimal solutions to the natural LP-relaxation of this problem yields a simple 3-approximation algorithm. This has been improved to 2.5 by Cai et\u00a0al. [SICOMP 2000], and subsequently to 7\/3 by Mnich et\u00a0al. [ESA 2016]. In this article, we give the first polynomial time factor 2-approximation algorithm for this problem. Assuming the Unique Games Conjecture, this is the best possible approximation ratio achievable in polynomial time.\n <\/jats:p>","DOI":"10.1145\/3446969","type":"journal-article","created":{"date-parts":[[2021,4,20]],"date-time":"2021-04-20T00:01:42Z","timestamp":1618876902000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["2-Approximating Feedback Vertex Set in Tournaments"],"prefix":"10.1145","volume":"17","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[{"name":"University of California, California, USA"}]},{"given":"Pranabendu","family":"Misra","sequence":"additional","affiliation":[{"name":"Max-Planck Institute for Informatics, SIC, Saarbrucken, Germany"}]},{"given":"Joydeep","family":"Mukherjee","sequence":"additional","affiliation":[{"name":"Ramakrishna Mission Vivekananda Educational and Research Institute, India and Indian Statistical Institute, West Bengal, India"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, IIT Hyderabad, Telangana, India"}]},{"given":"Geevarghese","family":"Philip","sequence":"additional","affiliation":[{"name":"Chennai Mathematical Institute, India and UMI ReLaX, Kelambakkam, India"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"Institute of Mathematical Sciences, HBNI, India and University of Bergen, Norway and UMI ReLaX, Tamil Nadu, India"}]}],"member":"320","published-online":{"date-parts":[[2021,4,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411513"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018353700639"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480196305124"},{"key":"e_1_2_1_4_1","volume-title":"Gutin","author":"Bang-Jensen J\u00f8rgen","year":"2009","unstructured":"J\u00f8rgen Bang-Jensen and Gregory Z . Gutin . 2009 . Digraphs\u2014Theory, Algorithms and Applications, 2 nd ed. Springer . J\u00f8rgen Bang-Jensen and Gregory Z. Gutin. 2009. Digraphs\u2014Theory, Algorithms and Applications, 2nd ed. Springer.","edition":"2"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90020-1"},{"key":"e_1_2_1_6_1","first-page":"1993","article-title":"An approximation algorithm for feedback vertex sets in tournaments","volume":"30","author":"Deng Xiaotie","year":"2000","unstructured":"Mao-cheng Cai, Xiaotie Deng , and Wenan Zang . 2000 . An approximation algorithm for feedback vertex sets in tournaments . SIAM J. Comput. 30 , 6 (2000), 1993 -- 2007 . Mao-cheng Cai, Xiaotie Deng, and Wenan Zang. 2000. An approximation algorithm for feedback vertex sets in tournaments. SIAM J. Comput. 30, 6 (2000), 1993--2007.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411511"},{"key":"e_1_2_1_8_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2009. Introduction to Algorithms ( 3 rd ed.). MIT Press , Cambridge, MA . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). MIT Press, Cambridge, MA.","edition":"3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.23"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704443057"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2009.08.001"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-035-8"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009191"},{"key":"e_1_2_1_14_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co. Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21631"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250806"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.05.001"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916)","volume":"47","author":"Kumar Mithilesh","year":"2016","unstructured":"Mithilesh Kumar and Daniel Lokshtanov . 2016 . Faster exact and parameterized algorithm for feedback vertex set in tournaments . In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916) (LIPIcs), Nicolas Ollinger and Heribert Vollmer (Eds.) , Vol. 47 . Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 49:1--49:13. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2016.49 10.4230\/LIPIcs.STACS.2016.49 Mithilesh Kumar and Daniel Lokshtanov. 2016. Faster exact and parameterized algorithm for feedback vertex set in tournaments. In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916) (LIPIcs), Nicolas Ollinger and Heribert Vollmer (Eds.), Vol. 47. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 49:1--49:13. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2016.49"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916)","volume":"57","author":"Mnich Matthias","unstructured":"Matthias Mnich , Virginia Vassilevska Williams , and L\u00e1szl\u00f3 A. V\u00e9gh . 2016. A 7\/3-approximation for feedback vertex sets in tournaments . In Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916) (LIPIcs), Piotr Sankowski and Christos D. Zaroliagis (Eds.) , Vol. 57 . Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 67:1--67:14. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2016.67 10.4230\/LIPIcs.ESA.2016.67 Matthias Mnich, Virginia Vassilevska Williams, and L\u00e1szl\u00f3 A. V\u00e9gh. 2016. A 7\/3-approximation for feedback vertex sets in tournaments. In Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916) (LIPIcs), Piotr Sankowski and Christos D. Zaroliagis (Eds.), Vol. 57. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 67:1--67:14. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2016.67"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.010"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1142\/9789812770998_0010"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01271272"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 15th International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201989)","volume":"411","author":"Speckenmeyer Ewald","year":"1989","unstructured":"Ewald Speckenmeyer . 1989 . On feedback problems in diagraphs . In Proceedings of the 15th International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201989) (Lecture Notes in Computer Science), Manfred Nagl (Ed.) , Vol. 411 . Springer, 218--231. DOI:https:\/\/doi.org\/10.1007\/3-540-52292-1_16 10.1007\/3-540-52292-1_16 Ewald Speckenmeyer. 1989. On feedback problems in diagraphs. In Proceedings of the 15th International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201989) (Lecture Notes in Computer Science), Manfred Nagl (Ed.), Vol. 411. Springer, 218--231. DOI:https:\/\/doi.org\/10.1007\/3-540-52292-1_16"},{"key":"e_1_2_1_25_1","volume-title":"Shmoys","author":"Williamson David P.","year":"2011","unstructured":"David P. Williamson and David B . Shmoys . 2011 . The Design of Approximation Algorithms. Cambridge University Press , Cambridge, UK. David P. Williamson and David B. Shmoys. 2011. The Design of Approximation Algorithms. Cambridge University Press, Cambridge, UK."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-014-9737-x"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3446969","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T21:33:00Z","timestamp":1672608780000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3446969"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,19]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,4,30]]}},"alternative-id":["10.1145\/3446969"],"URL":"https:\/\/doi.org\/10.1145\/3446969","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2021,4,19]]},"assertion":[{"value":"2019-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}