In recent years, with the increasing popularity and growth of social networks and mobile devices, the research on location-based social networks (LBSN) has attracted a lot of attention. As an important research topic in LBSN, submodular optimization in location-based social networks (SO-LBSN) has been considered by many studies, because it is useful in applications such as service location selection, marketing, and tourist trip planning. However, due to the rich information in LBSN (e.g., locations, user relationships), various constraints (e.g., spatial constraint, routing constraint) could be specified in LBSN applications, existing methods often fail in solving such problems on SO-LBSN efficiently. In this thesis, we study three typical problems on SO-LBSN, and utilize the location information, the properties of the submodular functions and the constraints to develop efficient algorithms. Firstly, we investigate the problem of maximizing bichromatic reverse k-nearest neighbor in LBSNs. We use a general submodular function to compute the value of influence. We design a hybrid quadtree-grid index to manage the server points and client points and to reduce the kNN computation cost substantially, and propose an optimization technique called “maximal-arc” to improve the efficiency of the influence computation. We also develop both exact and approximation algorithms with guaranteed error bounds. Secondly, we focus on the problem of optimal region search with submodular maximization. We prove that the problem is NP-hard and propose an approximation algorithm AppORS. We also design another algorithm with the same approximation ratio called IAppORS to further improve the effectiveness of AppORS, and present two heuristic methods to implement a key function of IAppORS. Finally, we study the constrained path search with submodular maximization query. We show that answering the query is NP-hard. We first propose a concept called "submodular α-dominance" by utilizing the properties of the submodular function, and develop an approximation algorithm based on this concept. By relaxing the submodular α-dominance conditions, we design another approximation algorithm with better efficiency that has the same error bound. We also utilize the way of bi-directional path search to further improve the efficiency, and propose a heuristic polynomial algorithm that is efficient yet effective in practice.