\documentclass[b5paper,12pt]{book}
%\usepackage{AML-2011aprilis9}
%\usepackage{AlkMat-2011apr7}
%\usepackage{Knuth-jun29-black}
\usepackage{Knuth-jul1-blue}

\makeindex
\addtocounter{chapter}{1}
\def\binom#1#2{\left(\strut\displaystyle{#1 \atop #2}\right)}
\def\textbinom#1#2{\left(\strut\textstyle{#1 \atop #2}\right)}


\begin{document}

\begin{center}
\Large
\textcolor{blue}{\textbf{\sf{ÜTEMEZÕ ALGORITMUSOK HIBAFÜGGVÉNYEI}}}

\vspace{4mm}
\textcolor{blue}{\textbf{\sf{(Processzorszámot minimalizáló algoritmusok)}}}

\vspace{4mm}
\textcolor{blue}{\textbf{\sf{Iványi Antal, 2011. április 12.}}}

\normalsize
\vspace{4mm}
(Ez a kézirat letölthetõ a következõ címrõl: 
\hrefun{http://compalg.inf.elte.hu/~tony/Kutatas/TAMOP/Papers-in-journals/}
{http://compalg.inf.elte.hu/$\sim$~tony/Kutatas/TAMOP/Papers-in-journals/})
\end{center}





\section*{1. Bevezetés}
Tegyük fel, hogy egymástól független programokat kell futtatnunk, és minden számítógép csak egységnyi ideig mûködik (az egység 
lehet például egy 8 órás mûszak). Célunk a programok olyan szétosztása a gépek között, hogy minél kevesebb gépet használjunk.

A feladat formális megfogalmazása a következõ. Legyen $n \geq 1$ egész szám, $\mathbf{t} = (t_1, t_2, \ldots, t_n)$ pedig 
valós számokat tartalmazó vektor, ahol $t_i \in (0,1]$ minden  $i = 1, \ 2, \ldots, \ n$ indexre. Osszuk fel a sorozatot 
minél kevesebb olyan részsorozatra, melyekben az elemek összege legfeljebb 1.

A feladat egydimenziós ládapakolási feladatként is ismert \cite{CormenLRS2009,Csirik1989,GareyJ1979,LovászG1989}. 
A feladat NP-teljes\index{NP-teljes = NP-complete}\angolnevindex{NP-complete = NP-teljes} 
\cite{CormenLRS2009,GareyJ1979}\nevindex{Cormen, T. H.}\nevindex{Leisenson, Ch. E}\nevindex{Rivest, R. L.}\nevindex{Stein, C.} 
(például visszavezethetõ az összegzési feladatra 
\cite{CormenLRS2009,GareyJ1979}), ezért a gyakorlati megoldásra közelítõ algoritmusokat 
\cite{Csirik1989,DosaI2011,Galambos} alkalmaznak.\nevindex{Csirik János}\nevindex{Galambos Gábor}\nevindex{Dósa György} 

Az A és B algoritmus relatív hatékonyságát gyakran jellemzik a kiválasztott 
hatékonysági mérték értékeinek hányadosával, jelen esetben az A(\textbf(t)/B\textbf(t) 
relatív ládaszámmal.\index{relatív ládaszám = relatív number of bins}\angolnevindex{relativ number of bins = relatív ládaszám} 
Ennek a hányadosnak a felhasználásával különbözõ jellemzõk 
definiálhatók, például a relatív ládaszám 
legrosszabb,\index{relatív ládaszám legrosszabb  esete = worst case of the relative number of bins}
\angolnevindex{worst case of the relative number of bins = relatív ládaszám legrosszabb  esete} 
várható\index{relatív ládaszám várható értéke = expected value of relative number of bins} és 
\angolnevindex{expected value of relative number of bins = relatív ládaszám várható értéke}
legjobb\index{relatív ládaszám legjobb esete = best case of the relative number of bins} esete. 

Ebben a cikkben a legismertebb közelítõ (NF, FF, BF, NFD, BFD, FFD)  
 \cite{CoffmanGJ1984,Ivanyi1984Comp,Ivanyi1984Kib,Ivanyi1985,Johnson1973} 
és becslõ (MAX, SUM, BIG, UPP) \cite{Aszalos1988,AszalosITZs1988,Johnson1973} 
algoritmusok legrosszabb esetére vonatkozó eredményeket foglaljuk össze
\index{NF = Next Fit}\index{FF = First Fit}\index{BF = Best Fit}\index{NFD = Next Fit Decreading}
\index{FFD = First Fit Decreasing}\index{BFD = Best Fit Decreasing}\index{MAX = Maximum}
\index{BIG}\index{UPP = Upper}\index{SUM = Sum of the sizes}


Az átlagos eset vizsgálata rendszerint lényegesen nehezebb, míg a legjobb eset vizsgálata rendszerint könnyû. 

Legyen $\mathcal{D}_n$ azon valós listák halmaza, amelyek $n$ elemet tartalmaznak, és legyen $\mathcal{D}$ 
az összes valós lista halmaza, azaz
\begin{equation}
D =   \bigcup _ {i=1} ^{\infty} \ D_i \koz .
\end{equation}

Legyen $\mathcal{A}_{\var{pak}}$ a minden $\mathbf{t} \in \mathcal{D}$ 
listához egy nemnegatív valós számot hozzárendelõ, és így a $\mathcal{D} \rightarrow \R^+_0$ 
leképezést megvalósító algoritmusok halmaza. Ezeket az algoritmusokat 
\ki{ládapakoló}\inddef{ládapakoló algoritmus = bin packing algorithm}
\angolnevindex{bin packing algorithm} algoritmusoknak nevezzük annak ellenére, hogy nem állítanak elõ konkrét pakolást, 
legfeljebb az optimális ládaszám valamilyen becslését adják.

Legyen $\mathcal{A}_{\var{opt}}$ a minden listához az optimális ládaszámot rendelõ algoritmusok 
halmaza, és \textsc{OPT} ennek a halmaznak egy eleme (azaz egy olyan algoritmus, amely minden 
$\mathbf{t} \in D$ listához megadja a listához tartozó tárgyak elhelyezéséhez szükséges 
és elégséges ládák számát). 

Legyen $\mathcal{A}_{\var{köz}}$ azon A $\in \mathcal{A}_{\var{pak}}$ algoritmusok halmaza, 
amelyekre A(\textbf{t}) $\geq$ OPT(\textbf{t}) minden 
$\mathbf{t} \in D$ listára, és van olyan $\mathbf{t} \in D$ lista, amelyre A(\textbf{t}) 
> OPT(\textbf{t}). Legyen $A_{\var{becs}}$ azon E $ \in \mathcal{A}_{\var{pak}}$  
algoritmusok halmaza, amelyekre $0 \leq$ E(\textbf{t}) $\leq$ OPT(\textbf{t}) minden 
$\mathbf{t} \in D$ listára, és van olyan $\mathbf{t} \in D$ lista, amelyre 
E(\textbf{t}) < OPT(\textbf{t}). 

Legyen $F_n$ azon valós listák halmaza, amelyekre OPT(\textbf{t}) = $n,$ azaz 
$F_n = \{\mathbf{t} \ | \ \mathbf{t} \in D$ és OPT(\textbf{t}) = $n  \ (n = 1, 2, \ldots )\}$.  
Az A és B $\in \mathcal{A}_{\var{köz}})$ algoritmusok $R_{\textsc{A,B,}n}$ hibafüggvényét, 
$R_{\textsc{A,B}}$ abszolut hibáját (röviden: hibáját) és $R_{A,\infty}$ aszimptotikus hibáját 
a következõképpen definiáljuk:

\begin{equation}
R_{\textsc{A,B},n} = \sup _{t \in F_n} \frac{\textsc{A}(\mathbf{t})}{\textsc{B}(\mathbf{t})} \koz ,\label{eq-RABn}
\end{equation}
\begin{equation} 
R_{\textsc{A,B}} = \sup _{t \in F} \frac{\textsc{A}(\mathbf{t})}{\textsc{B}(\mathbf{t})} \koz ,\label{eq-RAB}
\end{equation}
\begin{equation}
R_{\textsc{A},\infty} = \lim _{n \rightarrow \infty} R_{\textsc{A,B},n} \koz .\label{eq-RAinf}
\end{equation}

A becslõ algoritmusok esetén a (\ref{eq-RABn}), (\ref{eq-RAB}) és (\ref{eq-RAinf}) képletekben a számlálót és nevezõt  
felcseréljük és a (\ref{eq-RAinf}) képletben a lim sup helyett a lim inf határértéket használjuk. 

Ezek a mennyiségek fõleg akkor érdekesek, ha $\textsc{B} \in \mathcal{A}_\var{opt}.$ 
Ilyenkor az egyszerûség kedvéért a jelölésekbõl elhagyjuk a $\textsc{B}$-t, és az 
$\textsc{A}_{\var{köz}} \in \mathcal{A}_{\var{becs}},$ 
illetve az $\textsc{E} \in \mathcal{A}_{\var{becs}}$ algoritmusok hibafüggvényérõl, 
hibájáról és aszimptotikus hibájáról beszélünk. Más algoritmusok esetén célszerû a lim határérték helyett a 
lim sup határérték alkalmazása, hogy a határérték biztosan létezzen.
 
\section*{2. NF algoritmus}

Az NF algoritmusra vonatkozó elsõ jellemzés 1972-ben jelent meg, D. S. Johnson PhD disszertációjának kéziratában 
\cite{Johnson1972}. Ma inkább D. S. Johnson megvédett értekezésére \cite{Johnson1973} hivatkoznak.

\begin{tetel} \emph{(Johnson, 1972)} Ha $\mathbf{t} \in F_n,$ akkor\label{th:NFJohnson}
\begin{equation}
n = \textsc{OPT}(\mathbf{t}) \leq \textsc{NF}(\mathbf{t}) \leq 2\textsc{OPT}(\mathbf{t})-1=2n-1 \koz .\label{eq:NFkorlatok}
\end{equation}
Továbbá, ha $k \in \Z^+,$ akkor léteznek olyan $\mathbf{u}_k$ és $\mathbf{v}_k$ listák, melyekre
\begin{equation}
k = \textsc{OPT}(\mathbf{u}_k) = \textsc{NF}(\mathbf{u}_k)
\end{equation}
és 
\begin{equation}
k = \textsc{OPT}(\mathbf{v}_k)  \ \var{és} \   \textsc{NF}(\mathbf{v}_k) = 2\textsc{OPT}(v_k) - 2 \koz .
\end{equation}
\end{tetel}

\begin{biz} Johnson a felsõ korlátot úgy bizonyította, hogy feltette a korlát ellenkezõjét, miszerint van olyan 
$L = (t_1, t_2, \ldots,T_n)$ lista, amelyre OPT$(L) = n$ és FF$(L) \geq 2n.$ Mivel NF csak akkor nyit meg új ládát, 
ha a soron következõ tárgy nem fér be az utolsó megnyitott ládába, ezért az FF ütemezésében a szomszédos ládákban lévõ tárgyak 
súlyösszege nagyobb egynél, így a $2n$ ládában $n$-nél nagyobb lenne a súlyösszeg, és OPT nem tudná a listát 
$n$ ládába bepakolni.

A tétel második részét pedig olyan $u_k$ listával bizonyította, amely $k$ darab egyest tartalmazott, és olyan $v_k$ 
listával, amely $4k - 4$ elemet tartalmazott úgy, hogy a páratlan indexû elemek súlya 1/2 volt, míg a páros indexûeké 
$1/(2k - 2).$
\end{biz}

1984-ben a \cite{Ivanyi1984Comp}\nevindex{Iványi Antal} cikkben ennél pontosabb (éles) korlátot adtunk.

Legyen $\nu$ azon ládapakoló algoritmusok halmaza, amelyek ütemezésében a szomszédos ládákba kerülõ 
tárgyak súlyösszege mindig nagyobb egynél.

\begin{tetel} \emph{(Iványi, 1984)} Ha $\mathbf{t} \in F_n,$ akkor\label{th:NFIvanyi} minden $A \in \nu$ 
ládapakoló algoritmusra fennáll
\begin{equation}
n = \textsc{OPT}(\mathbf{t}) \leq \textsc{A}(\mathbf{t}) \leq 2\textsc{OPT}(\mathbf{t})-1 = 2n-1 \koz .\label{eq:NFpontoskorlatok}
\end{equation}
Továbbá, ha $k \in \Z,$ akkor létezik olyan $B \in \nu$ ládapakoló algoritmus és léteznek olyan $\mathbf{u}_k$ 
és $\mathbf{v}_k$ listák, melyekre
\begin{equation}
k = \textsc{OPT}(\mathbf{u}_k) = \textsc{B}(\mathbf{u}_k)
\end{equation}
és 
\begin{equation}
k = \textsc{OPT}(\mathbf{v}_k)  \ \var{és} \   \textsc{B}(\mathbf{v}_k) = 2k - 1 \koz .
\end{equation}
\end{tetel}

\begin{biz} Johnson bizonyításán csak annyit változtatunk, hogy a $v_k$ lista $4k - 2$ elemet tartalmaz úgy, hogy 
a páratlan indexû elemek súlya 1/2, míg a páros indexû elemek súlya $1/(4k - 2)$.
\end{biz}  

Ez a tétel magyarul is megtalálható a \cite{Ivanyi2004} könyv 500. oldalán, mint 11.9. tétel.

A NF ládapakoló algoritmus jellemzõ adatai ismertek.
\begin{tetel} Ha $\mathbf{t} \in F_n,$ akkor\label{th:NF}
\begin{equation}
n = \textsc{OPT}(\mathbf{t}) \leq \textsc{NF}(\mathbf{t}) \leq 2\textsc{OPT}(\mathbf{t})-1=2n-1 \koz .\label{eq:NFkorlatok}
\end{equation}
Továbbá, ha $k \in \Z,$ akkor léteznek olyan $\mathbf{u}_k$ és $\mathbf{v}_k$ listák, melyekre
\begin{equation}
k = \textsc{OPT}(\mathbf{u}_k) = \textsc{NF}(\mathbf{u}_k)
\end{equation}
és 
\begin{equation}
k = \textsc{OPT}(\mathbf{v}_k)  \ \var{és} \   \textsc{NF}(\mathbf{v}_k) = 2k - 1 \koz .
\end{equation}
\end{tetel}

Ebbõl az állításból adódik a NF fájlelhelyezõ algoritmus hibafüggvénye, abszolút hibája és aszimptotikus hibája.
\begin{kov} Ha $n \in \Z,$ akkor
\begin{equation}
R_{\textsc{NF},n} = 2 - \frac{1}{n} \koz ,
\end{equation}
továbbá
\begin{equation}
R_{\textsc{NF}} = R_{\textsc{NF},\infty} = 2 \koz .
\end{equation}
\end{kov}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{3. FF algoritmus} 
R. L. Graham,\nevindex{Graham, Ronald L.} 1972-ben \cite{Graham1972} 
1972-ben megmutatta, hogy az $L = ( 0.06^7,$ \linebreak 
\noindent $0.51^5,0.1^2,0.16^3,(0.34^2)^5,(0.51)^{10})$ listára  
FF$(L) = 17$, és ha a listát csökkenõ sorrendbe rendezzük, akkor az így kapott $L' = (0.51^{10},0.34^{10},$ 
$0.16^{10},0.10^{10})$ listára FF$L' = \textsc{OPT}(L')$ = 10. 

Graham ebben a cikkében megfogalmazta azt a sejtést, hogy ha OPT($L$) elég nagy, akkor $R_{\textsc{FF}}/\textsc{OPT}(L)$ < 1.7. 

A \cite{Ivanyi1984Comp,Ivanyi1984Kib} dolgozatban megmutattuk,\nevindex{Iványi Antal} hogy az FF relatív hibája tetszõlegesen 
nagy optimális ládaszám esetén is felveszi az 1,7 értéket.

\begin{tetel} \emph{Iványi, 1984}. Ha ...
\end{tetel}
 

A FF és BF ládapakoló algoritmus\angolnevindex{bin packing algorithm = ládapakoló algoritmus} 
legrosszabb esetére vonatkozik a következõ állítás \cite{Ivanyi1986} 

\begin{tetel} \emph{(Iványi, 1986)} Ha $\mathbf{t} \in F_n,$ akkor\label{th:Hetnegyed}
\begin{equation}
\rm{FF}(\mathbf{t}) < \frac{7}{4}.
\end{equation}
\end{tetel}

1994-ben D. Simchi-Levi \cite{SimchiLevi1994} egy valamivel gyengébb állításra publikált bonyolultabb bizonyítást 
(viszont az õ bizonyítása a BF algoritmusra is jó).)

