{"id":118,"date":"2015-06-22T00:03:36","date_gmt":"2015-06-21T15:03:36","guid":{"rendered":"http:\/\/www.opt.mist.i.u-tokyo.ac.jp\/crest-model\/?p=118"},"modified":"2015-06-22T00:03:36","modified_gmt":"2015-06-21T15:03:36","slug":"6%e6%9c%8822%e6%97%a5%ef%bc%9a%e3%80%8c%e6%9c%80%e9%81%a9%e3%83%a2%e3%83%87%e3%83%aa%e3%83%b3%e3%82%b0%e3%80%8d%e3%82%bb%e3%83%9f%e3%83%8a%e3%83%bc%e9%96%8b%e5%82%ac","status":"publish","type":"post","link":"https:\/\/www.opt.mist.i.u-tokyo.ac.jp\/crest-model\/2015\/06\/22\/6%e6%9c%8822%e6%97%a5%ef%bc%9a%e3%80%8c%e6%9c%80%e9%81%a9%e3%83%a2%e3%83%87%e3%83%aa%e3%83%b3%e3%82%b0%e3%80%8d%e3%82%bb%e3%83%9f%e3%83%8a%e3%83%bc%e9%96%8b%e5%82%ac\/","title":{"rendered":"\u300c\u6700\u9069\u30e2\u30c7\u30ea\u30f3\u30b0\u300d\u30bb\u30df\u30ca\u30fc\u6848\u5185(6\/22)"},"content":{"rendered":"<p>\u65e5\u6642: 2015\u5e746\u670822\u65e5\uff08\u6708\uff09\u300017\uff1a00&#8211;18\uff1a30<\/p>\n<p>\u5834\u6240: \u6771\u4eac\u5927\u5b66\u3000\u5de5\u5b66\u90e86\u53f7\u99283\u968e\u3000\u30bb\u30df\u30ca\u30fc\u5ba4 A\/D<br \/>\n       http:\/\/www.u-tokyo.ac.jp\/campusmap\/cam01_04_07_j.html<\/p>\n<p>\u8b1b\u6f14\u8005:  Sebastian Pokutta<br \/>\n      (Georgia Institute of Technology, School of Industrial and Systems Engineering (ISyE) )<\/p>\n<p>\u984c\u76ee: The Expressive Power of Linear and Semidefinite Programs<\/p>\n<p>Abstract:<br \/>\nLinear and semidefinite programming are two core optimization paradigms with many important applications in engineering and business.  However, the expressive power of these modeling paradigms is only partially understood so far and extended formulations are a powerful and natural tool to analyze the possibilities and limitations of linear and semidefinite programming formulations.<\/p>\n<p>In this talk I will provide an overview of recent breakthrough results in extended formulations, both in the linear and the semidefinite setting, lay out frameworks for establishing lower bounds including techniques from communication complexity and information theory, as well as discuss constructions. I will then explain reduction mechanisms between problems in the context of LPs and SDPs, which allow to establish strong inapproximability results for various problems.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u65e5\u6642: 2015\u5e746\u670822\u65e5\uff08\u6708\uff09\u300017\uff1a00&#8211;18\uff1a30 \u5834\u6240: \u6771\u4eac\u5927\u5b66\u3000\u5de5\u5b66\u90e86\u53f7&hellip; <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[],"class_list":["post-118","post","type-post","status-publish","format-standard","hentry","category-3"],"_links":{"self":[{"href":"https:\/\/www.opt.mist.i.u-tokyo.ac.jp\/crest-model\/wp-json\/wp\/v2\/posts\/118","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.opt.mist.i.u-tokyo.ac.jp\/crest-model\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.opt.mist.i.u-tokyo.ac.jp\/crest-model\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.opt.mist.i.u-tokyo.ac.jp\/crest-model\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.opt.mist.i.u-tokyo.ac.jp\/crest-model\/wp-json\/wp\/v2\/comments?post=118"}],"version-history":[{"count":0,"href":"https:\/\/www.opt.mist.i.u-tokyo.ac.jp\/crest-model\/wp-json\/wp\/v2\/posts\/118\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.opt.mist.i.u-tokyo.ac.jp\/crest-model\/wp-json\/wp\/v2\/media?parent=118"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.opt.mist.i.u-tokyo.ac.jp\/crest-model\/wp-json\/wp\/v2\/categories?post=118"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.opt.mist.i.u-tokyo.ac.jp\/crest-model\/wp-json\/wp\/v2\/tags?post=118"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}