Qian-Ping Gu
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Qian-Ping Gu has a total of 20 co-authors. Here are the top co-authors by number of shared publications:
- Jiajian Leo Liang
School of Computing Science Simon Fraser University Canada
4 shared publications - Anxiao He
University of Virginia, Charlottesville, VA, USA
3 shared publications - Kai Bu
Zhejiang University, Hangzhou, China
3 shared publications - Kui Ren
Zhejiang University
3 shared publications Guochuan Zhang
Zhejiang University
2 shared publicationsJiajian Leo Liang
Simon Fraser University
2 shared publications
Latest Publications
- 6 February 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Dependable and Secure Computing
- Vol. 23 (3) , 6183-6195
SwiftOracle: Orthogonality-Driven Private Multipath Validation
Path validation enables end-hosts to regulate and verify packet forwarding that otherwise remains transparent in the current internet architecture. It promises various guarantees in security and privacy for internet users. Recent advances in path validation start to secure multipath routing and protect path privacy. However, state-of-the-art private multipath validation limit in efficiency and may not apply to relatively large networks due to impractically long proofs. In this paper, we propose SwiftOracle that leverages orthogonality to achieve efficient private multipath validation. SwiftOracle uses orthogonal vectors as alternative keys; this enables much efficient proof computation. To protect path privacy, SwiftOracle only allows each router to know limited neighborship information. Furthermore, we develop constant-size proofs for SwiftOracle to guarantee scalability in large-scale networks. We implement SwiftOracle using DPDK and evaluate its performance in comparison with state-of-the-art VALNET. The results show that SwiftOracle can deliver 6$\times$ faster computation speed, support at least 4$\times$ larger network scale with more intricate topologies, and yield over 21$\times$ higher throughput on average.
- 6 February 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Dependable and Secure Computing
- Vol. 23 (3) , 6183-6195
SwiftOracle: Orthogonality-Driven Private Multipath Validation
Path validation enables end-hosts to regulate and verify packet forwarding that otherwise remains transparent in the current internet architecture. It promises various guarantees in security and privacy for internet users. Recent advances in path validation start to secure multipath routing and protect path privacy. However, state-of-the-art private multipath validation limit in efficiency and may not apply to relatively large networks due to impractically long proofs. In this paper, we propose SwiftOracle that leverages orthogonality to achieve efficient private multipath validation. SwiftOracle uses orthogonal vectors as alternative keys; this enables much efficient proof computation. To protect path privacy, SwiftOracle only allows each router to know limited neighborship information. Furthermore, we develop constant-size proofs for SwiftOracle to guarantee scalability in large-scale networks. We implement SwiftOracle using DPDK and evaluate its performance in comparison with state-of-the-art VALNET. The results show that SwiftOracle can deliver 6$\times$ faster computation speed, support at least 4$\times$ larger network scale with more intricate topologies, and yield over 21$\times$ higher throughput on average.
- 18 July 2025
- Published by Springer Nature
- p. 418-432
Exact Set Packing in Multimodal Transportation with Ridesharing System for First/Last Mile
- 18 July 2025
- Published by Springer Nature
- p. 418-432
Exact Set Packing in Multimodal Transportation with Ridesharing System for First/Last Mile
- 18 July 2025
- Published by Springer Nature
- p. 173-187
Average Sensitivity of Breadth-First Search Algorithms on Grids
- 18 July 2025
- Published by Springer Nature
- p. 173-187
Average Sensitivity of Breadth-First Search Algorithms on Grids
- Open Access
Exact Set Packing in Multimodal Transportation with Ridesharing System for First/Last Mile
We propose a centralized transportation system that integrates public transit with ridesharing to provide multimodal transportation. At each time interval, the system receives a set of personal drivers, designated drivers, and public transit riders. It then assigns all riders to drivers, ensuring that pick-ups and drop-offs occur at designated transit stations. This effectively replaces first-mile/last-mile (FM/LM) segments with a ridesharing alternative, reducing overall commuting time. We study two optimization problems: (1) minimizing the total travel distances of drivers and (2) minimizing the number of designated drivers required to serve all riders. We show the optimization problems are NP-hard and give hypergraph-based integer linear programming exact algorithm and approximation algorithms. To enhance computational efficiency, we introduce a clustering heuristic that utilizes both spatial and temporal aspects of the input data to accelerate rider-to-driver assignments. Finally, we conduct an extensive computational study using real-world datasets and surveys from Chicago to evaluate our model and algorithms at a city-wide scale.
Open AccessExact Set Packing in Multimodal Transportation with Ridesharing System for First/Last Mile
We propose a centralized transportation system that integrates public transit with ridesharing to provide multimodal transportation. At each time interval, the system receives a set of personal drivers, designated drivers, and public transit riders. It then assigns all riders to drivers, ensuring that pick-ups and drop-offs occur at designated transit stations. This effectively replaces first-mile/last-mile (FM/LM) segments with a ridesharing alternative, reducing overall commuting time. We study two optimization problems: (1) minimizing the total travel distances of drivers and (2) minimizing the number of designated drivers required to serve all riders. We show the optimization problems are NP-hard and give hypergraph-based integer linear programming exact algorithm and approximation algorithms. To enhance computational efficiency, we introduce a clustering heuristic that utilizes both spatial and temporal aspects of the input data to accelerate rider-to-driver assignments. Finally, we conduct an extensive computational study using real-world datasets and surveys from Chicago to evaluate our model and algorithms at a city-wide scale.
- 9 December 2023
- Published by Springer Nature
- p. 366-379
Algorithms for the Ridesharing with Profit Constraint Problem
- 9 December 2023
- Published by Springer Nature
- p. 366-379
Algorithms for the Ridesharing with Profit Constraint Problem
- Open Access
Algorithms for the Ridesharing with Profit Constraint Problem
Mobility-on-demand (MoD) ridesharing is a promising way to improve the occupancy rate of personal vehicles and reduce traffic congestion and emissions. Maximizing the number of passengers served and maximizing a profit target are major optimization goals in MoD ridesharing. We study the ridesharing with profit constraint problem (labeled as RPC) which considers both optimization goals altogether: maximize the total number of passengers subject to an overall drivers' profit target. We give a mathematical formulation for the RPC problem. We present a polynomial-time exact algorithm framework (including two practical implementations of the algorithm) and a (1/2)-approximation algorithm for the case that each vehicle serves at most one passenger. We propose a (2/3*lambda)-approximation algorithm for the case that each vehicle serves at most lambda >= 2 passengers. Our algorithms revolve around the idea of maximum cardinality matching in bipartite graphs and hypergraphs (set packing) with general edge weight. Based on a real-world ridesharing dataset in Chicago City and price schemes of Uber, we conduct an extensive empirical study on our model and algorithms. Experimental results show that practical price schemes can be incorporated into our model, our exact algorithms are efficient, and our approximation algorithms achieve about 90% of optimal solutions, in the number of passengers served.
Open AccessAlgorithms for the Ridesharing with Profit Constraint Problem
Mobility-on-demand (MoD) ridesharing is a promising way to improve the occupancy rate of personal vehicles and reduce traffic congestion and emissions. Maximizing the number of passengers served and maximizing a profit target are major optimization goals in MoD ridesharing. We study the ridesharing with profit constraint problem (labeled as RPC) which considers both optimization goals altogether: maximize the total number of passengers subject to an overall drivers' profit target. We give a mathematical formulation for the RPC problem. We present a polynomial-time exact algorithm framework (including two practical implementations of the algorithm) and a (1/2)-approximation algorithm for the case that each vehicle serves at most one passenger. We propose a (2/3*lambda)-approximation algorithm for the case that each vehicle serves at most lambda >= 2 passengers. Our algorithms revolve around the idea of maximum cardinality matching in bipartite graphs and hypergraphs (set packing) with general edge weight. Based on a real-world ridesharing dataset in Chicago City and price schemes of Uber, we conduct an extensive empirical study on our model and algorithms. Experimental results show that practical price schemes can be incorporated into our model, our exact algorithms are efficient, and our approximation algorithms achieve about 90% of optimal solutions, in the number of passengers served.
- 14 September 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Dependable and Secure Computing
- Vol. 21 (4) , 2720-2734
SwiftParade: Anti-Burst Multipath Validation
Path validation promises a necessary security add-on for future Internet architectures. It authenticates not only source identities but also the exact path where a packet forwards through. This offers users more flexibility and reliability in network services. Most existing solutions focus on single-path validation that pre-correlates a packet to a specific forwarding path. However, parallel transmissions in multipath routing tend to induce bursty traffic that is hardly validated in time by existing solutions. In this paper, we present SwiftParade as the first attempt toward anti-burst multipath validation. It proposes a composite validation technique that can simultaneously validate a group of packets likely from multiple different paths. This helps to amortize the validation overhead across packets of the entire group instead of imposing the validation overhead equally on every packet. To implement composite validation, SwiftParade further explores a noncommutative homomorphic asymmetric encryption scheme. We prove effectiveness and security of SwiftParade through theoretical analysis. We also conduct extensive experiments to evaluate SwiftParade performance. The results show that SwiftParade offers high efficiency and applicability to multipath validation with complex routing topologies. In comparison with the state-of-the-art multipath validation solution—Atlas, SwiftParade speeds up packet processing by 2.5× $\sim 8.3\times$ and increases communication throughput by 2.8× $\sim 10.2\times$ .
- 14 September 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Dependable and Secure Computing
- Vol. 21 (4) , 2720-2734
SwiftParade: Anti-Burst Multipath Validation
Path validation promises a necessary security add-on for future Internet architectures. It authenticates not only source identities but also the exact path where a packet forwards through. This offers users more flexibility and reliability in network services. Most existing solutions focus on single-path validation that pre-correlates a packet to a specific forwarding path. However, parallel transmissions in multipath routing tend to induce bursty traffic that is hardly validated in time by existing solutions. In this paper, we present SwiftParade as the first attempt toward anti-burst multipath validation. It proposes a composite validation technique that can simultaneously validate a group of packets likely from multiple different paths. This helps to amortize the validation overhead across packets of the entire group instead of imposing the validation overhead equally on every packet. To implement composite validation, SwiftParade further explores a noncommutative homomorphic asymmetric encryption scheme. We prove effectiveness and security of SwiftParade through theoretical analysis. We also conduct extensive experiments to evaluate SwiftParade performance. The results show that SwiftParade offers high efficiency and applicability to multipath validation with complex routing topologies. In comparison with the state-of-the-art multipath validation solution—Atlas, SwiftParade speeds up packet processing by 2.5× $\sim 8.3\times$ and increases communication throughput by 2.8× $\sim 10.2\times$ .
- 17 December 2021
- Published by Springer Nature
- p. 406-417
An Efficient Oracle for Counting Shortest Paths in Planar Graphs
- 17 December 2021
- Published by Springer Nature
- p. 406-417
An Efficient Oracle for Counting Shortest Paths in Planar Graphs
- Open Access
Multimodal Transportation with Ridesharing of Personal Vehicles
Many public transportation systems are unable to keep up with growing passenger demand as the population grows in urban areas. The slow or lack of improvements for public transportation pushes people to use private transportation modes, such as carpooling and ridesharing. However, the occupancy rate of personal vehicles has been dropping in many cities. In this paper, we describe a centralized transit system that integrates public transit and ridesharing, which matches drivers and transit riders such that the riders would result in shorter travel time using both transit and ridesharing. The optimization goal of the system is to assign as many riders to drivers as possible for ridesharing. We give an exact approach and approximation algorithms to achieve the optimization goal. As a case study, we conduct an extensive computational study to show the effectiveness of the transit system for different approximation algorithms, based on the real-world traffic data in Chicago City; the data sets include both public transit and ridesharing trip information. The experiment results show that our system is able to assign more than 60% of riders to drivers, leading to a substantial increase in occupancy rate of personal vehicles and reducing riders' travel time.
Open AccessMultimodal Transportation with Ridesharing of Personal Vehicles
Many public transportation systems are unable to keep up with growing passenger demand as the population grows in urban areas. The slow or lack of improvements for public transportation pushes people to use private transportation modes, such as carpooling and ridesharing. However, the occupancy rate of personal vehicles has been dropping in many cities. In this paper, we describe a centralized transit system that integrates public transit and ridesharing, which matches drivers and transit riders such that the riders would result in shorter travel time using both transit and ridesharing. The optimization goal of the system is to assign as many riders to drivers as possible for ridesharing. We give an exact approach and approximation algorithms to achieve the optimization goal. As a case study, we conduct an extensive computational study to show the effectiveness of the transit system for different approximation algorithms, based on the real-world traffic data in Chicago City; the data sets include both public transit and ridesharing trip information. The experiment results show that our system is able to assign more than 60% of riders to drivers, leading to a substantial increase in occupancy rate of personal vehicles and reducing riders' travel time.
- Open Access
Approximate Ridesharing of Personal Vehicles Problem
The ridesharing problem is that given a set of trips, each trip consists of an individual, a vehicle of the individual and some requirements, select a subset of trips and use the vehicles of selected trips to deliver all individuals to their destinations satisfying the requirements. Requirements of trips are specified by parameters including source, destination, vehicle capacity, preferred paths of a driver, detour distance and number of stops a driver is willing to make, and time constraints. We analyze the relations between the time complexity and parameters for two optimization problems: minimizing the number of selected vehicles and minimizing total travel distance of the vehicles. We consider the following conditions: (1) all trips have the same source or same destination, (2) no detour is allowed, (3) each participant has one preferred path, (4) no limit on the number of stops, and (5) all trips have the same departure and same arrival time. It is known that both minimization problems are NP-hard if one of Conditions (1), (2) and (3) is not satisfied. We prove that both problems are NP-hard and further show that it is NP-hard to approximate both problems within a constant factor if Conditions (4) or (5) is not satisfied. We give $\frac{K+2}{2}$-approximation algorithms for minimizing the number of selected vehicles when condition (4) is not satisfied, where $K$ is the largest capacity of all vehicles.Open AccessApproximate Ridesharing of Personal Vehicles Problem
The ridesharing problem is that given a set of trips, each trip consists of an individual, a vehicle of the individual and some requirements, select a subset of trips and use the vehicles of selected trips to deliver all individuals to their destinations satisfying the requirements. Requirements of trips are specified by parameters including source, destination, vehicle capacity, preferred paths of a driver, detour distance and number of stops a driver is willing to make, and time constraints. We analyze the relations between the time complexity and parameters for two optimization problems: minimizing the number of selected vehicles and minimizing total travel distance of the vehicles. We consider the following conditions: (1) all trips have the same source or same destination, (2) no detour is allowed, (3) each participant has one preferred path, (4) no limit on the number of stops, and (5) all trips have the same departure and same arrival time. It is known that both minimization problems are NP-hard if one of Conditions (1), (2) and (3) is not satisfied. We prove that both problems are NP-hard and further show that it is NP-hard to approximate both problems within a constant factor if Conditions (4) or (5) is not satisfied. We give $\frac{K+2}{2}$-approximation algorithms for minimizing the number of selected vehicles when condition (4) is not satisfied, where $K$ is the largest capacity of all vehicles.