Scheduling Public and Private Activities for Multiple Agents

Abstract

Activity scheduling arises widely in both societal coordination and individual planning, and is a major research topic in computer science and operations research. Classical scheduling models typically involve assigning a set of homogeneous jobs to machines or time slots to optimize metrics such as makespan or sum of completion time. However, many real-world scenarios involve activities that come from multiple agents and cannot be neatly categorized as independent tasks. In particular, some activities are public, requiring the simultaneous participation of multiple agents (e.g., meetings, seminars, or maintenance periods), while others are private, handled individually by each agent. Motivated by such scenarios, this thesis studies scheduling public and private activities for multiple agents under various practical constraints, with the goal of optimizing both social welfare and fairness.

In the first part, we study the setting where private activities take priority over public ones. Agents must complete all their private jobs and may attend public events only if doing so does not interfere with their job schedules. The goal is to maximize the total time agents can spend in public activities. In this part we consider the case where all the public events share a common event interval. We first show that the problem is NP-hard. For the special case where the length of event interval is polynomially bounded, we design a greedy algorithm achieving a 1/2-approximation. For the general event interval, we propose an algorithmic framework that achieves a 1/(α + 1)-approximation given an alpha-approximation algorithm for the one-event case. We also present a polynomial-time exact algorithm for the one-event instance, implying an overall 1/2-approximation for the general setting. For the fairness objective of maximizing the minimum attendance across agents, we prove that no f-approximation exists for any computable function f unless P = NP. We also study a variant with multiple identical public events where each agent can attend at most one. In this case, the max-sum version admits a (1 - 1/e)-approximation, while the max-min version remains inapproximable.

In the second part, we consider the opposite priority: public events must be fully attended, and agents cannot process private jobs during their occurrence. Each private job carries a specific profit, and the objective is to schedule all public events such that agents can complete as many profitable private jobs as possible, i.e., maximize weighted throughput. We first study the case where all public events share a common interval and all jobs have equal profits. For unit-length jobs, we show that the problem is solvable in polynomial time when there is only one event or when all events are of unit length. Then we study a special case where each agent’s jobs share a common interval, while public events have individual intervals. This case generalizes the multiple knapsack problem and thus is strongly NP-hard. For several special cases, we design polynomial-time approximation schemes, including when there is only one event, a constant number of events, or when event intervals are disjoint.

In the third part, we move beyond the public-private framework and focus on fair scheduling of private activities across multiple agents. Each agent has a set of unit-length jobs with associated weights, and the goal is to maximize throughput, subject to a total weight (knapsack) constraint and fairness constraints that limit how many jobs can be selected from each agent. This leads to a challenging general problem: fair submodular maximization under a knapsack constraint. While no non-trivial approximation is known in general without relaxing either constraint, we make progress by showing that when the number of agents is constant, there exists a polynomial-time algorithm achieving a constant-factor approximation with high probability. Moreover, if either the fairness or knapsack constraint is relaxed to be satisfied in expectation, we obtain a tight (1 - 1/e - ε)-approximation for any ε > 0 using randomized pipage rounding.

Date of Award	5 Sept 2025
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Minming LI (Supervisor) & Peter ROBINSON (Supervisor)