{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T23:05:11Z","timestamp":1725750311115},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642409349"},{"type":"electronic","value":"9783642409356"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40935-6_3","type":"book-chapter","created":{"date-parts":[[2013,9,27]],"date-time":"2013-09-27T05:14:50Z","timestamp":1380258890000},"page":"22-32","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Algorithms for Combinatorial Online Prediction"],"prefix":"10.1007","author":[{"given":"Eiji","family":"Takimoto","sequence":"first","affiliation":[]},{"given":"Kohei","family":"Hatano","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"3_CR1","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/s00453-008-9211-1","volume":"57","author":"N. Ailon","year":"2008","unstructured":"Ailon, N.: Aggregation of Partial Rankings, p-Ratings and Top-m Lists. Algorithmica\u00a057(2), 284\u2013300 (2008)","journal-title":"Algorithmica"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"Ailon, N., Charikar, M., Newman, A.: Aggregating inconsistent information: Ranking and clustering. Journal of the ACM\u00a055(5) (2008)","DOI":"10.1145\/1411509.1411513"},{"issue":"1","key":"3_CR3","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/rsa.10033","volume":"20","author":"D.R. Carr","year":"2002","unstructured":"Carr, D.R., Vempala, S.: Randomized metarounding. Random Structure and Algorithms\u00a020(1), 343\u2013352 (2002)","journal-title":"Random Structure and Algorithms"},{"key":"3_CR4","unstructured":"Cesa-Bianchi, N., Lugosi, G.: Combinatorial Bandits. In: Proceedings of the 22nd Conference on Learning Theory, COLT 2009 (2009)"},{"issue":"1","key":"3_CR5","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/0167-6377(89)90029-1","volume":"8","author":"S. Chopra","year":"1989","unstructured":"Chopra, S.: On the spanning tree polyhedron. Operations Research Letters\u00a08(1), 25\u201329 (1989)","journal-title":"Operations Research Letters"},{"issue":"1","key":"3_CR6","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01584082","volume":"1","author":"J. Edmonds","year":"1971","unstructured":"Edmonds, J.: Matroids and the greedy algorithm. Mathematical Programming\u00a01(1), 127\u2013136 (1971)","journal-title":"Mathematical Programming"},{"issue":"1","key":"3_CR7","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1006\/jcss.1997.1504","volume":"55","author":"Y. Freund","year":"1997","unstructured":"Freund, Y., Schapire, R.E.: A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting. Journal of Computer and System Sciences\u00a055(1), 119\u2013139 (1997)","journal-title":"Journal of Computer and System Sciences"},{"key":"3_CR8","unstructured":"Fujishige, S.: Submodular functions and optimization, 2nd edn. Elsevier Science (2005)"},{"key":"3_CR9","series-title":"LNAI","first-page":"56","volume-title":"ALT 2013","author":"T. Fujita","year":"2013","unstructured":"Fujita, T., Hatano, K., Takimoto, E.: Combinatorial Online Prediction via Metarounding. In: Jain, S., Munos, R., Stephan, F., Zeugmann, T. (eds.) ALT 2013. LNCS (LNAI), vol.\u00a08139, pp. 56\u201370. Springer, Heidelberg (2013)"},{"key":"3_CR10","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"M. Goemans","year":"1994","unstructured":"Goemans, M., Williamson, D.: New 3\/4-approximation algorithms for the maximum satisfiability problem. SIAM Journal on Discrete Mathematics\u00a07, 656\u2013666 (1994)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"Hazan, E.: The convex optimization approach to regret minimization. In: Sra, S., Nowozin, S., Wright, S.J. (eds.) Optimization for Machine Learning, ch. 10, pp. 287\u2013304. MIT Press (2011)","DOI":"10.7551\/mitpress\/8996.003.0012"},{"key":"3_CR12","unstructured":"Hazan, E., Kale, S.: Projection-free online learning. In: Proceedings of the 29th International Conference on Machine Learning, ICML 2012 (2012)"},{"key":"3_CR13","first-page":"1705","volume":"10","author":"D.P. Helmbold","year":"2009","unstructured":"Helmbold, D.P., Warmuth, M.K.: Learning Permutations with Exponential Weights. Journal of Machine Learning Research\u00a010, 1705\u20131736 (2009)","journal-title":"Journal of Machine Learning Research"},{"key":"3_CR14","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/s10107-006-0084-2","volume":"112","author":"S. Iwata","year":"2008","unstructured":"Iwata, S.: Submodular function minimization. Mathematical Programming, Ser. B\u00a0112, 45\u201364 (2008)","journal-title":"Mathematical Programming, Ser. B"},{"issue":"3","key":"3_CR15","doi-asserted-by":"publisher","first-page":"1018","DOI":"10.1137\/070701704","volume":"39","author":"S. Kakade","year":"2009","unstructured":"Kakade, S., Kalai, A.T., Ligett, L.: Playing games with approximation algorithms. SIAM Journal on Computing\u00a039(3), 1018\u20131106 (2009)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"3_CR16","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/j.jcss.2004.10.016","volume":"71","author":"A. Kalai","year":"2005","unstructured":"Kalai, A., Vempala, S.: Efficient algorithms for online decision problems. Journal of Computer and System Sciences\u00a071(3), 291\u2013307 (2005)","journal-title":"Journal of Computer and System Sciences"},{"key":"3_CR17","unstructured":"Koolen, W.M., Warmuth, M.K., Kivinen, J.: Hedging Structured Concepts. In: Proceedings of the 23rd Conference on Learning Theory, COLT 2010, pp. 93\u2013105 (2010)"},{"key":"3_CR18","unstructured":"Nagano, K.: A faster parametric submodular function minimization algorithm and applications. Technical Report METR 2007\u201343, Department of Mathematical Informatics, Graduate School of Information Science and Technology, University of Tokyo (2007)"},{"key":"3_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/978-3-540-72792-7_19","volume-title":"Integer Programming and Combinatorial Optimization","author":"J.B. Orlin","year":"2007","unstructured":"Orlin, J.B.: A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization. In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol.\u00a04513, pp. 240\u2013251. Springer, Heidelberg (2007)"},{"key":"3_CR20","unstructured":"Schrijver, A.: Theory of linear and integer programming. Wiley (1998)"},{"key":"3_CR21","doi-asserted-by":"crossref","unstructured":"Srinivasan, A.: Improved approximations of packing and covering problems. In: 27th ACM Symposium on the Theory of Computing, pp. 268\u2013276 (1995)","DOI":"10.1145\/225058.225138"},{"key":"3_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-642-34106-9_22","volume-title":"Algorithmic Learning Theory","author":"D. Suehiro","year":"2012","unstructured":"Suehiro, D., Hatano, K., Kijima, S., Takimoto, E., Nagano, K.: Online Prediction under Submodular Constraints. In: Bshouty, N.H., Stoltz, G., Vayatis, N., Zeugmann, T. (eds.) ALT 2012. LNCS, vol.\u00a07568, pp. 260\u2013274. Springer, Heidelberg (2012)"},{"key":"3_CR23","first-page":"773","volume":"4","author":"E. Takimoto","year":"2003","unstructured":"Takimoto, E., Warmuth, M.K.: Path kernels and multiplicative updates. Journal of Machine Learning Research\u00a04, 773\u2013818 (2003)","journal-title":"Journal of Machine Learning Research"},{"key":"3_CR24","unstructured":"Warmuth, M., Glocer, K., R\u00e4tsch, G.: Boosting Algorithms for Maximizing the Soft Margin. In: Advances in Neural Information Processing Systems 20, NIPS 2007, pp. 1585\u20131592 (2007)"},{"key":"3_CR25","first-page":"2287","volume":"9","author":"M.K. Warmuth","year":"2008","unstructured":"Warmuth, M.K., Kuzmin, D.: Randomized Online PCA Algorithms with Regret Bounds that are Logarithmic in the Dimension. Journal of Machine Learning Research\u00a09, 2287\u20132320 (2008)","journal-title":"Journal of Machine Learning Research"},{"key":"3_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"534","DOI":"10.1007\/978-3-642-25591-5_55","volume-title":"Algorithms and Computation","author":"S. Yasutake","year":"2011","unstructured":"Yasutake, S., Hatano, K., Kijima, S., Takimoto, E., Takeda, M.: Online Linear Optimization over Permutations. In: Asano, T., Nakano, S.-I., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol.\u00a07074, pp. 534\u2013543. Springer, Heidelberg (2011)"},{"key":"3_CR27","unstructured":"Yasutake, S., Hatano, K., Takimoto, E., Takeda, M.: Online Rank Aggregation. In: Proceedings of 4th Asian Conference on Machine Learning, ACML 2012, pp. 539\u2013553 (2012)"},{"key":"3_CR28","doi-asserted-by":"crossref","unstructured":"Ziegler, G.M.: Lectures on Polytopes. Graduate Texts in Mathematics, vol.\u00a0152. Springer (1995)","DOI":"10.1007\/978-1-4613-8431-1"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40935-6_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,4]],"date-time":"2023-07-04T21:23:17Z","timestamp":1688505797000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40935-6_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642409349","9783642409356"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40935-6_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}