\documentclass[a4paper,UKenglish,cleveref, autoref, thm-restate]{lipics-v2021} %This is a template for producing LIPIcs articles. %See lipics-v2021-authors-guidelines.pdf for further information. %for A4 paper format use option "a4paper", for US-letter use option "letterpaper" %for british hyphenation rules use option "UKenglish", for american hyphenation rules use option "USenglish" %for section-numbered lemmas etc., use "numberwithinsect" %for enabling cleveref support, use "cleveref" %for enabling autoref support, use "autoref" %for anonymousing the authors (e.g. for double-blind review), add "anonymous" %for enabling thm-restate support, use "thm-restate" %for enabling a two-column layout for the author/affilation part (only applicable for > 6 authors), use "authorcolumns" %for producing a PDF according the PDF/A standard, add "pdfa" %\pdfoutput=1 %uncomment to ensure pdflatex processing (mandatatory e.g. to submit to arXiv) %\hideLIPIcs %uncomment to remove references to LIPIcs series (logo, DOI, ...), e.g. when preparing a pre-final version to be uploaded to arXiv or another public repository %\graphicspath{{./graphics/}}%helpful if your graphic files are in another directory \usepackage{algpseudocode} \usepackage{algorithm} \bibliographystyle{plainurl}% the mandatory bibstyle \title{Scheduling Borrels to maximize students attendance and social experience} %TODO Please add %\titlerunning{Dummy short title} %TODO optional, please use if title is longer than one line \author{Floris van der Hout}{Utrecht University , 7234080, Netherlands}{f.l.vanderhout@students.uu.nl}{}{} \author{Thomas van Maaren}{Utrecht University , 9825827, Netherlands}{t.s.vanmaaren@students.uu.nl}{}{} \author{ Rens Versnel}{Utrecht University , 2693852, Netherlands}{r.versnel@students.uu.nl}{}{} \author{Wessel van der Ven}{Utrecht University , 2828189, Netherlands}{w.vanderven@students.uu.nl}{}{} \author{Ids de Vlas}{Utrecht University , 6967396, Netherlands}{i.devlas@students.uu.nl}{}{} \authorrunning{Floris van der Hout, Thomas van Maaren, Rens Versnel, Wessel van der Ven and Ids de Vlas} %TODO mandatory. First: Use abbreviated first/middle names. Second (only in severe cases): Use first author plus 'et al.' \Copyright{Floris van der Hout, Thomas van Maaren, Rens Versnel, Wessel van der Ven and Ids de Vlas} %TODO mandatory, please use full first names. LIPIcs license is "CC-BY"; http://creativecommons.org/licenses/by/3.0/ \ccsdesc[100]{Online algorithms} %TODO mandatory: Please choose ACM 2012 classifications from https://dl.acm.org/ccs/ccs_flat.cfm \keywords{Borrels Scheduling, NP-completeness, competitive ratio's} %TODO mandatory; please add comma-separated list of keywords \category{} %optional, e.g. invited paper \relatedversion{} %optional, e.g. full version hosted on arXiv, HAL, or other respository/website %\relatedversiondetails[linktext={opt. text shown instead of the URL}, cite=DBLP:books/mk/GrayR93]{Classification (e.g. Full Version, Extended Version, Previous Version}{URL to related version} %linktext and cite are optional %\supplement{}%optional, e.g. related research data, source code, ... hosted on a repository like zenodo, figshare, GitHub, ... %\supplementdetails[linktext={opt. text shown instead of the URL}, cite=DBLP:books/mk/GrayR93, subcategory={Description, Subcategory}, swhid={Software Heritage Identifier}]{General Classification (e.g. Software, Dataset, Model, ...)}{URL to related version} %linktext, cite, and subcategory are optional %\funding{(Optional) general funding statement \dots}%optional, to capture a funding statement, which applies to all authors. Please enter author specific funding statements as fifth argument of the \author macro. \acknowledgements{}%optional %\nolinenumbers %uncomment to disable line numbering %Editor-only macros:: begin (do not touch as author)%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \EventEditors{John Q. Open and Joan R. Access} \EventNoEds{2} \EventLongTitle{42nd Conference on Very Important Topics (CVIT 2016)} \EventShortTitle{CVIT 2016} \EventAcronym{CVIT} \EventYear{2016} \EventDate{December 24--27, 2016} \EventLocation{Little Whinging, United Kingdom} \EventLogo{} \SeriesVolume{42} \ArticleNo{23} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \maketitle %TODO mandatory: add short abstract of the document \begin{abstract} Lorem ipsum dolor sit amet, consectetur adipiscing elit. Praesent convallis orci arcu, eu mollis dolor. Aliquam eleifend suscipit lacinia. Maecenas quam mi, porta ut lacinia sed, convallis ac dui. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Suspendisse potenti. \end{abstract} \section{Introduction} Image you are part of the student organization responsible for organizing borrels (social gatherings) for freshers. However, the freshman's have many obligations such as deadlines, group meetings, exams, ect. These obligations are flexible and can be rescheduled or delayed, but they still need to be completed eventually. Freshmen are eager to attend the borrels and will do so as long as they don't have any conflicting obligations. However, if their schedules clash with their obligations, they will prioritize those obligations over the borrel. Borrels are typically free for students to attend, but they do incur costs for the student organization, such as renting a venue, providing snacks, and other logistical expenses. It's common for borrels to offer the first drink for free, but any additional drinks must be purchased. The revenue generated from drink sales is used to help cover the borrels costs. If students enjoy themselves, they're more likely to buy drinks. One key factor that can enhance their experience is being able to attend the borrels with their friends.Therefore, it's in the student organization's interest to not only focus on attendance but also on maximizing the happiness of the freshers by scheduling borrels in a way that allows groups of friends to participate together. This can boost the overall success of the event both socially and financially. This paper will present two offline algorithms for scheduling borrels: one focused on optimizing student attendance, and the other designed to maximize the overall happiness of the freshers by considering factors like social connections and shared availability. Additionally, we will provide competitive ratios for online algorithms which focusing on maximizing the attendance of freshers at the borrels in multiple scenario's. \subsection{Literature review} We will visit several relevant problems in the literature, the first of which is the Social Event Scheduling Problem (SES) \cite{SocialEventPlanning}. In this context, the goal is to schedule a series of events or borrels while maximizing attendance or overall utility, considering that third-party events (in our problems context obligations) are already scheduled. Utility is defined as the expected attendance across all scheduled events. The difference between Borrels Scheduling and Social Event Scheduling lies in how competing events are treated. In the SES problem, competing events are those that have already been scheduled by third parties, resulting in fixed time slots. In contrast, our constraints, which can be viewed as competing events, can often be postponed within their designated time windows. Furthermore, in the SES problem, each event is assigned a probability indicating a user's likelihood of attending. If two events overlap, the probability distribution determines which event the user will choose. However, if there are 5 events, we cannot impose a requirement for users to attend exactly 4 out of 5 third-party events (the obligations) while leaving the remaining event slots for our events (borrels). In our case, the probability of attending an event changes based on which event the user chooses to attend. There is no trivial way to translate the Borrel Scheduling problem into the SES problem. \\ Another relevant problem is the Optimization Of Calendar Events. Especially when optimizing the scheduling of meetings within large organizations, where the objective is to maximize attendance while considering each participant's individual schedule/calendar. Since it is not always feasible for everyone to attend, the focus shifts to maximizing the number of attendees at the meeting which is similar to our problem \cite{distributedOptimizationOfCalendarEvents} \cite{EventSchedulingWithSoftConstraints}. However, solutions derived from this model are not directly applicable to our problem. In these frameworks, a participant calendars time slots are either marked available or unavailable which is different from our problem. In our case, there is a time window within which certain obligations must be fulfilled, but the exact timing has yet to be determined. This differs from the SES problem because the Optimization Of Calendar Events allows for soft constraints. Soft constraints refer to events in a user's schedule that can be rescheduled to another date for a small penalty cost. This approach resembles the Borrel Scheduling problem, where rescheduling is allowed if the event can be moved to another time within the available time slot. However, incorporating this flexibility significantly complicates the problem, making it more challenging to solve. \\ The final relevant problem is the Job Scheduling Problem with Deadlines \cite{JobShopSchedulingWithDeadlines}, which closely parallels the obligation and borrel planning aspects of our study. In this scenario, each obligation can be viewed as a job that needs to be scheduled on a specific machine, with both a deadline and a start time. Similarly, we have borrels that also need to be scheduled on these machines. In our problems context, we want to maximize for the scheduling borrels on different machines simultaneously, the same as maximizing attendance at the events. However, this is different from the objective in the job scheduling problem with deadlines which is to minimize the makespan while ensuring that all tasks remain feasible within their respective constraints. There is no trivial way to translate the Borrel Scheduling problem to the Job Scheduling problem with deadlines. \section{Preliminaries} TODO \section{Theoretical section WIP} \subsection{Proof of NP-completeness WIP}\label{subsec:npComplete} Todo \subsubsection{Formulation as a decision problem} In order to prove the NP-completeness of borrel planning it needs to be formulated as a decision problem. The aim of the original problem is to schedule each borrel $h$ starting at time slot $sh$ and lasting until time slot $s_h + b_h - 1 $, such that as many students attend the borrels as possible. In the decision version of this problem the aim is then to decide if there exists a assignment of borrels to timeslots such that there are at least $k$ attendances in total for some $k\in N$. % maybe move this formal definition below to somewhere far away (or just delete it) More formally, the aim is to decide if there exists a start time $s_h$ for each borrel $h$ such that there exists a set of feasible schedules $S_{i,j}$ for every pair of student $i$ and obligation $j$ where the number of attendances is at least some $k\in N$. The number of attendances can be defined by defining the set of possible attendances $A = \{(h, i) : \forall j, [s_h, s_h+b_h-1] \cap S_{i,j} = \emptyset \}$. The actual attendances of borrels is a subset $G\subseteq A$ where for any two attendances $(h_1,i_1), (h_2,i_2)\in G: i_1 \neq i_2 \vee [s_{h_1}, s_{h_1}+b_{h_1}-1] \cap [s_{h_2}, s_{h_2}+b_{h_2}-1] = \emptyset$. If there exists a set $G$ with a cardinality of at least some $k\in N$ for some borrel schedule, then the answer to the decision problem should be positive (``yes'' or ``accept''). % I think the formal formulation of the problem in the borrel.pdf is not complete or not correct, so I made my own shitty one. Maybe I should just stick to the less formal formulation because this is kind of a mess.. \subsubsection{Borrel planning is in NP} % show that for every instance there is a valid certificate resulting in a yes % show that you can correctly verify a certificate in polynomial time % show that the certificate is of polynomial length (compared to input size) % We can use a witness (h,i) if borrel h is NOT be attended by student i BECAUSE OF AN OBLIGATION. This way we have a witness (h,i) only if a students has an obligation at that time, so the witness is of size O(|I|^z ^* m^z) for some $z\in\N$. % I think we cannot use this because it its size not polynomial in the input size: the witness boolean $A_{hi}$ for all students i and borrels h, denoting if student i attends borrel h. % Another way to ``fix" this is by only considering the scenario where each person has at least one obligation, this way the input size is always at least O(n ^* m), meaning that the witness can be of size O(n^k ^* m^k) for some k, which is easy. \subsubsection{Reduction of set cover problem to borrel planning} \paragraph{Set cover} We consider the set cover decision problem with a universe $U=\{1,2,...,n\}$ containing all possible elements and the set $S$ containing $m$ subsets of the universe $U$ and a goal $k\in N$. %(We can require that the union of $S$ is equal to $U$, but this is not strictly necessary when considering the decision problem, I think). The aim in the set cover problem is to decide if there exists a subset $A$ of $S$ such that the union of $A$ is equal to $U$ and $|A| \leq k$. We will construct an instance of the borrel planning decision problem whose answer is the same as the answer to this set cover problem. % RETRY at readable formulation \paragraph{Construction of the reduction} Given a universe $U=\{1,2,...,n_1\}$ containing $n_1$ elements, a set $S$ containing $m_1$ subsets of $U$, and a goal $k_1\in N$. We create an instance of borrel planning with the following parameters: \begin{itemize} \item $t = |S| = m_1$ \; the number of timeslots is equal to the number of sets in $S$. \item $n_2 = |U| = n_1$ \; the number of students is equal to the size of the universe. \item $m_2 = k_1$ \; the number of borrels is equal to the set cover goal. \item $b_h = 1$ \; the length of each borrel $h$ is 1. \end{itemize} Furthermore, for all students $i$ and subsets $S_a \in S$ we create an obligation $j$ with $I_{i,j} = [a, a]$ and $p_{i,j} = 1$ for student $i$ if $i \not\in S_a$. Additionally we add an obligation $x$ to each student $i$ with $I_{i,x} = [1, t]$ and $p_{i,x} = |\{a : i\in S_a\}| - 1$. The borrel decision problem is to determine if there exists a schedule such that there are at least $t = n_1$ attendances. \paragraph{Proof of the reduction} We will show that this instance of the borrel planning problem is equivalent to the original set cover problem. Note, first, that each person can attend at most one borrel, since there is one timeslot for each set in $S$ and for every person $i$ there is an obligation of length 1 for every set in $S$ that contains $i$ and there is an obligation of length one less that the number of sets in $S$ that do not contain $i$. We can also see that a student $i$ can only attend a borrel at timeslot $j$ if $i$ is in the $j$'th set $S_j$. Then if the borrel planning problem decided that there is a feasible borrel schedule such that there are at least $|U|$ attendances with $k$ borrels, then these must be $|U|$ different students and therefore all elements in the universe. This borrel schedule must also use at most $k$ borrels corresponding to sets in $S$ to cover this universe. This proves that if the answer to this constructed borrel is yes, then the original set cover problem is also a yes-instance. Then, conversely, if the original set cover instance can be covered in at most $k$ sets, we can show that there exists some assignment of the borrels such that there are at least $|U|$ attendances. Given the $k$ sets that cover the universe, the $k$ borrels can be scheduled at the timeslots corresponding to those sets. Then each person can attend at least one borrel since the sets cover the entire universe, resulting in at least $|U|$ attendances. Since we have shown that a yes-instance of the borrel planning implies a yes-instance of the original set cover, and we have shown that a yes-instance of the original set cover implies a yes-instance of the borrel planning (and by contraposition a no-instance of borrel planning implies a no-instance of the set cover) it follows that the constructed borrel planning problem and the set cover problem are equivalent and thus set cover can be reduced to borrel planning. todo % prove that rewriting this problem can be done in polynomial time. \subsection{Problem competitive ratio} \subsubsection{Base problem} \subsubsection{k-foresight} \subsubsection{Non-overlapping obligations} \subsubsection{At most N different timeslots} \section{Offline Algorithms} In this section we will provide an algorithm for the base case as well as an algorithm for solving a variation of the base case. As we in section \ref{subsec:npComplete} the problem is NP-complete and therefore providing a polynomial algorithm for this problem would prove that NP=P. It is therefore not worthwhile to try and find a polynomial algorithm for this problem and therefore all the algorithms in this section will have exponential time. Even though this is quite bad, it is still possible to make an algorithm better than going through all possibilities. \subsubsection{Iterators} Our algorithms will be a brute force algorithm for a great part. This makes it necessary to iterate over all different possibilities. In some cases it is a good idea to choose a specific order of iteration. First of all we want to iterate over all possible borrel positions. If for example $m=2$, $b=\{3,1\}$ and $t=5$ we see that $s$ has 15 possible values: \[\{1,1\},\{2,1\},\{3,1\},\{1,2\},\{2,2\},\{3,2\},\{1,3\},\{2,3\},\{3,3\},\{1,4\},\{2,4\},\{3,4\},\{1,5\},\{2,5\},\{3,5\}.\] Note that $b_h+s_h-1\leq t$ always has to hold to ensure that the borrel is completely inside of the time interval. We can construct a general iterator, by increasing the $s_1$ until it hits the end of the time interval. After this it increases $s_2$ by 1 and it can start over again with $s_1$. It does this until $s_2$ hit the end of the time interval and it increments $s_3$ and so on. We can now define our borrel iterator (see algorithm \ref{borrelIt}). \begin{algorithm} \caption{Borrel iteration}\label{borrelIt} \begin{algorithmic}[1] \Procedure{borrelIt}{$t,m,b,s$} \For{$h\gets 1,n$} \State $s_h\gets s_h+1$ \If{$s_h+b_h-1\leq t$} \State \textbf{return} (False,$s$) \Else \State $s_h\gets 0$ \EndIf \EndFor \State \textbf{return} (True,$s$) \EndProcedure \end{algorithmic} \end{algorithm} For each student we need to make a decision on which borrels they should attend. Again we need to go through all possibilities to see which choice is the best. The easiest way of doing this is by using the binary counter method. Given a set $T$ we make a binary number $b$ that has the same amount of bits as $T$ has elements. A $1$ in the $i$-th digit indicates that the $i$-th element of $T$ is part of $S$ and a $0$ indicates that it is not part of $S$. By incrementing this number until all bits are set to 1 we get all possible subsets. For example if $T={12,2,4}$ we get the following iteration as seen in table \ref{binaryCount}. \begin{table} \begin{tabular}{|c|c c c c c c c c|} \hline b& 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 \\\hline S& $\emptyset$ & $\{12\}$ & $\{2\}$ & $\{2,12\}$ & \{4\} & $\{12,4\}$ & $\{2,4\}$ &\{12,2,4\}\\\hline \end{tabular} \caption{Subset iteration when using the binary count method.} \label{binaryCount} \end{table} The downside of using this method in our case is that we would be doing a lot of unnecessary work. Assume that it is possible for a student to go a set of borrels $B$. If $C\subset B$ we know that $C$ can not contain more borrels and therefore it will always be to go for $C$. It is therefore much better to use an iteration where bigger subsets come first (See table \ref{bigSetFirst}. The subset iterator will use a separate procedure called the fixed subset iterator which will iterate a subset of fixed size (see algorithm \ref{subsetIt}). The subset iterator will keep lowering the amount of sets until there are no elements left \begin{table} \begin{tabular}{|c|c c c c c c c c|} \hline S & $\{12,2,4\}$ & $\{12,2\}$ & $\{12,4\}$ & \{2,4\} & $\{12\}$ & $\{2\}$ &\{4\} & $\emptyset$\\\hline \end{tabular} \caption{Subset iteration when asserting that bigger subsets should come first.} \label{bigSetFirst} \end{table} \begin{algorithm} \caption{Fixed Subset iterator.}\label{subsetIt} \begin{algorithmic}[1] \Procedure{fSubIt}{sub,set} \State $i \gets$ \#sub \For {$j\gets 1,$\#sub} \While {$\text{set}_i\notin \text{sub}$} \State $i\gets i-1$ \EndWhile \If{$j\leq \#\text{set}-i$} \State $\text{sub} \gets \text{sub} \backslash \{\text{set}_i\} \cup \{\text{set}_i,\dots,\text{set}_{i+j}\}\backslash \{\text{set}_{i+j+1},\dots,\text{set}_{\#\text{set}}\}$ \State \textbf{return}(False,sub) \EndIf \State $i\gets i-1$ \EndFor \State \textbf{return}(True,\{$\text{set}_1,\dots,\text{set}_{\#\text{sub}}$) \EndProcedure \end{algorithmic} \end{algorithm} \begin{algorithm} \caption{Subset iterator.} \begin{algorithmic}[1] \Procedure{subIt}{sub,set} \If{\#sub=0} \State \textbf{return}(True,set) \EndIf \If(end) \State \textbf{return}(False,\{$\text{set}_1,\dots,\text{set}_{\#\text{sub}-1}$) \Else \State \textbf{return}(False,sub) \EndIf \EndProcedure \end{algorithmic} \end{algorithm} \subsubsection{Base case} First we provide an algorithm for the base case. For the paper outline we did not have time to give a full explanation of the algorithm. Algorithm 6 is the algorithm for the base case. \begin{algorithm} \caption{Checks if the current obligation times are valid.} \begin{algorithmic} \Procedure{obligationoverlap}{t,obl,k,r,p,d,U}: \State $V \gets \emptyset$ \For{$j\gets 1, k$} \If{$(U\cup V)\cap \text{obl}_j = \emptyset$} \State $V \gets V \cup \text{obl}_j$ \Else \State \textbf{return} True \EndIf \EndFor \State \textbf{return} False \EndProcedure \end{algorithmic} \end{algorithm} \begin{algorithm} \caption{Choose obligation times.} \begin{algorithmic}[1] \Procedure{chooseObl}{t,borSub,b,s,r,p,d,k} \State $U \gets \emptyset$ \For{$j\gets 1,k$} $\text{obl}_j \gets \{r_j,...,r_j+p_j-1\}$ \EndFor \For{$h\gets 1, \#b$} \State $A \gets {s_h,...,s_h+b_h-1}$ \If{$A \cap U \neq \emptyset$} \State \textbf{return}(False, \text{obl}) \EndIf \State $U \gets U \cup \{s_h,...,s_h+b_h-1\}$ \EndFor \State loop $\gets$ True \While{loop} \If{$\neg$\Call{obligationoverlap}{t,obl,k,r,p,d,U)}} \State \textbf{return}(True, obl) \EndIf \For{$i\gets 1,k$} \State (end,$\text{obl}_j$) $\gets$ \Call{fSubsIt}{$\text{obl}_j,\{r_j,...,d_j\}$} \State loop $\gets$ $\neg$end \If{end} \State $\text{obl}_j \gets \{r_j,...,r_j+p_j-1\}$ \Else \State \textbf{break} \EndIf \EndFor \EndWhile \EndProcedure \end{algorithmic} \end{algorithm} \begin{algorithm} \caption{Finds the optimum borrel times.} \begin{algorithmic} \Procedure{initialState}{$t,m,b,n,I,p$} \For{$h\gets 1, m$} \State $s_h \gets 0$ \EndFor \For{$i \gets 1, n$} \For{$j\gets 1, \ell_i$} \State $o_{i,j} \gets \{r_{i,j},...,r_{i,j}+p_{i,j}-1\}$ \EndFor \EndFor \State $v\gets 1$ \State \textbf{return}(s,o,v) \EndProcedure \\ \Procedure{borrel}{$t,m,b,n,I,p,\ell$} \State $(s,o,v) \gets \text{initialState}(t,m,b,n,I,p,\ell)$ \State $(s^*,o^*,v^*) \gets \text{initialState}(t,m,b,n,I,p,\ell)$ \While{True} \State $v\gets 0$ \For{$i\gets 1, n$} \State borSub $\gets \{1,...,m\}$ \State $vS \gets 0$ \While{True} \State (canAttend,obl) $\gets$ \Call{chooseObl}{$t,\text{borSub},b,s,r_i,d_i,p_i,\ell_i$} \If{canAttend}: \State $vS \gets \#\text{borSub}$ \State $o^*_i <- \text{obl}$ \State \textbf{break} \EndIf \State (end,borSub) $\gets$ \Call{subsIt}{borSub,{1,...,m}} \If{subsIt(borSub)} \State \textbf{break} \EndIf \EndWhile \State $v \gets v+vS$ \EndFor \If{$v^*v^*$} \State $o^* \gets o$ \State $v^* \gets v$ \EndIf \EndIf \For{$i\gets 1,n$} \State (end,$\text{borSub}_i$) $\gets$ \Call{subsIt}{$\text{borSub}_i,\{1,...,m\}$} \If{end} \State $\text{borSub}_i \gets \{1,...,m\}$ \EndIf \EndFor \EndWhile \If{$v^{**}