\u65e5\u6642 \uff1a 2016\u5e74 4\u670821\u65e5(\u6728) 15:00 \uff5e 16:00<\/p>\n
\u5834\u6240 \uff1a \u6771\u4eac\u5927\u5b66 \u672c\u90f7\u30ad\u30e3\u30f3\u30d1\u30b9 \u5de5\u5b66\u90e8 14\u53f7\u9928 5\u968e 534\u53f7\u5ba4<\/p>\n
\u8b1b\u6f14\u8005\uff1a Alantha Newman (G-SCOP, Grenoble)<\/p>\n
\u8b1b\u6f14\u984c\u76ee:
\nThe Alternating Stock Size Problem and the Gasoline Puzzle<\/p>\n
\u8b1b\u6f14\u6982\u8981:
\nGiven a set S of integers whose sum is zero, consider the
\nproblem of finding a permutation of these integers such that:
\n(i) all prefixes of the ordering are non-negative, and
\n(ii) the maximum value of a prefix sum is minimized.
\nKellerer et al. referred to this problem as the
\n“Stock Size Problem” and showed that it can be approximated
\nto within 3\/2. They also showed that an approximation
\nratio of 2 can be achieved via several simple algorithms.<\/p>\n
We consider a related problem, which we call the “Alternating Stock
\nSize Problem”, where the number of positive and negative integers in
\nthe input set S are equal. The problem is the same as above, but we
\nare additionally required to alternate the positive and negative
\nnumbers in the output ordering. This problem also has several simple
\n2-approximations. We show that it can be approximated to within 1.79.<\/p>\n
Then we show that this problem is closely related to an optimization
\nversion of the Gasoline Puzzle due to Lovasz, in which we want to
\nminimize the size of the gas tank necessary to go around the track.
\nWe give a 2-approximation for this problem, based on rounding an LP
\nrelaxation whose feasible solutions are convex combinations of
\npermutation matrices.<\/p>\n
This is joint work with Heiko Roeglin (Universitaet Bonn) and Johanna
\nSeif (ENS Lyon).<\/p>\n","protected":false},"excerpt":{"rendered":"
\u65e5\u6642 \uff1a 2016\u5e74 4\u670821\u65e5(\u6728) 15:00 \uff5e 16:00 \u5834\u6240 \uff1a \u6771\u4eac\u5927\u5b66 \u672c\u90f7\u30ad\u30e3\u30f3\u30d1… <\/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-257","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\/257","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=257"}],"version-history":[{"count":0,"href":"https:\/\/www.opt.mist.i.u-tokyo.ac.jp\/crest-model\/wp-json\/wp\/v2\/posts\/257\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.opt.mist.i.u-tokyo.ac.jp\/crest-model\/wp-json\/wp\/v2\/media?parent=257"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.opt.mist.i.u-tokyo.ac.jp\/crest-model\/wp-json\/wp\/v2\/categories?post=257"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.opt.mist.i.u-tokyo.ac.jp\/crest-model\/wp-json\/wp\/v2\/tags?post=257"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}