{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T15:40:06Z","timestamp":1741448406971,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642229343"},{"type":"electronic","value":"9783642229350"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22935-0_24","type":"book-chapter","created":{"date-parts":[[2011,8,12]],"date-time":"2011-08-12T09:20:39Z","timestamp":1313140839000},"page":"277-288","source":"Crossref","is-referenced-by-count":2,"title":["Approximation Schemes for the Betweenness\u00a0Problem in Tournaments and Related Ranking Problems"],"prefix":"10.1007","author":[{"given":"Marek","family":"Karpinski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Warren","family":"Schudy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"24_CR1","unstructured":"Ailon, N.: Aggregation of Partial Rankings, p-ratings and top-m Lists. In: 18th SODA, pp. 415\u2013424 (2007)"},{"key":"24_CR2","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1016\/j.ic.2007.02.006","volume":"205","author":"N. Ailon","year":"2007","unstructured":"Ailon, N., Alon, N.: Hardness of Fully Dense Problems. Inf. Comput.\u00a0205, 1117\u20131129 (2007)","journal-title":"Inf. Comput."},{"key":"24_CR3","doi-asserted-by":"crossref","unstructured":"Ailon, N., Charikar, M., Newman, A.: Aggregating Inconsistent Information: Ranking and Clustering. J. ACM\u00a055 (2008)","DOI":"10.1145\/1411509.1411513"},{"key":"#cr-split#-24_CR4.1","doi-asserted-by":"crossref","unstructured":"Alon, N., Fernandez de la Vega, W., Kannan, R., Karpinski, M.: Random Sampling and Approximation of MAX-CSP Problems. In: 34th ACM STOC, pp. 232???239 (2002);","DOI":"10.1145\/509907.509945"},{"key":"#cr-split#-24_CR4.2","doi-asserted-by":"crossref","unstructured":"Journal version in JCSS 67, 212???243 (2003)","DOI":"10.1016\/S0022-0000(03)00008-4"},{"key":"24_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/978-3-642-02927-1_6","volume-title":"Automata, Languages and Programming","author":"N. Alon","year":"2009","unstructured":"Alon, N., Lokshtanov, D., Saurabh, S.: Fast FAST. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05555, pp. 49\u201358. Springer, Heidelberg (2009)"},{"key":"#cr-split#-24_CR6.1","doi-asserted-by":"crossref","unstructured":"Arora, S., Karger, D., Karpinski, M.: Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems. In: 27th ACM STOC, pp. 284???293 (1995);","DOI":"10.1145\/225058.225140"},{"key":"#cr-split#-24_CR6.2","doi-asserted-by":"crossref","unstructured":"Journal version in J. Comput. System Sciences 58, 193???210 (1999)","DOI":"10.1006\/jcss.1998.1605"},{"key":"24_CR7","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1002\/rsa.10072","volume":"23","author":"C. Bazgan","year":"2003","unstructured":"Bazgan, C., Fernandez de la Vega, W., Karpinski, M.: Polynomial Time Approximation Schemes for Dense Instances of the Minimum Constraint Satisfaction Problem. Random Structures and Algorithms\u00a023, 73\u201391 (2003)","journal-title":"Random Structures and Algorithms"},{"key":"24_CR8","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guruswami, V., Manokaran, R.: Every Permutation CSP of Arity 3 is Approximation Restitant. In: 24th IEEE CCC (2009)","DOI":"10.1109\/CCC.2009.29"},{"key":"24_CR9","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1137\/S0895480195296221","volume":"11","author":"B. Chor","year":"1998","unstructured":"Chor, B., Sudan, M.: A Geometric Approach to Betweenness. SIAM J. Discrete Math.\u00a011, 511\u2013523 (1998)","journal-title":"SIAM J. Discrete Math."},{"key":"24_CR10","unstructured":"Fernandez de la Vega, W., Kannan, R., Karpinski, M.: Approximation of Global MAX\u2013CSP Problems. Technical Report TR06-124, ECCC (2006)"},{"key":"24_CR11","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/s004930050052","volume":"19","author":"A. Frieze","year":"1999","unstructured":"Frieze, A., Kannan, R.: Quick Approximation to Matrices and Applications. Combinatorica\u00a019, 175\u2013220 (1999)","journal-title":"Combinatorica"},{"key":"24_CR12","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Hastad, J., Manokaran, R., Raghavendra, P., Charikar, M.: Beating the random ordering is hard: Every ordering csp is approximation resistant. In: ECCC TR-11-027 (2011)","DOI":"10.1137\/090756144"},{"issue":"8","key":"24_CR13","doi-asserted-by":"publisher","first-page":"872","DOI":"10.1016\/j.jcss.2010.05.001","volume":"76","author":"G. Gutin","year":"2010","unstructured":"Gutin, G., Kim, E.J., Mnich, M., Yeo, A.: Betweenness parameterized above tight lower bound. Journal of Computer and System Sciences\u00a076(8), 872\u2013878 (2010)","journal-title":"Journal of Computer and System Sciences"},{"key":"24_CR14","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Schudy, W.: Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems. In: 41st ACM STOC, pp. 313\u2013322 (2009)","DOI":"10.1145\/1536414.1536458"},{"key":"24_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-642-17517-6_3","volume-title":"Algorithms and Computation","author":"M. Karpinski","year":"2010","unstructured":"Karpinski, M., Schudy, W.: Faster algorithms for feedback arc set tournament, kemeny rank aggregation and betweenness tournament (LNCS 6506\/2010). In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010. LNCS, vol.\u00a06506, pp. 3\u201314. Springer, Heidelberg (2010)"},{"key":"#cr-split#-24_CR16.1","doi-asserted-by":"crossref","unstructured":"Mathieu, C., Schudy, W.: How to Rank with Few Errors. In: 39th ACM STOC, pp. 95???103 (2007);","DOI":"10.1145\/1250790.1250806"},{"key":"#cr-split#-24_CR16.2","unstructured":"In Submission http:\/\/www.cs.brown.edu\/~ws\/papers\/fast_journal.pdf (2009)"},{"key":"24_CR17","unstructured":"Mathieu, C., Schudy, W.: Yet Another Algorithm for Dense Max Cut: Go Greedy. In: Proc. 19th ACM-SIAM SODA, pp. 176\u2013182 (2008)"},{"key":"24_CR18","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1137\/0208008","volume":"8","author":"J. Opatrny","year":"1979","unstructured":"Opatrny, J.: Total Ordering Problem. SIAM J. Comput.\u00a08, 111\u2013114 (1979)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22935-0_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T15:18:14Z","timestamp":1741447094000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22935-0_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229343","9783642229350"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22935-0_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}