國立虎尾科技大學 |

Bin Packing, Number Balancing, and Rescaling Linear Programs.

紀錄類型:	書目-語言資料,手稿 : Monograph/item
正題名/作者:	Bin Packing, Number Balancing, and Rescaling Linear Programs./
作者:	Hoberg, Rebecca.
面頁冊數:	1 online resource (81 pages)
附註:	Source: Dissertation Abstracts International, Volume: 79-01(E), Section: B.
Contained By:	Dissertation Abstracts International79-01B(E).
標題:	Mathematics. -
電子資源:	click for full text (PQDT)
ISBN:	9780355121872

Bin Packing, Number Balancing, and Rescaling Linear Programs.
Hoberg, Rebecca.

Bin Packing, Number Balancing, and Rescaling Linear Programs. - 1 online resource (81 pages)

Source: Dissertation Abstracts International, Volume: 79-01(E), Section: B.

Thesis (Ph.D.)

Includes bibliographical references

This thesis deals with several important algorithmic questions using techniques from diverse areas including discrepancy theory, machine learning and lattice theory.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2018

Mode of access: World Wide Web

ISBN: 9780355121872Subjects--Topical Terms:

527692
Mathematics.
Index Terms--Genre/Form:

554714
Electronic books.

Bin Packing, Number Balancing, and Rescaling Linear Programs.
LDR:04188ntm a2200385Ki 4500 001 909813
005 20180426091047.5
006 m o u
007 cr mn||||a|a||
008 190606s2017 xx obm 000 0 eng d
020 $a 9780355121872
035 $a (MiAaPQ)AAI10288726
035 $a (MiAaPQ)washington:17221
035 $a AAI10288726
040 $a MiAaPQ $b eng $c MiAaPQ
099 $a TUL $f hyy $c available through World Wide Web
100 1 $a Hoberg, Rebecca. $3 1180775
245 1 0 $a Bin Packing, Number Balancing, and Rescaling Linear Programs.
264 0 $c 2017
300 $a 1 online resource (81 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertation Abstracts International, Volume: 79-01(E), Section: B.
500 $a Adviser: Thomas Rothvoss.
502 $a Thesis (Ph.D.) $c University of Washington $d 2017.
504 $a Includes bibliographical references
520 $a This thesis deals with several important algorithmic questions using techniques from diverse areas including discrepancy theory, machine learning and lattice theory.
520 $a In Chapter 2, we construct an improved approximation algorithm for a classical NP-complete problem, the bin packing problem. In this problem, the goal is to pack items of sizes si ∈ [0,1] into as few bins as possible, where a set of items fits into a bin provided the sum of the item sizes is at most one. We give a polynomial-time rounding scheme for a standard linear programming relaxation of the problem, yielding a packing that uses at most OPT + O(log OPT) bins. This makes progress towards one of the "10 open problems in approximation algorithms" stated in the book of Shmoys and Williamson. In fact, based on related combinatorial lower bounds, Rothvoss conjectures that theta(logOPT) may be a tight bound on the additive integrality gap of this LP relaxation.
520 $a In Chapter 3, we give a new polynomial-time algorithm for linear programming. Our algorithm is based on the multiplicative weights update (MWU) method, which is a general framework that is currently of great interest in theoretical computer science. An algorithm for linear programming based on MWU was known previously, but was not polynomial time---we remedy this by alternating between a MWU phase and a rescaling phase. The rescaling methods we introduce improve upon previous methods by reducing the number of iterations needed until one can rescale, and they can be used for any algorithm with a similar rescaling structure. Finally, we note that the MWU phase of the algorithm has a simple interpretation as gradient descent of a particular potential function, and we show we can speed up this phase by walking in a direction that decreases both the potential function and its gradient.
520 $a In Chapter 4, we show that an approximate oracle for Minkowski's Theorem gives an approximate oracle for the number balancing problem, and conversely. Number balancing is the problem of minimizing | &lang;a,x&rang; | over x ∈ {--1,0,1}n \ { 0}, given a ∈ [0,1]n. While an application of the pigeonhole principle shows that there always exists x with | &lang;a,x&rang;| ≤ O(√ n/2n), the best known algorithm only guarantees |&lang;a,x&rang;| ≤ 2--ntheta(log n). We show that an oracle for Minkowski's Theorem with approximation factor rho would give an algorithm for NBP that guarantees | &lang;a,x&rang; | ≤ 2--ntheta(1/rho). In particular, this would beat the bound of Karmarkar and Karp provided rho ≤ O(logn/loglogn). In the other direction, we prove that any polynomial time algorithm for NBP that guarantees a solution of difference at most 2√n/2 n would give a polynomial approximation for Minkowski as well as a polynomial factor approximation algorithm for the Shortest Vector Problem.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2018
538 $a Mode of access: World Wide Web
650 4 $a Mathematics. $3 527692
650 4 $a Computer science. $3 573171
655 7 $a Electronic books. $2 local $3 554714
690 $a 0405
690 $a 0984
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a University of Washington. $b Mathematics. $3 1179079
773 0 $t Dissertation Abstracts International $g 79-01B(E).
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10288726 $z click for full text (PQDT)