\cite{GareyGU1973}.

\begin{tetel} \emph{(Garey, Graham, Ullman, 1973)} Ha $\mathbf{t} \in F_n,$ akkor\label{th:NF}
\begin{equation}
\textsc{OPT}(\mathbf{t}) \leq \textsc{FF}(\mathbf{t}), \ \textsc{BF}(\mathbf{t}) 
\leq 1.7\textsc{OPT}(\mathbf{t}) + 2 \koz .\label{eq:FFkorlatok}
\end{equation}
Továbbá, ha $k \in \Z,$ akkor léteznek olyan $\mathbf{u}_k$ és $\mathbf{v}_k$ listák, melyekre
\begin{equation}
k = \textsc{OPT}(\mathbf{u}_k) = \textsc{FF}(\mathbf{u}_k) = \textsc{BF}(\mathbf{u}_k) 
\end{equation}
valamint
\begin{equation}
k = \textsc{OPT}(\mathbf{v}_k)  \ \var{és} \   \textsc{FF}(\mathbf{v}_k) = 
\textsc{BF}(\mathbf{v}_k) = \lfloor 1.7k \rfloor \koz .
\end{equation}
\end{tetel}

A FF algoritmusra egy erõsebb felsõ korlát is érvényes.

\begin{tetel} Ha $\mathbf{t} \in F_n,$ akkor\label{th:FF1}
\begin{equation}
\textsc{OPT}(\mathbf{t}) \leq \textsc{FF}(\mathbf{t}) < 1.7\textsc{OPT}(\mathbf{t}) + 1 \koz .\label{eq:FFkorlatok}
\end{equation}
\end{tetel}

