Public Event Scheduling with Busy Agents

1 Introduction

Artificial intelligence algorithms are widely used in many societal settings, such as scheduling public activities and assisting with personal work schedules, in which finding a suitable schedule shall lead to good social welfare. To motivate our study, consider the pubic event scheduling process at a university. Suppose the student/staff development office wants to hold some public activities for students/staffs, e.g., networking events, new student/staff orientation, etc. These events have fixed duration, while the target students/staffs are busy, and they have their own tasks that must be done but with some degree of time flexibility, e.g., homework, lectures, research meetings, submission deadlines, etc. For example, there are two events, both lasting for two hours. Some of the students/staffs must spend two hours on their own tasks between 10:00 and 13:00, and other students/staffs must spend three hours between 14:00 and 18:00. The whole schedulable time span for events is 10:00-18:00. These events are important to students/staffs, and it is crucial to schedule these public events at suitable times so that the target students/staffs can participate as long as possible. The agreement of a student/staff to an event schedule is considered as the total time that she can attend the events. Hence, the organizer's task is to make the event schedule admit a maximum agreement. This shall lead to good social welfare, motivating our work.

The above public event scheduling problem aims to find feasible job and event schedules such that social welfare is maximized. Hence, it falls under the umbrella of both job scheduling and computational social choices. The intersection of these two fields has been extensively studied in various literature, such as selfish load balancing [Bil`o et al., 2020; Vinci et al., 2022], the Santa clause problem [Bamas et al., 2021; Bansal and Sviridenko, 2006; Springer et al., 2022], fair division with scheduling constraints [Li et al., 2021; Li et al., 2023; Zhou et al., 2023], etc [Elkind et al., 2022; Pascual et al., 2018; Endriss et al., 2022].

From the scheduling perspective, our problem shares some similarities with a set of scheduling problems. Intuitively, the optimal solution to our problem tends to gather the schedule of agents' jobs, which leads to a long consecutive idle time during which events can be scheduled. The optimal solution for a batch of scheduling problems also shares a similar behavior, such as gap scheduling [Antoniadis et al., 2020; Baptiste, 2006], active time slots minimization [Chang et al., 2014; Chau and Li, 2020; Kumar and Khuller, 2018], calibration scheduling [Bender et al., 2013; Chau et al., 2020; Chen et al., 2019], etc. However, our work investigates a distinct objective compared to these classical scheduling problems and thus leads to completely different techniques.

From the perspective of computational social choice, our problem shares some similarities with the recently proposed cake-sharing model [Bei et al., 2022]. We can consider the whole timeline as a cake whose range is from [0, 1], and then normalize all agents' tasks to ensure that jobs' release time and deadline are in [0, 1]. Furthermore, we assume the jobs' processing time is equal to the length of its interval, where we call a job rigid (otherwise, it is called flexible). An agent's task can be interpreted as a preference for the cake, i.e., if an agent has a task [a, b], then the agent does not prefer this part of the cake. Our goal is to pick m pieces of cakes such that the total agreement of the picked cakes is maximized. The above scenario also motivates our work, and it matches the setting of cake-sharing [Bei et al., 2022] in the general sense. Compared to cake sharing, the first main difference is that we allow jobs to be flexible. The second main difference is that we focus on the social welfare maximization problem while [Bei et al., 2022] aims to design truthful mechanisms.

1.1 Our Contributions

We consider the problem of Public Event Scheduling with Busy Agents (PESBA). We distinguish several cases according to the event set or the length of the whole timeline. For each case, we either give an approximate (or exact) algorithm running in polynomial time or show the problem is NP-hard. We remark that, due to space limits, all formal proofs are omitted and can be found in full version [Li et al., 2024].

Main Result 1 (Theorem 1). When the whole timeline is polynomially bounded, a natural greedy algorithm running in polynomial time achieves 1 2 -approximation for PESBA. Moreover, PESBA admits a (1 - 1e )-approximate algorithm running in polynomial time.

For a better understanding of our method, let us first focus on the case where the whole timeline is polynomially bounded (Section 3). Our main algorithm is an intuitive greedy algorithm which can be viewed as a simple voting process. Namely, in each round of our algorithm, for each unscheduled event, we ask agents to vote on the position for this event, and each agent votes for those time slots that maximize her agreement. The algorithm then picks one position that receives the most votes for this event. Finally, the algorithm schedules the event that maximizes the total agreement among all unscheduled events in this round. By proving (i) a new result for a variant of the submodular maximization (ii) the agreement function is submodular, we show that the greedy algorithm is 12 -approximate. This intuitive algorithm enables us to extend it to arbitrary timeline cases. In fact, we show a stronger result that the agreement function is a rank function of some matroid, which is also crucial for the arbitrary timeline case. By using the more involved algorithms for submodular optimization with matroid constraints, our method also implies a better (1 - 1e )-approximate algorithm, but it is hard to extend to arbitrary timeline cases.

Main Result 2 (Theorem 2). When the whole timeline is arbitrary, we present an algorithmic framework that extends a 1α -approximate algorithm for PESBA with one event to the multiple events case achieving 1 α+1 -approximation. We design an optimal algorithm for the one-event instance and hence obtain a 1 2 -approximate algorithm for the arbitrary timeline case.

Our second result focuses on the general PESBA instance (Section 4). We propose an algorithmic framework for the general case. Given any 1α -approximate algorithm for the one-event instance, our framework extends the algorithm to multiple events case in polynomial time that achieves 1 α+1 - approximation. Our algorithmic framework is rooted in the greedy algorithm for the polynomially bounded timeline case. In each iteration of the greedy algorithm, it enumerates each time slot for searching the best position of each unscheduled event. This only works for the previous case since the whole timeline is polynomially bounded. We design a new oracle based on the given one-event approximation algorithm that is able to return a "good" position for each unscheduled event without enumerating the whole timeline. How good the position is depends on the approximation ratio of the given one-event algorithm. By using the optimal algorithm for the one-event instance proposed in full version [Li et al., 2024], we directly obtain a 12 -approximate algorithm for general PESBA instances, which matches the approximation ratio for restricted timeline case.

Main Result 3. The problem PESBA is NP-hard even in the case where (i) there is only one agent; (ii) this agent has only two rigid jobs. Moreover, the problem PESBA is in P when only one event is required to be scheduled.

Our last result focuses on the computation complexity of the problem. We first show that PESBA is NP-hard even if there is only one agent and the agent has only two rigid jobs. The hardness result is built on the classical partition problem. Then we show PESBA is in P when there is only one event that needs to be scheduled. This result shall be used to get an approximation for general PESBA instances. Our algorithm for one-event instance is involved, and its basic idea is to draw the plot for the agreement function when the event moves over the timeline. To this end, we prove that the agreement function is piecewise linear and has a polynomial number of turning points. These two parts can be found in the full version [Li et al., 2024].

1.2 Other RelatedWorks

Fair Allocation with Public Goods. Our problem shares some similarities with fair allocation of public goods. [Conitzer et al., 2017] first uses "public" to distinguish the previous "private" goods, and subsequently, there is a batch of follow-up works [Fain et al., 2018; Fluschnik et al., 2019; Garg et al., 2021]. In the public goods setting, all agents obtain utilities when some goods are selected, which is similar to the agreement in our problem. However, the techniques are different since we consider a different objective.

Other Related Scheduling Problems. When the preemption is not allowed, it is NP-complete to determine whether the given job set admits a feasible schedule [Garey and Johnson, 1979]. When all jobs are rigid or unit, the problem is equivalent to determining the size of the maximum independent set on interval graphs or a maximum matching. Hence it is in P [Schrijver, 1999]. When preemption is allowed, a simple greedy algorithm (earliest deadline first) can be used to decide instances' feasibility [Lenstra and Shmoys, 2020].

2 Preliminaries

We consider the problem of Public Event Scheduling with Busy Agents (PESBA). An instance of PESBA consists of an agent set A := {1, . . . , n} and a public event set E := { e1, . . . , em }. We consider discrete time, and for t ∈ N≥1, let [t, t+1) denote the t-th time slot. T is a time slot set consisting of all time slots where events and jobs can be scheduled. Each agent i has a set of jobs denoted by Ji. Each job j in Ji has a release time rj ∈ N≥1, a deadline dj ∈ N≥1, and a processing time pj ∈ N≥1 such that pj ≤ dj -rj +1. A job j is called a rigid job if pj = dj -rj +1; it is called a unit job if pj = 1. For each job j, the interval [rj, dj] is called a job interval, which can also be viewed as a set of consecutive time slots, i.e., { rj, rj +1, . . . , dj }. The event set E consists of m public events, and each event e has a length l(e) ∈ N≥1. When an event e is scheduled at the t-th time slot, this event occupies { t, t +1, . . . , t + l(e) -1} time slots to be held. We use a tuple (e, t) to denote that event e is scheduled at the t-th time slot. Let L be a set of all possible tuples, i.e., L := { (e, t) }e∈E,t∈T . Let L(e) be the set of all possible schedules of event e, i.e., L(e) := { (e′ , t) ∈ L | e′ = e }.

A solution consists of both the event schedule and the job schedule for each agent. The event schedule S is considered as a subset of L such that every event appears in exactly one tuple in S. This ensures that (i) every event e ∈ E is scheduled at some time slot; (ii) no event is scheduled more than two time slots. An event schedule S is said to be a partial event schedule if every event appears in at most one tuple; otherwise, it is called a complete event schedule. The job schedule consists of n subschedules, each of which corresponds to a job schedule for each agent. We consider the preemptive schedule, and the job schedule for each Ji, i ∈ A is required to be feasible, i.e., (i) each job j in Ji is assigned pj time slots in its job interval; (ii) for each t ∈ T, at most one job from Ji is processed at t. It is ensured that for each i ∈ A, the input job set Ji is feasible.

Each event is considered to be a good activity, and agents are willing to attend the events. A time slot t is said to be an agreement time slot for agent i if (i) t is occupied by some scheduled event; (ii) no job from Ji is scheduled at t. Given any event schedule and a job schedule for Ji, agent i's agreement is defined as the total number of agreement time slots. We allow event schedules to overlap since we can always eliminate the overlap by adjusting events' schedules without decreasing the total agreement (see Observation 1 in full version [Li et al., 2024]). Our goal is to find a job schedule for each Ji as well as a complete event schedule such that the total agents' agreement is maximized.

We use function agri : 2L → N≥0 to represent the maximum agreement that is produced by an event schedule S for agent i. Given any partial event schedule S and an agent i, in Section 3.2, we show that the value of agri(S) can be computed in polynomial time. Such an algorithm is used to compute the optimal job schedule, and this allows us to focus only on finding an event schedule. Based on the agreement function, our objective is equivalent to finding a complete event schedule S such that ∑i∈A agri(S) is maximized. An example can be found in Figure 1. In the remainder of this paper, we refer to S as a partial solution if S is a partial event schedule; otherwise, it is a complete solution.

3 Algorithms for Polynomial T

In this section, for a better understanding of our method, we focus on the case where the whole timeline is polynomially bounded; the assumption shall be removed in Section 4. We show that a natural greedy algorithm achieves

12 -approximation. In Section 4, we shall extend the 1 2 - approximation algorithm to the arbitrary |T| case with the approximation ratio being preserved. Our method also implies a slightly stronger algorithm that achieves (1 - 1e )- approximation in the polynomial bounded |T| case. Such a stronger result uses the submodular maximization subject to a matroid constraint [C˘alinescu et al., 2011] as a black box, and thus, it is hard to be extended to the arbitrary |T| case. Thus, we focus on the greedy algorithm, and we state how to get a (1 - 1e )-approximation in the proof of Theorem 1.

Theorem 1. Given any instance of PESBA with polynomially bounded |T|, there exists a greedy algorithm running in polynomial time that achieves 12 -approximation. The approximation ratio can be further improved to (1 - 1e ).

Algorithmic Framework. For each event e ∈ E and a time slot t ∈ T , the tuple (e, t) represents that the event e is scheduled at the t-th time slot. Since |T| is assumed to be polynomially bounded, we can find the optimal position for event e by enumerating all possible positions. Our algorithm runs in rounds and schedules exactly one event in each round until all events are assigned to a starting position. In each round, the algorithm checks the unscheduled events one by one. For each unscheduled event e′ , every agent assigns some "votes" to every possible position of e′ . Then, our algorithm chooses the schedule (e′ , t′ ) that receives the most votes (break ties arbitrarily), which gives a scheduled position t′ for event e′ . For each unscheduled event, we have a position in this round, and then, the algorithm just picks an event and its position (e∗ , t∗ ) with the maximum votes among all unscheduled events. Intuitively, the votes of some schedule (e, t) stands for the agent's preference for this schedule. Our algorithm shall select the schedule that is liked by the most agents and schedule the corresponding event at the corresponding time slot.

The first step of the algorithm is to set up an appropriate preference rule such that each agent assigns suitable votes to each schedule. Our idea is intuitive, i.e., agent i's preference for some schedule (e, t) is just the maximum incremental agreement that agent i can gain by scheduling e at t, i.e., agri(S ∪{ (e, t) })-agri(S) where S is the current solution.

3.1 The Complete Algorithm

This section presents the formal description of the algorithm. Given the partial solution S, we define F to be the total agreement produced by S for notation convenience, i.e., F(S) := ∑i∈A agri(S). For an unscheduled event e and any schedule (e, t), the total preference for the schedule (e, t) is F(S ∪ { (e, t) }) - F(S). Following the basic idea stated above, the algorithm picks a schedule with the maximum total preference in each round until all events are scheduled.

Algorithm 1 The Complete Algorithm for PESBA

Input: A PESBA instance with polynomially bounded |T |. Output: A schedule S of all events in E.

• 1: S ← ∅. 2: while there exists an unscheduled event do 3: H← ∅. 4: for each unscheduled event e′ do 5: t′ ← arg maxt∈T F (S ∪ { (e′ , t) }) - F (S). 6: H ← H ∪ { (e′ , t′ ) }. 7: end for 8: (e∗ , t∗ ) ← arg max(e,t)∈H F (S ∪ { (e, t) }) - F (S). 9: S ←S ∪ { (e∗ , t∗ ) }. 10: end while 11: return S.

The analysis of Algorithm 1 is built on a variant of a classical submodular maximization problem, i.e., the selected elements are additionally required to satisfy the group constraints, and an imperfect oracle exists. The formal definition is shown in Definition 1.

Definition 1 (Submodular Maximization with Group Constraints and Imperfect Oracle (SMGC)). Given some parameter n ∈ N≥1 and there is a ground element set U with |U| = 2poly(n) . There is a monotone and submodular function f : 2U → R≥0 defined over U. The ground element U is partitioned into ℓ groups: G1, . . . ,Gℓ with ℓ = poly(n). There is a polynomial α-approximate oracle g(·, ·) that takes two parameters as the input: a subset S ⊆ U and a group Gi, and it returns an element e∗ ∈ Gi in poly(n) time such that f(S∪{ e∗ })-f(S) ≥ 1α maxe∈Gi f(S∪{ e })-f(S), where α ≥ 1 is some given parameter. The goal is to pick a subset S of the ground element set such that f(S) is maximized, where S is required to satisfy two conditions: (i) |S| ≤ k (ℓ is guaranteed to be larger than k); (ii) S contains at most one element from Gi for all i ∈ [ℓ]. The running time of the algorithm is required to be poly(n).

SMGC v.s. PESBA. To see the connection, consider U as all possible schedules L, n as the input size of PESBA, f(·) as the total preference function F(·). The additional group constraint corresponds to the requirement that each event can be assigned at most one starting point in our problem. The imperfect oracle states that to get an element with a good marginal value in polynomial time, the algorithm has to ask an imperfect oracle, which may only be able to return some non-optimal elements. The α-approximate oracle is used to deal with general |T| cases, and its role will be clear in Section 4. In this section, we can assume that we have a 1approximate oracle (i.e., α = 1) since we consider the polynomially bounded |T| case. This implies that the size of L (i.e., the ground element set) is polynomially bounded, so finding an element with the maximum marginal value takes polynomial time.

When α = 1, SMGC is a special case of submodular maximization subject to a matroid constraint [C˘alinescu et al., 2011], which admits a (1 - 1e )-approximation. However, the algorithm is involved, and it is based on the multilinear extension of a submodular function. For the matroid constraint, the approximate ratio of the natural greedy algorithm is proved to be 12 [Horel, 2015] whose proof is based on both the exchange property of a matroid and the submodularity. In Section 3.4, we show that the ratio only depends on the submodularity for our problem and thus simplifies the proof for the α = 1 case.

Formally, the analysis mainly consists of three steps. In the first step, we show that the agreement function can be computed in polynomial time. In the second step, we prove that the agreement function is submodular. In the last step, we demonstrate that the natural greedy algorithm achieves 1 α+1 - approximation to SMGC with an α-approximate oracle; when α = 1, it is a 1 2 -approximate algorithm. The detailed description is as follows.

1. We show that given any partial solution S, the value of agri(S) can be computed in polynomial time for any i ∈ A. This implies that the cumulative function F in Algorithm 1 can also be computed in polynomial time. This part is deferred to Section 3.2.

Lemma 1. Given any partial solution S ⊆ L, there is an algorithm running in polynomial time that computes the value of agri(S).

1. We demonstrate that the agreement function agri(·) is a submodular function. We actually show a stronger result, i.e., the agreement function is a rank function of some matroid which also plays an important role in the arbitrary T case. This part is shown in Section 3.3.

Lemma 2. Consider any agent i ∈ A, the agreement function agri : 2L →N≥0 is a submodular function.

1. We prove that greedily picking the element with a good marginal value from unselected groups achieves 1 α+1 - approximation for SMGC. This part is in Section 3.4.

Lemma 3. The natural greedy algorithm (Algorithm 2) achieves 1 α+1 -approximation to the problem of submodular maximization with group constraints and an αapproximate oracle stated in Definition 1.

The first part of Theorem 1 can be proved by combining the above lemmas and setting α = 1, and the other part is based on another result for submodular maximization.

3.2 Agreement Function Computation

In this section, we show that the maximum agreement of any partial solution can be computed in polynomial time. We fix an agent i ∈ A and analyze her agreement function agri(·). For notation convenience, we drop the subscript i for the time.

For an event or job interval, we use s(·) and f(·) to denote the first and the last time slot occupied by the interval. Given a partial solution S ⊆ L, let E′ be the scheduled event set. Define Ψ to be the set of s(j), f(j), s(e), f(e) for all j ∈ J and e ∈ E′ (remove duplicate values). Note that the size of Ψ is polynomially bounded regardless of the size of the time span T. We sort all time slots in Ψ in increasing order obtaining Ψ = { t1, . . . , tκ }. Then, the time slots in Ψ split the whole time span into several segments, i.e., every adjacent two-time slot in Ψ defines a segment ϕ. See the left part of Figure 2 for an example. Let Φ := {ϕ1, . . . , ϕℓ } be the set of segments. Note that a segment ϕ may contain more than one time slot. Let c(ϕ) be the capacity of the segment ϕ, i.e., c(ϕ) is the number of time slots that are included in ϕ. Note that it must be the case that for any segment ϕ ∈ Φ and any job or event interval I, ϕ is either completely included in I or ϕ has no overlap with I.

Our algorithm for computing agr(·) is built based on the min-cost max-flow algorithm. In the following, we first introduce the construction of the flow network and then prove the correctness. Given any partial solution S and a job set J, we first construct the starting point set Ψ and the segment set Φ. Then, we construct a network G := (s, t,A ∪ B,E) according to Ψ and J. (I) For each job j ∈ J, we create a vertex a in A. (II) For each segment ϕ ∈ Φ, we have one vertex b in B. (III) There is a directed edge e from a to b if and only if a's corresponding job can be scheduled at the time slots included in b's corresponding segment (let E2 be these edges). (IV) Add a source s and create a directed edge from s to each vertex in A (let E1 be these edges). (V) Add a sink t and create a directed edge from each vertex in B to t (let E3 be these edges). (VI) Every edge in E1 has the same cost 0 and only connects one vertex in A. Let pj be e := (s, a)'s capacity where a's corresponding job is j. (VII) Every edge in E2 has the same cost 0, and edges that are connected with the same job vertex j have the same capacity pj. (VIII) Each edge in E3 only connects one vertex from B; let c(ϕ) be e := (b, t)'s capacity where ϕ is the corresponding segment of b; the cost of e is 1 if there is an event occupying ϕ otherwise the cost of e is 0. The goal is to find the cheapest way to send ∑j∈J pj amount of flows from s to t. An example is shown in Figure 2.

It is well-known that the min-cost max-flow problem can be solved in polynomial time. The solution to min-cost maxflow has integral property as long as all capacities are integral, i.e., there exists an optimal solution to min-cost maxflow such that all flow values are integral. Lemma 4 captures the equivalence between the instance of our problem and the constructed min-cost max-flow instance.

Lemma 4. Given any instance I of our problem with job set J and partial solution S. Let I ′ be the constructed min-cost max-flow instance. Then, the constructed min-cost max-flow instance has a feasible integral flow assignment S′ with cost ct(S′ ) if and only if the instance I has a job schedule S with the agreement |st(S)| - ct(S′ ), where st(S) is a set of time slots that are occupied by some scheduled event in S.

Lemma 1 can be proved by Lemma 4.

3.3 Submodularity of the Agreement Function

In this section, we show that the agreement function agri(·) is submodular for any agent i ∈ A. To this end, we fix an agent i ∈ A and analyze her agreement function. For notation convenience, we drop the subscript i.

For convenience, each unit of a job is considered as a new job, i.e., we create pj new jobs with unit length for each job j. In this way, we can assume that all jobs in J have unit length. Given any partial solution S ⊆ L, let st(S) be a set of time slots that are occupied by scheduled events in S, so st(S) ⊆ T. Given any schedule of jobs in J, the agreement produced by the partial solution S and the job schedule is equal to the difference between the size of st(S) and the number of time slots that are occupied by some jobs in the job schedule. So, finding the maximum agreement produced by the partial solution S is equivalent to finding a schedule of jobs in J that uses the minimum number of time slots in st(S).

This motivates us to define the following set system, which is called scheduling matroid (Definition 2). We shall connect the size of an independent set in the defined set system with the value of the maximum agreement later.

Definition 2 (Scheduling Matroid). The scheduling matroid M(J) := (T, I) is defined over the time slot set T for a job set J, where T is the ground element set and I is a collection of all independent sets. Each job in J has a release time, unit processing time, and deadline. A set I ⊆ T is an independent set if there exists a feasible schedule of J only using time slots T \ I.

Consider any partial solution S, let I ⊆ st(S) be an independent set with the maximum size that is included in st(S).

By definition, |I| is the maximum number of time slots in st(S) such that all jobs in J can be scheduled in T \ I. Thus, the size of I is equal to the maximum agreement produced by the partial solution S since all other time slots in st(S) \ I have to be used to ensure a feasible job schedule. The above connection is captured by Observation 1.

Observation 1. Given any partial solution S, let I be a maximum independent set defined in Definition 2 that are included in st(S). Then, |I| is equal to the maximum agreement produced by the partial solution S.

As one may observe, the maximum independent set that is included in some given element set aligns with the concept of the rank in matroid theory. The rank function of a matroid is one of the famous submodular functions. Hence, in the following, we aim to prove the scheduling matroid defined in Definition 2 is a matroid. In fact, besides the submodularity, the polynomial implementation of Algorithm 1 in Section 4 also depends on the property that the scheduling matroid is a matroid. We start with restating the definition of a matroid and its rank function in Definition 3.

Definition 3 (Matroid). A set systemM := (U, I) is a matroid if the collection I of subsets of U has the following properties: (i) ∅ ∈ I; (ii) if A ∈ I and B ⊆ A, then B ∈ I; (iii) If A, B ∈ I and |B| > |A|, then there exists x ∈ (B\A) such that A ∪ {x} ∈ I. Given any set S ⊆ U, the rank of S is defined as the size of the maximum independent set included in S, i.e., rank(S) :=maxI∈I:I⊆S|I|.

Lemma 5. The scheduling matroid is a matroid.

Lemma 2 can be proved by Lemma 5 and Observation 1.

3.4 Submodular Maximization with Group Constraints and Imperfect Oracle

In this section, we show greedily picking an element with a "good" marginal value from the unselected groups is a 1 α+1 - approximate algorithm for SMGC under an α-approximate oracle g(·, ·) (see Algorithm 2). We cannot find the element with the exact maximum marginal value because the oracle is α-approximate. When α = 1, Algorithm 2 is 12 - approximate, which aligns with the result for submodular maximization subject to matroid constraint stated in [Horel, 2015]. But our proof only uses the monotone and submodular properties and thus simplifies the proof in [Horel, 2015]. For α > 1, our result generalizes the approximation ratio stated in [Chekuri and Kumar, 2004] where they also consider the α-approximate oracle but only focus on coverage functions.

4 An Algorithmic Framework for Arbitrary T

In this section, we consider the case where |T| is an arbitrary value and present an algorithmic framework for this case. Given any approximation algorithm for the one-event instance, the proposed algorithmic framework rooted in Algorithm 1 is able to extend the given approximation algorithm to the general case by only losing a small constant factor on the approximation ratio. The formal description can be found in Theorem 2. The one-event instance is a special case of PESBA where there is only one event that needs to be scheduled; we use PESBA with |E| = 1 to denote this case.

Algorithm 2 Natural Greedy for SMGC

Input: The ground element set U and its group collection G1, . . . , Gκ; Amonotone submodular function f : 2U → R≥0; The capacity k ∈ N≥0. Output: A subset S ⊆ U with |S| ≤ k. 1: S ← ∅. 2: while |S| ≤ k do 3: H ← ∅. 4: for each unselected group Gi do 5: ai ← g(S, Gi). 6: H ← H ∪ { ai }. 7: end for 8: a∗ ←maxb∈H f(S ∪ { b }) - f(S). 9: S ←S ∪ {a∗ }. 10: end while 11: return S.

We remark that, for our problem, it is hard to use the standard technique to make Algorithm 1 run in polynomial time for the arbitrary |T| case; see full version [Li et al., 2024] for discussions.

Algorithmic Ideas. To design an algorithmic framework that achieves Theorem 2, our idea is to release the full power of Algorithm 1 and Lemma 3. Recall that in Section 3, we consider the polynomially bounded |T|, which is equivalent to assuming that we have a 1-approximate oracle for SMGC (Definition 1). By Lemma 3, as long as we have an α-approximate oracle, Algorithm 1 with line 5 replaced (which is Algorithm 4 in full version [Li et al., 2024]) is a 1 α+1 -approximate algorithm. Thus, in this section, we aim to design such an α-approximate oracle to replace line 5 of Algorithm 1. To this end, we need to build an algorithm ALG (Algorithm 3) such that ALG satisfies the following two properties: (i) ALG runs in polynomial time (Observation 2); (ii) given any partial solution S and an event e, ALG returns a position for the event e such that the resulting schedule is 1α -approximate (Lemma 7).

We shall build the polynomial time oracle based on the given 1α -approximate algorithm for PESBA with |E| = 1. To achieve this, the main obstacle is that the given one-event instance algorithm only works for the case where there is no partial solution; this disagrees with the requirement of the oracle. Our idea to fix this issue is to construct an equivalent pure one-event instance so that when we run 1α -approximate algorithm on the constructed one-event instance, it is able to return a good position for the instance with the partial solution. This method works mainly due to the exchange property of the scheduling matroid.

Formally, we use OneEvent(·, ·) to represent the given 1α -approximate algorithm for PESBA with |E| = 1. The algorithm OneEvent(A, e∗ ) takes the agent set A (including their job sets) and an event e∗ as the input; its output is a time slot t∗ that indicates the scheduled position for the given event. By our assumption, the returned time slot t∗ satisfies the following property: ∑i∈A agri({ (e∗ , t∗ ) }) ≥ 1α · maxt∈T ∑i∈A agri({ (e∗ , t) }). Let GoodPosn(·, ·) be the desired approximate oracle, and GoodPosn(S, e∗ ) shall use the given 1α -approximate one-event algorithm as a subroutine. It takes two parameters as the input: the given partial solution S and an event e∗ , and will return a time slot that indicates the scheduled time of the given event. Recall that, given a partial solution S, we need to construct an equivalent pure one-event instance A′ such that the time slot t∗ returned by OneEvent(A′ , e∗ ) is a good position for e∗ , i.e., ∑i∈A agri(S ∪ { (e∗ , t∗ ) }) ≥ 1α · maxt∈T ∑i∈A agri(S ∪ { (e∗ , t) }). The above inequality shall imply that GoodPosn(·, ·) is exactly the same as the α-approximate oracle g inDefinition 1, which leads to a 1 α+1 - approximate algorithm by Lemma 3.

In the following, we focus on how to construct such an equivalent instance A′ . We start with an important property of the scheduling matroid.

Lemma 6. For a scheduling matroid M(J) := (T, I) defined in Definition 2, consider a time slot set S ⊆ T and let F ∈ I be a maximum independent set that is included in S. For each time slot in F, create a rigid job and let J ′ be all these rigid jobs. The job set J ∪ J ′ defines a new scheduling matroid, denoted by M(J ∪ J ′ ) := (T, I ′ ). Consider a time slot set H ⊆ T and let B ∈ I ′ be a maximum independent set that is included in H. Then, F ∪ B ∈ I is a maximum independent set inM(J) that is included in S ∪H.

Given any partial solution S, recall that a maximum independent set included in st(S) is a set of time slots with the maximum size that produces the agreement (Observation 1). We call these time slots agreement time slots. Thus, Lemma 6 actually suggests a "stability" property of these agreement time slots. In other words, consider two partial solutions S and H. The agreement time slot of the partial solution S is a subset of the agreement time slot of the partial solution S∪H. This crucial stable property motivates the pure one-event instance construction method, where we shall replace all agreement time slots of partial solution S with many rigid jobs. In this way, we eliminate the impact of the partial solution S and focus on finding the maximum agreement of the partial solution H. Then, by Lemma 6, the union of S's and H's agreement time slots shall be the maximum agreement time slots of the whole solution S ∪H. The only issue is that we need to be careful when creating rigid jobs since the number of constructed rigid jobs is required to be polynomial. This requirement can be satisfied by aggregating all agreement time slots in each segment when computing the min-cost flow (Algorithm 3). An example is shown in Figure 3.

Observation 2. Algorithm 3 runs in polynomial time, i.e., Algorithm 3 creates a polynomial number of rigid jobs.

Lemma 7 states that Algorithm 3 GoodPosn(·, ·) is a valid α-approximate oracle for the submodular maximization problem stated in Definition 1. The correctness of Lemma 7 mainly relies on Lemma 6.

Lemma 7. Given any partial solution S and an unscheduled event e∗ , let t∗ be the time slot returned by Algo- Algorithm 3 GoodPosn(·, ·)

Input: A partial solution S; An unscheduled event e∗ .

Output: A good position t∗ for event e∗ .

• 1: for each agent i ∈ A do
• 2: Compute a schedule for Ji by min-cost max-flow.
• 3: for each segment in { ϕ ∈ Φ | ϕ ⊆ st(S) } do
• 4: Aggregate all agreement time slots forming an agreement segment ϕ′ .
• 5: Create a rigid job j ′ for ϕ′ .
• 6: end for
• 7: Ji ← Ji ∪ { all created rigid jobs }.
• 8: end for
• 9: return t∗ ←OneEvent(A, e∗ ).

rithm 3. Then, we have ∑i∈A agri(S ∪ { (e∗ , t∗ ) }) ≥ 1α · maxt∈T ∑i∈A agri(S ∪ { (e∗ , t) }).

The complete algorithm for arbitrary |T | (see Algorithm 4 in full version [Li et al., 2024]) just replaces line 5 of Algorithm 1 with Algorithm 3. Theorem 2 is implied by Lemma 3 and Lemma 7. Combing Theorem 4 in full version [Li et al., 2024] with Theorem 2 implies a 1 2 -approximate algorithm for the general |T| case.

5 Conclusion

In this paper, we study the problem of public event scheduling with busy agents, in which a set of public events are required to be scheduled to let agents attend for a period of time as long as possible. We present a general algorithmic framework and give a polynomial time algorithm with a constant approximation ratio for such an NP-hard problem.

This work points out many interesting future directions. Firstly, it would be interesting to see a better approximation algorithm or a lower bound. Secondly, our 12 -approximate algorithm for general cases uses an involved optimal algorithm for one-event instances. So, a simplified algorithm for oneevent instances would be beneficial, even if some approximation ratio needs to be sacrificed. Lastly, the weighted setting of our problem is also interesting, i.e., different agents hold a distinct preference for the same event.

Contribution Statement

All authors (ordered alphabetically) have equal contributions and are corresponding authors.

Acknowledgements

We thank the anonymous reviewers for their many insightful suggestions. Bo Li is funded by HKSAR RGC (No. PolyU 15224823) and GDSTC (No. 2023A1515010592). Ruilong Zhang was supported by NSF grant CCF-1844890.