Optimal Region Search with Submodular Maximization

Xuefeng Chen, Xin Cao, Yifeng Zeng, Yixiang Fang, Bin YaoIJCAI 2020 · DOI

Introduction

In the realm of Location-Based Services (LBS), "region search" is a fundamental task—identifying an area that maximizes a specific value, such as the density of amenities, within a defined travel budget. Traditional approaches often simplify regions into geometric shapes like circles or rectangles. However, real-world urban environments are defined by complex road networks where regions are irregularly shaped subgraphs. Furthermore, standard additive value functions fail to account for the principle of diminishing returns. This paper introduces ORS-SM, a framework that addresses these challenges by maximizing submodular objective functions over connected subgraphs.

Problem Formulation

The Optimal Region Search with Submodular Maximization (ORS-SM) problem involves finding a connected subgraph (a region) that maximizes a submodular function $f(S)$ while ensuring the total edge cost of connecting the nodes in $S$ does not exceed a budget $\Delta$. Submodularity is crucial for realism; for instance, in a diversity-focused search, the first coffee shop found adds significant value, whereas subsequent ones offer diminishing marginal utility.

Example of a network graph where nodes have attributes (e.g., {mall, bar}) and edges have travel costs.

As illustrated in Figure 1, the network consists of nodes with specific attributes and weighted edges representing costs. Finding the optimal connected subgraph is NP-hard, necessitating efficient approximation strategies.

Algorithmic Framework

The authors propose two primary algorithmic solutions:

  1. AppORS (Approximation ORS): This algorithm utilizes a greedy approach based on Nemhauser’s algorithm. it selects nodes that provide the highest marginal gain to the objective function while ensuring they can be connected within the budget. It provides a theoretical approximation ratio of $1/O(\sqrt{\Delta/b_{min}})$.
  2. IAppORS (Improved AppORS): To enhance practical performance, two heuristics were developed:
  3. Heu1: Employs "Lazy Evaluations" to prune unnecessary calculations and uses a Minimum Spanning Tree (MST) as a fast proxy for the Steiner Tree problem to estimate connection costs.
  4. Heu2: Further optimizes by restricting the search space to immediate neighboring nodes, drastically reducing computational overhead in large-scale networks.

Experimental Evaluation

The framework was tested on real-world datasets from Singapore (SG), Austin (AS), and California (CA), alongside synthetic data (SY). The evaluation focused on two key metrics: efficiency (run time) and solution quality (objective score).

Performance comparison of AppORS and IAppORS variants against the GCBAll baseline on SG and AS datasets.

Key Results

  • Efficiency: As shown in Figure 2, the proposed algorithms are orders of magnitude faster than the exhaustive baseline (GCBAll). Specifically, IAppORSHeu2 maintains a near-constant runtime even as the budget $\Delta$ increases, whereas the baseline's runtime grows exponentially.
  • Quality: Despite the significant speedup, the IAppORS variants consistently achieve objective scores exceeding 90% of those found by the exhaustive search, demonstrating that the heuristics do not significantly compromise solution quality.
  • Scalability: Tests on synthetic datasets with up to 30,000 nodes confirmed that IAppORSHeu2 scales gracefully, making it suitable for large-scale urban planning and real-time query applications.

Conclusion

The ORS-SM framework successfully bridges the gap between complex, realistic submodular queries and the topological constraints of road networks. By utilizing Steiner Tree approximations and localized search heuristics, the authors provide a solution that is both theoretically grounded and practically viable for massive datasets. Future work will explore advanced spatial indexing to further reduce query times to the millisecond range.

Summary updated

BibTeX
@inproceedings{chen2020optimal,
  author = {Xuefeng Chen and Xin Cao and Yifeng Zeng and Yixiang Fang and Bin Yao},
  title = {{Optimal Region Search with Submodular Maximization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/169},
}
Figure