Ebbõl a két állításból adódik FF és BF aszimptotikus hibája, valamint hibafüggvényük jó becslése.

\begin{kov} Ha $n \in \Z,$ akkor
\begin{equation}
\frac{\lfloor 1.7n \rfloor}{n} \leq  R_{\textsc{FF},n} \leq \frac{\lceil 1.7n \rceil}{n} 
\label{memeq:FFegyhet}
\end{equation}
és
\begin{equation}
\frac{\lfloor 1.7n \rfloor}{n} \leq  R_{\textsc{BF},n} \leq \frac{\lfloor 1.7n + 2 \rfloor}{n} 
\label{memeq:BFegyhet}
\end{equation}

továbbá
\begin{equation}
R_{\textsc{FF},\infty} = R_{\textsc{BF},\infty} = 1.7 \koz .
\end{equation}
\end{kov} 

Ha $n$ osztható tízzel, akkor a (\ref{memeq:FFegyhet}) egyenlõtlenségben az alsó és felsõ határok megegyeznek, 
azaz ebben az esetben $1.7 = R_{FF,n}.$


Baker-Coffman \cite{BakerC1981}, Iványi \cite{Ivanyi1984Comp,Ivanyi1984Kib,Ivanyi1985} 

Korlát a legrosszabb esetre: \cite{SimchiLevi1994}.

