{"id":6766,"date":"2019-09-18T09:22:41","date_gmt":"2019-09-18T07:22:41","guid":{"rendered":"https:\/\/www.ftf.or.at\/?p=6766"},"modified":"2019-09-18T09:22:41","modified_gmt":"2019-09-18T07:22:41","slug":"isotonic-regression-by-dynamic-programming","status":"publish","type":"post","link":"https:\/\/www.ftf.or.at\/?p=6766","title":{"rendered":"Isotonic regression by dynamic programming"},"content":{"rendered":"<div class=\"page\" title=\"Page 1\">\n<div class=\"section\">\n<div class=\"layoutArea\">\n<div class=\"column\">\n<p><strong>Prof. Dr. Gu\u0308nter Rote |\u00a0Freie Universita\u0308t Berlin, Deutschland | Thursday, 19 September 2019 | 11:00 a.m. |\u00a0N.2.01<\/strong><\/p>\n<div class=\"page\" title=\"Page 1\">\n<div class=\"section\">\n<div class=\"layoutArea\">\n<div class=\"column\">\n<p><strong><img loading=\"lazy\" decoding=\"async\" class=\"alignright size-full wp-image-6768\" src=\"https:\/\/www.ftf.or.at\/wp-content\/uploads\/2019\/09\/rote.png\" alt=\"\" width=\"180\" height=\"240\" \/>Abstract<\/strong><\/p>\n<p>For a given sequence of n numbers, we want to find a monotonically in- creasing sequence of the same length that best approximates it in the sense of minimizing the weighted sum of absolute values of the differences. A conceptually easy dynamic programming approach leads to an algorithm with running time O(n log n). While other algorithms with the same run- ning time are known, our algorithm is very simple. The only auxiliary data structure that it requires is a priority queue. The approach extends to other error measures.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Prof. Dr. Gu\u0308nter Rote |\u00a0Freie Universita\u0308t Berlin, Deutschland | Thursday, 19 September 2019 | 11:00 a.m. |\u00a0N.2.01 Abstract For a given sequence of n numbers, we want to find a monotonically in- creasing sequence of the same length that best &hellip; <a href=\"https:\/\/www.ftf.or.at\/?p=6766\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"sfsi_plus_gutenberg_text_before_share":"","sfsi_plus_gutenberg_show_text_before_share":"","sfsi_plus_gutenberg_icon_type":"","sfsi_plus_gutenberg_icon_alignemt":"","sfsi_plus_gutenburg_max_per_row":"","footnotes":""},"categories":[1],"tags":[],"class_list":["post-6766","post","type-post","status-publish","format-standard","hentry","category-tewi-kolloquium"],"_links":{"self":[{"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/posts\/6766","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=6766"}],"version-history":[{"count":2,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/posts\/6766\/revisions"}],"predecessor-version":[{"id":6769,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/posts\/6766\/revisions\/6769"}],"wp:attachment":[{"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=6766"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=6766"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=6766"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}