Ця стаття є сирим з іншої мови. Можливо, вона створена за допомогою машинного перекладу або перекладачем, який недостатньо володіє обома мовами. (липень 2020) |
У теорії складності обчислень задача про розміщення в ємності (посудини) — NP-складна комбінаторна задача. Задача полягає в пакуванні об'єктів визначеної завідомо форми в скінченне число ємностей (також кажуть контейнерів) - теж завідомо відомої заздалегідь форми у такий спосіб, аби число використаних ємностей було найменшим, або кількість чи об'єм предметів (які розміщують) були якнайбільшими.
Різновиди та методи розв'язування задач упакування
Існує безліч різновидів цієї задачі (, , пакування на вагу, за вартістю тощо), що можуть застосовуватись у різних галузях, як власне у питанні якнайвигіднішого наповнення ємностей, навантаження напіввагона чи вантажівки з ваговим обмеженням; створення резервних копій на знімних носіях тощо.
Оскільки задача є NP-складною, то застосування точного перебірного алгоритму припустиме лише за невеликих розмірностей. Зазвичай для розв'язування цієї задачі використовують евристичні наближені поліноміальні алгоритми.
Спрощений підхід
Попри те, що математики зараз часто розв'язують нікому не потрібні задачі й уважають повсякденне життя за частинний випадок, не можна забувати про те, що найкращий розв'язок — це той, який нескладний, доступний для нематематиків та підходить для використання у побутових умовах (неможливо вираховувати годинами чи добами ідеальний варіант, коли, на приклад, рішення потрібно було прийняти «ще на тому тижні», комп'ютер старий і повільний, і як на те, ще й вимкнулось світло). Ледачий (жадібний) підхід, очевидно, є незамінним при розв'язуванні життєвих задач. Алгоритм обробляє речі в довільному порядку. Кожну річ він намагається помістити у першу-ліпшу посудину, куди вона здатна ввійти. Якщо такої не знайде, він дозволить відкрити нову посудину (в житті — сумку або вантажний вагон, або контейнер) і ставить його туди. Точно те саме роблять люди, коли переміщують досить значні речі: ще одну сумку, возик або валізу беруть лише в тому разі, коли неможливо помістити все у ті сумки, які у вас є. А ось вирішити, чи вам їхати поїздом, чи автобусом, чи машиною, а, може, вам взагалі треба відправляти вантаж товарним вагоном, цей алгоритм вам не допоможе, а якщо і допоможе, то неповністю: він не вміє визначити, чи помнуться речі у посудинах в такому положенні, чи можна (а якщо можна — то чи припустимо) їх стиснути або згорнути, наскільки легко їх буде дістати тощо. У цьому і полягає перевага людського мозку над комп'ютером.
Жадібний алгоритм забезпечує коефіцієнт наближення 2, тобто, кількість задіяних посудин не перевищить більш, ніж у два рази ту найвигіднішу їх кількість, яку комп'ютер буде вираховувати неприпустимо довго.
Задача про розміщення в одновимірні однакові ємності
Постановка задачі
Нехай дана множина ємностей розміру і множина предметів розмірів . Необхідно знайти ціле число ємностей і на таких підмножин , що для всіх . Очевидно, що менше , тим вигідніший розв'язок вдалося знайти. Найменше можливе надалі позначатимемо OPT.
Пакування як задача лінійного програмування
Задача пакування в ємності може бути задана як задача лінійного програмування наступним чином:
Мінімізувати | ||
при обмеженнях | ||
де , якщо ємність використовується, й , якщо предмет поміщено в ємність .
Наближені поліноміальні алгоритми
Найпростішими поліноміальними алгоритмами пакування вважають алгоритми Best Fit Decreasing — BFD (Наліпший підходящий за спаданням) і First Fit Decreasing — FFD (Перший підходящий за спаданням). Предмети упорядковують за незростанням розміру й послідовно розміщують або в ємність, у якій після того залишиться якнайменший вільний об'єм — BFD, або в першу ємність, у які він входить (просторочо та/або за вагою) — FFD. Доведено, що ці алгоритми використають не більш як
ємностей.
Однак для задачі упакування існують й асимптотично ε -оптимальні поліноміальні алгоритми.
Задача визначити, чи рівне OPT двом або трьом є NP-складною. Тому для довільного ε > 0 важко розмістити предмети до (3/2 − ε)OPT ємностей. (Якщо такий поліноміальний алгоритм існує, то за поліноміальний час можна визначити, чи розділиться n невід'ємних чисел на дві множини з однаковою сумою елементів. Однак відомо, що це питання NP-складне.) Відповідно, якщо P не збігається з NP, то для задачі упакування в ємності немає алгоритму схеми наближення до поліноміального часу (PTAS). З іншогобоку, для довільного ε >0 можна знайти рішення, як розмістити у не більш, ніж (1 + ε)OPT + 1 ємностей за поліноміальний час. Такі алгоритми відносять до асимптотичної PTAS. Але оскільки в оцінці склааності цього класу алгоритмів обидві константи довільно залежать від ε, подібні алгоритми, на відміну від FFD и BFD, насправді зовсім некорисні для життєвих задач.
Ймовірнісний підхід
Для певного класу ймовірнісного розподілу розмірів розміщених предметів, що включає опуклі вгору та внизу функції розподілу, існує практичний поліноміальний алгоритм пакування, асимптотично оптимальний майже напевне за необмеженого росту числа предметів. Для розподілів поза цим класом можна будувати власні поліноміальні асимптотичні оптимальні алгоритми..
Примітки
- Silvano Martello and Paolo Toth (1990). Knapsack problems. Chichester, UK: John Wiley and Sons. с. 221. ISBN .
- Yue, Minyi (October 1991), A simple proof of the inequality FFD (L) ≤ 11/9 OPT (L) + 1, ∀L for the FFD bin-packing algorithm, Acta Mathematicae Applicatae Sinica, 7 (4): 321—331, doi:10.1007/BF02009683, ISSN 0168-9673
{{}}
: Проігноровано|contribution=
() - Fernandez de la Vega, W.; Lueker, G. S. (December 1981), Bin packing can be solved within 1 + ε in linear time, Combinatorica, Springer Berlin / Heidelberg, 1 (4): 349—355, doi:10.1007/BF02579456, ISSN 0209-9683
{{}}
: Проігноровано|contribution=
() - Смирнов А. В. Оптимізація процесу обробки даних в локальних мережах ЕОМ. — 1991.
Див. також
Бібліографія
Джерела
- Бернард Корте, Єнс Вигон: Комбінаторна оптимізація. - Берлін/Хайдельберг: Спрінгер, 2008, , Стор. 485
Мережеві посилання на матеріали
- PHP Class to pack files without exceeding a given size limit [ 27 грудня 2015 у Wayback Machine.]
- An implementation of several bin packing heuristics in Haskell [ 1 липня 2020 у Wayback Machine.], including FFD and MFFD.
- Cutting And Packing Algorithms Research Framework [ 31 грудня 2015 у Wayback Machine.], including a number of bin packing algorithms and test data.
- A simple on-line bin-packing algorithm
- Optimizing Three-Dimensional Bin Packing [ 5 березня 2016 у Wayback Machine.]
- Fpart : open-source command-line tool to pack files (C, BSD-licensed) [ 1 грудня 2015 у Wayback Machine.]
- Bin Packing and Cutting Stock Solver Algorithm [ 27 грудня 2015 у Wayback Machine.]
Увага! Бракує посилань на українські сайти. Хто їх знає - додайте їх сюди!
Перелік книг
- Korf, Richard E. (2002), (PDF), архів оригіналу (PDF) за 27 грудня 2015, процитовано 26 грудня 2015
- (2003), Approximation Algorithms, Berlin: Springer, ISBN
- Yue, Minyi (October 1991), A simple proof of the inequality FFD (L) ≤ 11/9 OPT (L) + 1, ∀L for the FFD bin-packing algorithm, Acta Mathematicae Applicatae Sinica, 7 (4): 321—331, doi:10.1007/BF02009683, ISSN 0168-9673
{{}}
: Проігноровано|contribution=
() - Dósa, György (2007), The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I)≤(11/9)OPT(I)+6/9, у Chen, Bo; Paterson, Mike; Zhang, Guochuan (ред.), Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, т. 4614/2007, Springer Berlin / Heidelberg, с. 1—11, doi:10.1007/978-3-540-74450-4, ISBN , ISSN 0302-9743
- Xia, Binzhou; Tan, Zhiyi (2010), Tighter bounds of the First Fit algorithm for the bin-packing problem, Discrete Applied Mathematics, 158 (15): 1668—1675, doi:10.1016/j.dam.2010.05.026, ISSN 0166-218X
{{}}
: Проігноровано|contribution=
() - ; Johnson, David S. (1985), A 71/60 theorem for bin packing*1, Journal of Complexity, 1: 65—106, doi:10.1016/0885-064X(85)90022-6
{{}}
: Проігноровано|contribution=
() - Yue, Minyi; Zhang, Lei (July 1995), A simple proof of the inequality MFFD(L)≤71/60 OPT(L) + 1,L for the MFFD bin-packing algorithm, Acta Mathematicae Applicatae Sinica, 11 (3): 318—330, doi:10.1007/BF02011198, ISSN 0168-9673
{{}}
: Проігноровано|contribution=
() - Fernandez de la Vega, W.; Lueker, G. S. (December 1981), Bin packing can be solved within 1 + ε in linear time, Combinatorica, Springer Berlin / Heidelberg, 1 (4): 349—355, doi:10.1007/BF02579456, ISSN 0209-9683
{{}}
: Проігноровано|contribution=
() - Lewis, R. (2009), A General-Purpose Hill-Climbing Method for Order Independent Minimum Grouping Problems: A Case Study in Graph Colouring and Bin Packing, Computers and Operations Research, 36 (7): 2295—2310, doi:10.1016/j.cor.2008.09.004
- Silvano Martello and Paolo Toth (1990), Knapsack Problems Algorithms and Computer Implementations.
- Michael R. Garey and David S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. . A4.1: SR1, p. 226.
- David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, M. R. Garey, Ronald L. Graham. Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms [ 9 жовтня 2016 у Wayback Machine.]. SICOMP, Volume 3, Issue 4. 1974.
- Lodi A., Martello S., Monaci, M., Vigo, D. (2010) Two-Dimensional Bin Packing Problems. In V.Th. Paschos (Ed.), “Paradigms of Combinatorial Optimization”, Wiley/ISTE, p. 107-129
- Dósa G., Sgall J. (2013) First Fit bin packing: A tight analysis. To appear in STACS 2013.
- Sindelar, Michael; ; Shenoy, Prashant (2011), Sharing-Aware Algorithms for Virtual Machine Colocation, Proceedings of 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), San Jose, CA, June 2011: 367—378
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Cya stattya ye sirim perekladom z inshoyi movi Mozhlivo vona stvorena za dopomogoyu mashinnogo perekladu abo perekladachem yakij nedostatno volodiye oboma movami Bud laska dopomozhit polipshiti pereklad lipen 2020 U teoriyi skladnosti obchislen zadacha pro rozmishennya v yemnosti posudini NP skladna kombinatorna zadacha Zadacha polyagaye v pakuvanni ob yektiv viznachenoyi zavidomo formi v skinchenne chislo yemnostej takozh kazhut kontejneriv tezh zavidomo vidomoyi zazdalegid formi u takij sposib abi chislo vikoristanih yemnostej bulo najmenshim abo kilkist chi ob yem predmetiv yaki rozmishuyut buli yaknajbilshimi Riznovidi ta metodi rozv yazuvannya zadach upakuvannyaIsnuye bezlich riznovidiv ciyeyi zadachi pakuvannya na vagu za vartistyu tosho sho mozhut zastosovuvatis u riznih galuzyah yak vlasne u pitanni yaknajvigidnishogo napovnennya yemnostej navantazhennya napivvagona chi vantazhivki z vagovim obmezhennyam stvorennya rezervnih kopij na znimnih nosiyah tosho Oskilki zadacha ye NP skladnoyu to zastosuvannya tochnogo perebirnogo algoritmu pripustime lishe za nevelikih rozmirnostej Zazvichaj dlya rozv yazuvannya ciyeyi zadachi vikoristovuyut evristichni nablizheni polinomialni algoritmi Sproshenij pidhidPopri te sho matematiki zaraz chasto rozv yazuyut nikomu ne potribni zadachi j uvazhayut povsyakdenne zhittya za chastinnij vipadok ne mozhna zabuvati pro te sho najkrashij rozv yazok ce toj yakij neskladnij dostupnij dlya nematematikiv ta pidhodit dlya vikoristannya u pobutovih umovah nemozhlivo virahovuvati godinami chi dobami idealnij variant koli na priklad rishennya potribno bulo prijnyati she na tomu tizhni komp yuter starij i povilnij i yak na te she j vimknulos svitlo Ledachij zhadibnij pidhid ochevidno ye nezaminnim pri rozv yazuvanni zhittyevih zadach Algoritm obroblyaye rechi v dovilnomu poryadku Kozhnu rich vin namagayetsya pomistiti u pershu lipshu posudinu kudi vona zdatna vvijti Yaksho takoyi ne znajde vin dozvolit vidkriti novu posudinu v zhitti sumku abo vantazhnij vagon abo kontejner i stavit jogo tudi Tochno te same roblyat lyudi koli peremishuyut dosit znachni rechi she odnu sumku vozik abo valizu berut lishe v tomu razi koli nemozhlivo pomistiti vse u ti sumki yaki u vas ye A os virishiti chi vam yihati poyizdom chi avtobusom chi mashinoyu a mozhe vam vzagali treba vidpravlyati vantazh tovarnim vagonom cej algoritm vam ne dopomozhe a yaksho i dopomozhe to nepovnistyu vin ne vmiye viznachiti chi pomnutsya rechi u posudinah v takomu polozhenni chi mozhna a yaksho mozhna to chi pripustimo yih stisnuti abo zgornuti naskilki legko yih bude distati tosho U comu i polyagaye perevaga lyudskogo mozku nad komp yuterom Zhadibnij algoritm zabezpechuye koeficiyent nablizhennya 2 tobto kilkist zadiyanih posudin ne perevishit bilsh nizh u dva razi tu najvigidnishu yih kilkist yaku komp yuter bude virahovuvati nepripustimo dovgo Zadacha pro rozmishennya v odnovimirni odnakovi yemnostiPostanovka zadachi Nehaj dana mnozhina yemnostej rozmiru V displaystyle V i mnozhina n displaystyle n predmetiv rozmiriv a1 an displaystyle a 1 dots a n Neobhidno znajti cile chislo yemnostej B displaystyle B i 1 n displaystyle 1 dots n na B displaystyle B takih pidmnozhin S1 SB displaystyle S 1 cup dots cup S B sho i Skai V displaystyle sum i in S k a i leq V dlya vsih k 1 B displaystyle k 1 dots B Ochevidno sho menshe B displaystyle B tim vigidnishij rozv yazok vdalosya znajti Najmenshe mozhlive B displaystyle B nadali poznachatimemo OPT Pakuvannya yak zadacha linijnogo programuvannya Zadacha pakuvannya v yemnosti mozhe buti zadana yak zadacha linijnogo programuvannya nastupnim chinom Minimizuvati B i 1nyi displaystyle B sum i 1 n y i pri obmezhennyah j 1najxij Vyi displaystyle sum j 1 n a j x ij leq Vy i i 1 n displaystyle forall i in 1 ldots n i 1nxij 1 displaystyle sum i 1 n x ij 1 j 1 n displaystyle forall j in 1 ldots n yi 0 1 displaystyle y i in 0 1 i 1 n displaystyle forall i in 1 ldots n xij 0 1 displaystyle x ij in 0 1 i 1 n j 1 n displaystyle forall i in 1 ldots n forall j in 1 ldots n de yi 1 displaystyle y i 1 yaksho yemnist i displaystyle i vikoristovuyetsya j xij 1 displaystyle x ij 1 yaksho predmet j displaystyle j pomisheno v yemnist i displaystyle i Nablizheni polinomialni algoritmi Najprostishimi polinomialnimi algoritmami pakuvannya vvazhayut algoritmi Best Fit Decreasing BFD Nalipshij pidhodyashij za spadannyam i First Fit Decreasing FFD Pershij pidhodyashij za spadannyam Predmeti uporyadkovuyut za nezrostannyam rozmiru j poslidovno rozmishuyut abo v yemnist u yakij pislya togo zalishitsya yaknajmenshij vilnij ob yem BFD abo v pershu yemnist u yaki vin vhodit prostorocho ta abo za vagoyu FFD Dovedeno sho ci algoritmi vikoristayut ne bilsh yak 119OPT 1 displaystyle frac 11 9 OPT 1 yemnostej Odnak dlya zadachi upakuvannya isnuyut j asimptotichno e optimalni polinomialni algoritmi Zadacha viznachiti chi rivne OPT dvom abo trom ye NP skladnoyu Tomu dlya dovilnogo e gt 0 vazhko rozmistiti predmeti do 3 2 e OPT yemnostej Yaksho takij polinomialnij algoritm isnuye to za polinomialnij chas mozhna viznachiti chi rozdilitsya n nevid yemnih chisel na dvi mnozhini z odnakovoyu sumoyu elementiv Odnak vidomo sho ce pitannya NP skladne Vidpovidno yaksho P ne zbigayetsya z NP to dlya zadachi upakuvannya v yemnosti nemaye algoritmu shemi nablizhennya do polinomialnogo chasu PTAS Z inshogoboku dlya dovilnogo e gt 0 mozhna znajti rishennya yak rozmistiti u ne bilsh nizh 1 e OPT 1 yemnostej za polinomialnij chas Taki algoritmi vidnosyat do asimptotichnoyi PTAS Ale oskilki v ocinci sklaanosti cogo klasu algoritmiv anb displaystyle an b obidvi konstanti dovilno zalezhat vid e podibni algoritmi na vidminu vid FFD i BFD naspravdi zovsim nekorisni dlya zhittyevih zadach Jmovirnisnij pidhid Dlya pevnogo klasu jmovirnisnogo rozpodilu rozmiriv rozmishenih predmetiv sho vklyuchaye opukli vgoru ta vnizu funkciyi rozpodilu isnuye praktichnij polinomialnij algoritm pakuvannya asimptotichno optimalnij majzhe napevne za neobmezhenogo rostu chisla predmetiv Dlya rozpodiliv poza cim klasom mozhna buduvati vlasni polinomialni asimptotichni optimalni algoritmi PrimitkiSilvano Martello and Paolo Toth 1990 Knapsack problems Chichester UK John Wiley and Sons s 221 ISBN 0471924202 Yue Minyi October 1991 A simple proof of the inequality FFD L 11 9 OPT L 1 L for the FFD bin packing algorithm Acta Mathematicae Applicatae Sinica 7 4 321 331 doi 10 1007 BF02009683 ISSN 0168 9673 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Citation title Shablon Citation citation a Proignorovano contribution dovidka Fernandez de la Vega W Lueker G S December 1981 Bin packing can be solved within 1 e in linear time Combinatorica Springer Berlin Heidelberg 1 4 349 355 doi 10 1007 BF02579456 ISSN 0209 9683 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Citation title Shablon Citation citation a Proignorovano contribution dovidka Smirnov A V Optimizaciya procesu obrobki danih v lokalnih merezhah EOM 1991 Div takozhZadacha pro ranec Zadacha pro sumu pidmnozhin OptimizaciyaBibliografiyaDzherela Bernard Korte Yens Vigon Kombinatorna optimizaciya Berlin Hajdelberg Springer 2008 ISBN 978 3 540 76918 7 Stor 485Merezhevi posilannya na materiali PHP Class to pack files without exceeding a given size limit 27 grudnya 2015 u Wayback Machine An implementation of several bin packing heuristics in Haskell 1 lipnya 2020 u Wayback Machine including FFD and MFFD Cutting And Packing Algorithms Research Framework 31 grudnya 2015 u Wayback Machine including a number of bin packing algorithms and test data A simple on line bin packing algorithm Optimizing Three Dimensional Bin Packing 5 bereznya 2016 u Wayback Machine Fpart open source command line tool to pack files C BSD licensed 1 grudnya 2015 u Wayback Machine Bin Packing and Cutting Stock Solver Algorithm 27 grudnya 2015 u Wayback Machine Uvaga Brakuye posilan na ukrayinski sajti Hto yih znaye dodajte yih syudi Perelik knig Korf Richard E 2002 PDF arhiv originalu PDF za 27 grudnya 2015 procitovano 26 grudnya 2015 2003 Approximation Algorithms Berlin Springer ISBN 3 540 65367 8 Yue Minyi October 1991 A simple proof of the inequality FFD L 11 9 OPT L 1 L for the FFD bin packing algorithm Acta Mathematicae Applicatae Sinica 7 4 321 331 doi 10 1007 BF02009683 ISSN 0168 9673 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Citation title Shablon Citation citation a Proignorovano contribution dovidka Dosa Gyorgy 2007 The Tight Bound of First Fit Decreasing Bin Packing Algorithm Is FFD I 11 9 OPT I 6 9 u Chen Bo Paterson Mike Zhang Guochuan red Combinatorics Algorithms Probabilistic and Experimental Methodologies t 4614 2007 Springer Berlin Heidelberg s 1 11 doi 10 1007 978 3 540 74450 4 ISBN 978 3 540 74449 8 ISSN 0302 9743 Xia Binzhou Tan Zhiyi 2010 Tighter bounds of the First Fit algorithm for the bin packing problem Discrete Applied Mathematics 158 15 1668 1675 doi 10 1016 j dam 2010 05 026 ISSN 0166 218X a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Citation title Shablon Citation citation a Proignorovano contribution dovidka Johnson David S 1985 A 71 60 theorem for bin packing 1 Journal of Complexity 1 65 106 doi 10 1016 0885 064X 85 90022 6 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Citation title Shablon Citation citation a Proignorovano contribution dovidka Yue Minyi Zhang Lei July 1995 A simple proof of the inequality MFFD L 71 60 OPT L 1 L for the MFFD bin packing algorithm Acta Mathematicae Applicatae Sinica 11 3 318 330 doi 10 1007 BF02011198 ISSN 0168 9673 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Citation title Shablon Citation citation a Proignorovano contribution dovidka Fernandez de la Vega W Lueker G S December 1981 Bin packing can be solved within 1 e in linear time Combinatorica Springer Berlin Heidelberg 1 4 349 355 doi 10 1007 BF02579456 ISSN 0209 9683 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Citation title Shablon Citation citation a Proignorovano contribution dovidka Lewis R 2009 A General Purpose Hill Climbing Method for Order Independent Minimum Grouping Problems A Case Study in Graph Colouring and Bin Packing Computers and Operations Research 36 7 2295 2310 doi 10 1016 j cor 2008 09 004 Silvano Martello and Paolo Toth 1990 Knapsack Problems Algorithms and Computer Implementations Michael R Garey and David S Johnson 1979 Computers and Intractability A Guide to the Theory of NP Completeness W H Freeman ISBN 0 7167 1045 5 A4 1 SR1 p 226 David S Johnson Alan J Demers Jeffrey D Ullman M R Garey Ronald L Graham Worst Case Performance Bounds for Simple One Dimensional Packing Algorithms 9 zhovtnya 2016 u Wayback Machine SICOMP Volume 3 Issue 4 1974 Lodi A Martello S Monaci M Vigo D 2010 Two Dimensional Bin Packing Problems In V Th Paschos Ed Paradigms of Combinatorial Optimization Wiley ISTE p 107 129 Dosa G Sgall J 2013 First Fit bin packing A tight analysis To appear in STACS 2013 Sindelar Michael Shenoy Prashant 2011 Sharing Aware Algorithms for Virtual Machine Colocation Proceedings of 23rd ACM Symposium on Parallelism in Algorithms and Architectures SPAA San Jose CA June 2011 367 378