Xia és Tan \cite{XiaT2010} 2010-ben a  következõ tételt bizonyították. 

\begin{tetel} Ha $\mathbf{t} \in F_n,$ akkor\label{th:FFXia}
\begin{equation}
\textsc{OPT}(\mathbf{t}) \leq \textsc{FF}(\mathbf{t}) \leq 1.7\textsc{OPT}(\mathbf{t}) + \frac{7}{10} \koz .\label{eq:FFkorlatok}
\end{equation}
\end{tetel}

\section*{4. BF algoritmus} 

Korlát a legrosszabb esetre: \cite{SimchiLevi1994}

\section*{5. NFD algoritmus}

\section*{6. FFD algoritmus}

Korlát a legrosszabb esetre: \cite{SimchiLevi1994}

Legjobb korlát a legrosszabb esetre: \cite{Yue1991}

\section*{7. BFD algoritmus} 

Korlát a legrosszabb esetre: \cite{SimchiLevi1994}
\angolnevindex{bound for the worst case of BFD = korlát a BFD legrosszabb esetére}
\index{legrosszabb eset korlát FFD-re = worst case bound for FFD}

\section*{8. Átlagos eset} 
\cite{CoffmanCG2000}

Iványi-Zolotarev: \cite{IvanyiZ1989}

