DeDPO: Bridging Online Social Interests with Offline Spatio-Temporal Constraints

TL;DR

Managing Event-Based Social Networks (EBSNs) like Meetup or Plancast is no longer just about recommending a single event. This paper tackles the Utility-aware Social Event-participant Planning (USEP) problem—a complex optimization task where users want to attend multiple events while juggling time conflicts, limited venue capacities, and personal travel budgets. The authors propose the DeDPO algorithm, a local-ratio-based framework that offers a guaranteed 1/2-approximation ratio while remaining scalable to hundreds of thousands of users.

The Conflict: Why Simple Recommendations Fail

In the real world, a sports fan might want to attend a morning running club, a midday tennis match, and an afternoon music party. Existing EBSN models often fail because they treat events as isolated units. In reality:

1. Spatio-Temporal Overlap: You can't be in two places at once.
2. Travel Budget: Moving between venues costs time and money.
3. Global Capacity: Popular events have limited seats, making independent local optimization (simply picking the "best" events for one person) lead to global inefficiency.

The authors prove that finding the optimal global schedule under these constraints is NP-hard, necessitating sophisticated approximation strategies.

Methodology: Decomposition through Local Ratio

The core insight of the paper is the use of the Local Ratio Theorem. Instead of solving the massive global assignment problem at once, the authors decompose it into two distinct steps.

1. The Pseudo-Event Strategy

To handle event capacities ($c_v$), the authors split each event into $c_v$ "pseudo-events." This allows the algorithm to treat capacity as a discrete matching problem.

2. The Two-Step Framework

• Step 1 (Forward Pass): The algorithm iterates through users. For each user, it finds an optimal individual schedule using Dynamic Programming (DeDP) or a faster Greedy approach (DeGreedy). Crucially, the "utility" values are updated (decremented) as pseudo-events are "claimed," ensuring that later users see a modified benefit landscape.
• Step 2 (Backward Pass): To resolve cases where a pseudo-event was assigned to multiple users during the forward pass, the algorithm iterates backwards. It grants the event to the user who "needed" it most in the local-ratio decomposition, ensuring all capacity constraints are strictly met.

Optimized Performance: DeDPO & DeGreedy

While the initial DeDP algorithm is theoretically sound, it is a memory hog. The authors introduced DeDPO (DeDP Optimized), which tracks the "last user" to claim an event instead of storing full utility matrices.

For massive datasets, they offer DeGreedy, swapping the expensive Dynamic Programming step for a ratio-based heuristic.

Key Experimental Findings

• Efficiency: DeDPO reduces memory consumption by an order of magnitude compared to standard DeDP.
• Scalability: On datasets with 100k+ users (e.g., Singapore or Vancouver Meetup data), DeGreedy returns high-utility schedules in about 13 minutes, whereas non-optimized approaches fail to scale.
• Conflict Handling: As event conflicts increase (higher $cr$), DeDP/DeDPO maintains a significant lead in total utility over simple greedy baselines because it looks ahead at the "bottleneck" events.

Deep Insight & Future Outlook

The USEP framework is a masterclass in applying classic combinatorial optimization (Local Ratio) to modern social data. Its strength lies in its flexibility—it accounts for the "triangle inequality" of travel costs, meaning it realistically models the physical world.

Limitations: The current model assumes fixed event times. Future iterations could explore "flexible" start times or group-based planning where friends want to attend events together (Social Affinity).

Takeaway: For developers building city-scale itinerary planners or social discovery apps, the DeDPO framework provides a robust blueprint for maximizing user happiness without breaking the laws of physics or event capacities.