Problem statement Trichromatic Online Matching (TOM) MaxSum(M)-EtET, pE,wEw U(t, p,w/st the total utility Find a matching M to maximize Deadline constraint Each object should be matched before the leaving time Range Constraint o a workplace can only be matched to tasks/workers whose range can cover it Invariable Constraint Once a triple(t, p, w is matched, it cannot be changed The offline version of toM is np-hardProblem Statement ⚫ Trichromatic Online Matching (TOM) ⚫ Find a matching 𝑀 to maximize the total utility MaxSum(M)=σ𝑡∈𝑇,𝑝∈𝑃,𝑤∈𝑊 𝑈(𝑡, 𝑝, 𝑤) s.t. ⚫ Deadline Constraint. o Each object should be matched before the leaving time. ⚫ Range Constraint. o A workplace can only be matched to tasks/workers whose range can cover it. ⚫ Invariable Constraint o Once a triple (t, p, w) is matched, it cannot be changed. ⚫ The offline version of TOM is NP-hard. 26