Bramel et al.: \cite{BramelRS1997}

\section*{9. Érdekességek}

Párhuzamos algoritmusok:\angolnevindex{parallel algorithm = párhuzamos algoritmus}
\index{párhuzamos algoritmus = parallel algorithm} Anderson et al. \cite{AndersonMW1989} 

Duális probléma: \cite{CsirikFG1991} 

Online ládalefedõ: \cite{CsirikEII2010}

Korlátozott ládapakolás: \cite{EpsteinIL2010}

Lineáris programozás: \cite{MuiSB1998}
 
\textcolor{red}{\textbf{@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@}} \\

Az irodalomjegyzékben \textbf{letölthetõ} megjegyzéssel szereplõ mûvek letölthetõk a megadott honlapról, 
a \textbf{digitálisan} megjegyzéssel szereplõ mûvek letölthetõek a 
\href{http://compalg.inf.elte.hu/~tony/Kutatas/Pros-szam/}{http://compalg.inf.elte.hu/$\sim$tony/Kutatas/BinPacking/} 
honlapról, míg a \textbf{nyomtatva} megjegyzéssel szereplõ mûveket nyomtatott formában sikerült megszerezni. 

A szerzõ címe: Iványi Antal: \quad  \hrefun{tony@compalg.inf.elte.hu}{tony@compalg.inf.elte.hu}

\vspace{4mm}
Budapest, 2011. április 12.


\begin{thebibliography}{x}
\large
\vspace{-2mm}
\bibitem{AndersonMW1989} R. J. Anderson, E. W. Mayr, M. K. Warmuth. 
\hrefun{http://users.soe.ucsc.edu/~manfred/pubs/J13.pdf}{Parallel} approximation algorithms for bin packing. 
\textit{Inf. and Comp.}, \textbf{82} (1989) 262--277. \textbf{letölthetõ}

\bibitem{Aszalos1988} Aszalós Péter: Lower estimation of optimal number of bins. In: 
\textit{Fourth Conference of program Designers} (Budapest, 1988. június 1--3, szerkesztette Iványi Antal). 
ELTE, Budapest, 1988. 81--91. 

\bibitem{AszalosITZs1988} Aszalós Péter, Iványi Antal, Tóth Zoltán, Zsoldos Zsolt: 
Optimális processzorszám homogén hálózatokban. In: \textit{Programozási rendszerek'88} 
(Szekszárd, 1988. április 20--23), 77--78.\nevindex{Aszalós Péter}\nevindex{Tóth Zoltán}\nevindex{Zsoldos Zsolt}

\bibitem{Baker1985}  B. S. Baker. A new proof for the first-fit decreasing bin-packing algorithm. 
\textit{J. Algorithms}, \textbf{6} (1985) 49--70. \textbf{nyomtatva}

\bibitem{BakerC1981} B. S. Baker, E. G. \hrefun{http://www.el.columbia.edu/~egc/}{Coffman, Jr.} A tight asymptotic bound for
next-fit-decreasing bin-packing. \textit{SIAM J. Alg. Disc. Meth.}, \textbf{2} (1981) 147--152. 

\bibitem{BekesiG} J. Békési, G. Galambos, H. Kellerer. A 5/4 linear time bin packing algorithm. 
\textit{JCSS}, \textbf{60} (2000) 145--160.

\bibitem{BerghammerReuter2003} R. Berghammer, F. Reuter. A linear approximation algorithm for bin packing 
with absolute approximation factor 3/2. \textit{Science of Computer Programming}, \textbf{48} (2003) 67--80.

\bibitem{BerkeyW1994} J. O. Berkey, P. Y. Wang. A systolic-based parallel bin packing algorithm. 
\textit{IEEE Transactions on Parallel and Distributed Systems}, \textbf{5} (1994) 769--772. 

\bibitem{Bilchev1996} G. Bilchev. Evolutionary metaphors for the bin packing problem. In 
\textit{Evolutionary Programming V: Proceedings of the Fifth Annual Conference on Evolutionary Programming} 
1996, 333--341.

\bibitem{BlazewiczE1983} J. Blazewicz, K. Ecker. A linear time algorithm for restricted bin packing and scheduling problems. 
\textit{Oper. Res. Lett.}, \textbf{2} (1983) 80--83.

\bibitem{Bortfeld2000} A. Bortfeldt. A heuristic for multiple container loading problems.
\textit{OR Spektrum}, \textbf{22} (2000) 239--261.

\bibitem{Bourjolly} J. M. Bourjolly, V. Rebetez. An analysis of lower bound procedures for the bin packing 
problem. \textit{Computers and Operations Research}, \textbf{32} (3) (2005) 395--405.

\bibitem{BramelRS1997}  J. Bramel, W. T. Rhee, Rhee, D. Simchi-Levi:
\nevindex{Simchi-Levi, David}qnevindex{Bramel, Julien} 
Average-case analysis of the bin-packing problem with general cost structures. 
\textit{Naval Res. Logist.} \textbf{44} )7) (1997) 673--686. MR1471152 (99d:90091)

\bibitem{Brown1971} A. R. Brown. Optimum Packing and Depletion. American Elsevier, New York, 1971. \textbf{nyomtatva}

\bibitem{CoffmanCG2000} E. G. Coffman, Jr., C. Courcoubetis, M. R. Garey, 
D. S. \hrefun{http://www.research.att.com/~dsj}{Johnson}, P. W. Shor, R. R. Weber, M. Yannakakis. 
Bin packing with discrete item sizes, Part I: Perfect packing theorems and the
average case behavior of optimal packings. \textit{SIAM J. Disc. Math.}, \textbf{13} (2000) 384-402. 

\bibitem{CoffmanCG2002} E. G. \hrefun{http://www.el.columbia.edu/~egc/}{Coffman, Jr.}, Jr., C. Courcoubetis, M. R. Garey, 
D. S. \hrefun{http://www.research.att.com/~dsj}{Johnson}, P. W. Shor, 
R. R. Weber, M. Yannakakis. Perfect packing theorems and the average-case behavior of optimal and online bin
packing. \textit{SIAM Review}, \textbf{44} (2002) 95--108.

\bibitem{CoffmanGJ1984} E. G. \hrefun{http://www.el.columbia.edu/~egc/}{Coffman, Jr.}, Jr., M. R. Garey, 
D. S. \hrefun{http://www.research.att.com/~dsj}{Johnson}: Approximation algorithms for bin-packing: 
An updated survey. In G. Ausiello, M. Lucertini, P. Serafini, editors, \textit{Algorithm Design for Computer System Design}. 
Springer-Verlag, Wien, 1984. CISM Courses and Lectures Number 284, 49--106.

\bibitem{CoffmanG1978} E. G. \hrefun{http://www.el.columbia.edu/~egc/}{Coffman, Jr.}, M. R. 
\hrefun{http://cm.bell-labs.com/cm/ms/former/mrg/}{Garey}, D. S. \hrefun{http://www.research.att.com/~dsj}{Johnson}: 
An application of bin-packing to multiprocessor scheduling, \textit{SIAM Journal on Computing}, \textbf{7} 1978, 1--17.

\bibitem{CormenLRS2009} T. H. \hrefun{http://www.cs.dartmouth.edu/~thc/}{Cormen}, C. E. 
\hrefun{http://theory.lcs.mit.edu/~cel/}{Leiserson}, R. L. \hrefun{http://theory.lcs.mit.edu/~rivest/}{Rivest}, 
C. \hrefun{http://www.ieor.columbia.edu/~cliff/}{Stein}, \textit{Introduction to Algorithms}, 
The \hrefun{http://mitpress.mit.edu/main/home/default.asp?sid=C6EE87F7-92B7-4CC1-8035-E3AB8EAC0886}{MIT} 
Press/\hrefun{www.mcgraw-hill.com/}{McGraw}-Hill, 2009 (Harmadik kiadás). Magyarul: \textit{Algoritmusok.} 
\hrefun{http://www.muszakikiado.hu/}{Mûszaki Kiadó}, Budapest, 1999 (az 1991-es elsõ angol nylvû kiadás fordítása). 
\textbf{Informatikai Könyvtár}

\bibitem{Csirik1989} \hrefun{http://www.inf.u-szeged.hu/~csirik/}{Csirik} János:\nevindex{Csirik János} 
Ládapakolási algoritmusok. Szeged, 1989. 123 oldal. \textbf{nyomtatva}

\bibitem{CsirikEII2010} J. Csirik, L. Epstein, Cs. Imreh, A. Levin:
\nevindex{Csirik János}\nevindex{Epstein, Leah}\nevindex{Imreh Csanád}\nevindex{Levin, Asaf} 
On the sum minimization version of the online bin covering problem. 
\textit{Discrete Appl. Math.}    \textbf{158} (13) (2010) 1381--1393. MR2651988 \textbf{letölthetõ}

\bibitem{CsirikG1986} J. \hrefun{http://www.inf.u-szeged.hu/~csirik/}{Csirik}, G. 
\hrefun{http://www.jgypk.u-szeged.hu/~galambos/}{Galambos}. 
An $O(n)$ bin-packing algorithm for uniformly distributed data. 
\textit{Computing} \textbf{36} (1986) 313--319.

\bibitem{CsirikG1987} J. \hrefun{http://www.inf.u-szeged.hu/~csirik/}{Csirik}, 
G. \hrefun{http://www.jgypk.u-szeged.hu/~galambos/}{Galambos}. 
On the expected behaviour of the NF algorithm for a 
\hrefun{http://www.inf.u-szeged.hu/actacybernetica/prevvols/8_1/8_1_all.pdf}{dual bin} packing problem. 
\textit{Acta} \hrefun{http://www.inf.u-szeged.hu/actacybernetica/}{\textit{Cybernetica}} \textbf{8} (1987) 5--9.

\bibitem{CsirikFF1986} J. \hrefun{http://www.inf.u-szeged.hu/~csirik/}{Csirik}, J. B. G. Frenk, A. Frieze, G. 
\hrefun{http://www.jgypk.u-szeged.hu/~galambos/}{Galambos}, A. H. G. Rinnooy Kan. 
A probabilistic analysis of the next fit decreasing bin packing heuristic. 
\textit{Oper. Res. Lett.}, \textbf{5} (1986) 233--236. 

\bibitem{CsirikFG1991} J. \hrefun{http://www.inf.u-szeged.hu/~csirik/}{Csirik}, J. B. G. Frenk, G. 
\hrefun{http://www.jgypk.u-szeged.hu/~galambos/}{Galambos}, A. H. G. Rinnooy Kan.
Probabilistic analysis of algorithms for dual bin packing problems.
\textit{J. Algorithms}, \textbf{12} (1991) 189--203.

\bibitem{DosaI2011} \hrefun{http://math.uni-pannon.hu/index.php?option=com\_content\&amp;view=article\&amp;id
=51$\%$3Abemutatkozas\&amp;catid=45$\%$3Adr-dosa-gyoergy\&amp;Itemid=27\&amp;lang=hu}{Dósa} György, 
\hrefun{http://www.inf.u-szeged.hu/~cimreh/}{Imreh} Csanád: \textit{Online algoritmusok.} Elektronikus jegyzet. 
SZTE TTIK, Szeged, 2011 (kézirat). 

\bibitem{EpsteinIL2010} L. Epstein, Cs. \hrefun{http://www.inf.u-szeged.hu/~cimreh/}{Imreh}, 
A. Levin: Class constrained bin packing revisited. 
\nevindex{Epstein, leah}\nevindex{Imreh Csanád}\nevindex{Levin, Asaf}
\textit{Theoret. Comput. Sci.} \textbf{411} (34--36) (2010) 3073--3089. MR2676854 \textbf{letölthetõ}

\bibitem{Galambos} \hrefun{http://www.jgypk.u-szeged.hu/~galambos/}{Galambos} Gábor: 
Ládapakolási feladatok közelítõ algoritmusainak legrosszabb-eset vizsgálata. 
Kandidátusi értekezés tézisei. Szeged, 1991. \textbf{nyomtatva}

\bibitem{GareyGU1973} M. R. Garey, R. L. Graham, J. D. Ullman: An analysis of some 
\hrefun{http://www.math.ucsd.edu/~ronspubs/73_08_packing.pdf}{packing algorithms}. In: 
\textit{Combinatorial Algorithms}, ed. R. Rustin.\nevindex{Rustin, R.} Algorithmic Press, 1973, 39--48. 

\bibitem{GareyJ1979} M. Garey, D. S. \hrefun{http://www2.research.att.com/~dsj/}{Johnson}: 
\textit{Computers and Intractability.} 1979. \textbf{Informatikai Könyvtár}

\bibitem{Graham1972} R. L. Graham: Bounds on multiprocessing anomalies and related packing algorithms. In: 
\textit{Proceedings of the AFIPS Conference} \textbf{40}, AFIPS Press, Montvale, 1972, 205--217. 

\bibitem{Ivanyi1984Comp} A. \hrefun{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}: 
Performance bounds for simple \hrefun{http://ac.inf.elte.hu/Vol_005_1984/077.pdf}{bin packing} algorithms. 
\textit{Ann. Univ. Sci. Budapest. Sect.} \hrefun{http://ac.inf.elte.hu/}{\textit{Comput.}} \textbf{5} 
(1984) 77--82. MR0822601 (87h:68067) \textbf{letölthetõ}

\bibitem{Ivanyi1984Kib} A. \hrefun{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}: 
Estimation of the efficiency of bin-packing algorithms. (Russian) \textit{Problemy Kibernet.} \textbf{41} 
(1984) 253--256.  \textbf{digitálisan}

\bibitem{Ivanyi1985} A. \hrefun{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}: 
Tight worst-case bounds for bin packing algorithms. \textit{Theory of Algorithms}  
(Pécs, 1984), Colloq. Math. Soc. János Bolyai, 44, North-Holland, Amsterdam, 1985, 233--240. MR0872310 (88g:68051)
 \textbf{nyomtatva}
 
 \bibitem{Ivanyi1986} Iványi A.: \textit{Processzorütemezés}. Kézirat. ELTE, Numerikus és Gépi 
 Matematika Tanszék, Budapest, 1986. \textbf{nyomtatva} 
 
 \bibitem{IvanyiZ1989} A. \hrefun{http://compalg.inf.elte.hu/tanszek/tony/oktato.php?oktato=tony}{Iványi}, 
 V. M. Zolotarev:\nevindex{Zolotarev, V. M.} Probabilistic analysis of the optimal bin packing algorithm. In: ed. by A. Iványi, 
 \textit{Fifth Conference of Program Designers} (Budapest, 1989. augusztus 28--szeptember 1, szerkesztette Iványi Antal). 
 ELTE, Budapest, 1989, 183--198.  
  
 \bibitem{Ivanyi2004} Iványi A.: \textit{Informatikai algoritmusok}. ELTE Eötvös Kiadó, Budapest, 2004. 
 Elektronikusan: ELTE Informatikai Kar, 1974.
 
 \bibitem{Johnson1972} D. S. \hrefun{http://www2.research.att.com/~dsj/}{Johnson}: 
 \textit{Near-Optimal Bin Packing Algorithms}. MAC TR-109 számú technikai riport. Massachusetts Institute of Technology, 
 Cambridge, 1973. \textbf{nyomtatva}  
 
 \bibitem{Johnson1973} D. S. \hrefun{http://www2.research.att.com/~dsj/}{Johnson}: 
 \textit{Near-Optimal Bin Packing Algorithms}. PhD thesis,
Massachusetts Institute of Technology, Department of Mathematics, Cambridge, 1973.
 
\bibitem{LovászG1989} Lovász László, Gács Péter: \textit{Algoritmusok}. Tankönyvkiadó, Budapest, 1989. 
\textbf{ELTE Matematikai Könyvtárában}

\bibitem{MuiSB1998} L. Mui Ann Chan, D. Simchi-Levi, J. Bramel:  
Worst-case analyses, linear programming and the bin-packing problem. 
\textit{Math. Programming, Ser. A.} \textbf{83} (2) (1998) 213--227. MR1647849 (99h:90080)

\bibitem{SimchiLevi1994} D. \hrefun{http://web.mit.edu/dslevi/www/}{Simchi-Levi}: New worst-case results for the 
bin-packing problem. \textit{Naval Research Logistics} \textbf{41} (1994) 579--585. \textbf{digitálisan}

\bibitem{XiaT2010} B. Xia, Z. \hrefun{http://www.math.zju.edu.cn/webpagenew/teacherintroen.asp?userid=208}{Than}: 
Tighter bounds of the \hrefun{http://www.sciencedirect.com/science?\_ob=ArticleURL\&\_udi=B6TYW-50DXCVP-1\&\_user
=798018\&\_coverDate=08$\%$2F06$\%$2F2010\&\_rdoc=1\&\_fmt=high\&\_orig=gateway\&\_origin=gateway\&\_sort=d\&\_docanchor
=&view=c\&\_searchStrId=1705449523\&\_rerunOrigin=google\&\_acct=C000043568\&\_version=1\&\_urlVersion=0\&\_userid
=798018\&md5=eb51ecc60aa6f5b21ce9f17390edb09d&searchtype=a}{First Fit} algorithm for the bin-packing problem. 
\hrefun{http://www.sciencedirect.com/science/journal/0166218X}{\textit{Discrete}} \textit{Applied Mathematics} 
\textbf{158} (2010) 1668--1675. \textbf{letölthetõ} 

\bibitem{Yue1991} M. Yue: A simple proof of the inequaliy FFD$(L) \leq (11/9)$OPT$(L) + 1$ \textit{Acta Math. Applicatae Sinica} 
\textbf{7} (4) (1991) 322--331. \textbf{digitálisan}

\end{thebibliography}

\begin{printindex}
\end{printindex}

%\begin{printangolnevindex}
%\end{printangolnevindex}

\begin{printnevindex}
\end{printnevindex}



\end{document} 
