\relax 
\providecommand\babel@aux[2]{}
\@nameuse{bbl@beforestart}
\providecommand\hyper@newdestlabel[2]{}
\providecommand\HyField@AuxAddToFields[1]{}
\providecommand\HyField@AuxAddToCoFields[2]{}
\bibstyle{plainurl}
\gdef\@authornum{1}
\gdef\@authornum{2}
\gdef\@authornum{3}
\gdef\@authornum{4}
\gdef\@authornum{5}
\babel@aux{UKenglish}{}
\gdef\@pageNumberEndAbstract{1}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{1}{section.1}\protected@file@percent }
\citation{SocialEventPlanning}
\citation{distributedOptimizationOfCalendarEvents}
\citation{EventSchedulingWithSoftConstraints}
\citation{JobShopSchedulingWithDeadlines}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.1}Literature review}{2}{subsection.1.1}\protected@file@percent }
\@writefile{toc}{\contentsline {section}{\numberline {2}Preliminaries}{3}{section.2}\protected@file@percent }
\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Formal problem definition}{3}{subsection.2.1}\protected@file@percent }
\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.1.1}Offline setting}{3}{subsubsection.2.1.1}\protected@file@percent }
\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.1.2}Online setting}{3}{subsubsection.2.1.2}\protected@file@percent }
\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.1.3}Decision problem}{3}{subsubsection.2.1.3}\protected@file@percent }
\newlabel{decision-problem}{{2.1.3}{3}{Decision problem}{subsubsection.2.1.3}{}}
\newlabel{decision-problem@cref}{{[subsubsection][3][2,1]2.1.3}{[1][3][]3}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.1.4}Borrel scheduling with at most 2 concurrent obligations (BS-2CO)}{3}{subsubsection.2.1.4}\protected@file@percent }
\newlabel{BS-2CO}{{2.1.4}{3}{Borrel scheduling with at most 2 concurrent obligations (BS-2CO)}{subsubsection.2.1.4}{}}
\newlabel{BS-2CO@cref}{{[subsubsection][4][2,1]2.1.4}{[1][3][]3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Set cover}{4}{subsection.2.2}\protected@file@percent }
\@writefile{toc}{\contentsline {section}{\numberline {3}Problem competitive ratio}{4}{section.3}\protected@file@percent }
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1}Base problem}{4}{subsection.3.1}\protected@file@percent }
\newlabel{base}{{3.1}{4}{Base problem}{subsection.3.1}{}}
\newlabel{base@cref}{{[subsection][1][3]3.1}{[1][4][]4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2}Multiple borrels}{4}{subsection.3.2}\protected@file@percent }
\newlabel{multiple}{{3.2}{4}{Multiple borrels}{subsection.3.2}{}}
\newlabel{multiple@cref}{{[subsection][2][3]3.2}{[1][4][]4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.3}Lookahead}{5}{subsection.3.3}\protected@file@percent }
\citation{Karp1972}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.4}Combination of lookahead and multiple borrels}{6}{subsection.3.4}\protected@file@percent }
\@writefile{toc}{\contentsline {section}{\numberline {4}BS-2CO is NP-complete}{6}{section.4}\protected@file@percent }
\newlabel{subsec:npHard}{{4}{6}{BS-2CO is NP-complete}{section.4}{}}
\newlabel{subsec:npHard@cref}{{[section][4][]4}{[1][6][]6}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1}BS-2CO is in NP}{6}{subsection.4.1}\protected@file@percent }
\@writefile{toc}{\contentsline {subparagraph}{Definition of certificate polynomial in size}{6}{section*.1}\protected@file@percent }
\@writefile{toc}{\contentsline {subparagraph}{Existance of certificate for yes-instances}{7}{section*.2}\protected@file@percent }
\@writefile{toc}{\contentsline {subparagraph}{Verification}{7}{section*.3}\protected@file@percent }
\@writefile{toc}{\contentsline {subparagraph}{Sorting the input and checking borrel overlap}{7}{section*.4}\protected@file@percent }
\@writefile{toc}{\contentsline {subparagraph}{Shift and shorten obligations}{7}{section*.5}\protected@file@percent }
\providecommand*\caption@xref[2]{\@setref\relax\@undefined{#1}}
\newlabel{fig:obligation-shift}{{1}{7}{The shift of obligations}{figure.caption.6}{}}
\newlabel{fig:obligation-shift@cref}{{[figure][1][]1}{[1][7][]7}}
\@writefile{toc}{\contentsline {subparagraph}{Fill in obligations in earliest deadline order}{8}{section*.7}\protected@file@percent }
\@writefile{toc}{\contentsline {subparagraph}{Proof of optimality}{8}{section*.8}\protected@file@percent }
\@writefile{toc}{\contentsline {subsection}{\numberline {4.2}Reduction of set cover problem to BS-2CO}{8}{subsection.4.2}\protected@file@percent }
\@writefile{toc}{\contentsline {subparagraph}{Construction of the reduction}{9}{section*.9}\protected@file@percent }
\newlabel{fig:set-cover-reduction}{{2}{9}{The reduction from set cover to borrel planning}{figure.caption.10}{}}
\newlabel{fig:set-cover-reduction@cref}{{[figure][2][]2}{[1][9][]9}}
\@writefile{toc}{\contentsline {subparagraph}{Proof of the reduction}{9}{section*.11}\protected@file@percent }
\@writefile{toc}{\contentsline {section}{\numberline {5}Offline Algorithms}{10}{section.5}\protected@file@percent }
\@writefile{toc}{\contentsline {subsection}{\numberline {5.1}Iterators}{10}{subsection.5.1}\protected@file@percent }
\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.1.1}Borrel positions}{10}{subsubsection.5.1.1}\protected@file@percent }
\newlabel{BorPos}{{5.1.1}{10}{Borrel positions}{subsubsection.5.1.1}{}}
\newlabel{BorPos@cref}{{[subsubsection][1][5,1]5.1.1}{[1][10][]10}}
\@writefile{loe}{\contentsline {theorem}{\ifthmt@listswap Theorem~1\else \numberline {1}Theorem\fi }{11}{theorem.1}\protected@file@percent }
\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.1.2}Subsets}{11}{subsubsection.5.1.2}\protected@file@percent }
\newlabel{BorSub}{{5.1.2}{11}{Subsets}{subsubsection.5.1.2}{}}
\newlabel{BorSub@cref}{{[subsubsection][2][5,1]5.1.2}{[1][11][]11}}
\newlabel{binaryCount}{{1}{11}{Subset iteration when using the binary counter method}{table.caption.12}{}}
\newlabel{binaryCount@cref}{{[table][1][]1}{[1][11][]11}}
\newlabel{bigSetFirst}{{2}{12}{Subset iteration when asserting that bigger subsets should come first}{table.caption.13}{}}
\newlabel{bigSetFirst@cref}{{[table][2][]2}{[1][12][]12}}
\@writefile{loe}{\contentsline {lemma}{\ifthmt@listswap Lemma~2\else \numberline {2}Lemma\fi }{12}{lemma.2}\protected@file@percent }
\newlabel{iterateSets}{{2}{12}{}{lemma.2}{}}
\newlabel{iterateSets@cref}{{[lemma][2][]2}{[1][12][]12}}
\@writefile{loe}{\contentsline {lemma}{\ifthmt@listswap Lemma~3\else \numberline {3}Lemma\fi }{12}{lemma.3}\protected@file@percent }
\newlabel{iterateNumbers}{{3}{12}{}{lemma.3}{}}
\newlabel{iterateNumbers@cref}{{[lemma][3][]3}{[1][12][]12}}
\@writefile{loe}{\contentsline {theorem}{\ifthmt@listswap Theorem~4\else \numberline {4}Theorem\fi }{13}{theorem.4}\protected@file@percent }
\newlabel{iterateNumbers}{{5.1.2}{13}{Subsets}{theorem.4}{}}
\newlabel{iterateNumbers@cref}{{[subsubsection][2][5,1]5.1.2}{[1][13][]13}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.2}Base case}{13}{subsection.5.2}\protected@file@percent }
\@writefile{toc}{\contentsline {subsection}{\numberline {5.3}Social Matrix algorithm}{13}{subsection.5.3}\protected@file@percent }
\@writefile{toc}{\contentsline {section}{\numberline {6}Complexity}{14}{section.6}\protected@file@percent }
\@writefile{toc}{\contentsline {section}{\numberline {7}Experiments}{14}{section.7}\protected@file@percent }
\newlabel{Benchmarks}{{3}{14}{Runtime of the algorithm on all the instances. \textbf {CPU:} Intel i5-7200U (4) 3.100GHz, \textbf {OS:} Manjaro Linux x86\_64}{table.caption.14}{}}
\newlabel{Benchmarks@cref}{{[table][3][]3}{[1][14][]14}}
\@writefile{toc}{\contentsline {section}{\numberline {8}Conclusion}{15}{section.8}\protected@file@percent }
\@writefile{toc}{\contentsline {section}{\numberline {9}Appendix}{15}{section.9}\protected@file@percent }
\newlabel{borrelIt}{{1}{15}{Borrel iteration}{algorithm.1}{}}
\newlabel{borrelIt@cref}{{[algorithm][1][]1}{[1][15][]15}}
\newlabel{subsetIt}{{2}{15}{Fixed Subset iterator}{algorithm.2}{}}
\newlabel{subsetIt@cref}{{[algorithm][2][]2}{[1][15][]15}}
\bibdata{lipics-v2021jf}
\newlabel{notFixedSub}{{3}{16}{Subset iterator}{algorithm.3}{}}
\newlabel{notFixedSub@cref}{{[algorithm][3][]3}{[1][15][]16}}
\newlabel{BaseAlg}{{6}{18}{Finds the optimum borrel times}{algorithm.6}{}}
\newlabel{BaseAlg@cref}{{[algorithm][6][]6}{[1][16][]18}}
\newlabel{SocialAlg}{{8}{20}{Borrel with social matrix}{algorithm.8}{}}
\newlabel{SocialAlg@cref}{{[algorithm][8][]8}{[1][16][]20}}
\newlabel{TotPages}{{20}{20}{}{page.20}{}}
\gdef \@abspage@last{20}