QGQian-Ping Gu

Qian-Ping Gu

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Qian-Ping Gu has a total of 20 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • SwiftOracle: Orthogonality-Driven Private Multipath Validation

    by Yifei Pang, Anxiao He, Wenjie Hou, Yunyi Teng, Kai Bu, Qianping Gu, Kui Ren

    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.

  • Open Access

    Exact Set Packing in Multimodal Transportation with Ridesharing System for First/Last Mile

    by Qian-Ping Gu, Jiajian Leo Liang

    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 Access

    Algorithms for the Ridesharing with Profit Constraint Problem

    by Qian-Ping Gu, Jiajian Leo Liang

    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.

  • SwiftParade: Anti-Burst Multipath Validation

    by Anxiao He, Kai Bu, Jiongrui Huang, Yifei Pang, Qianping Gu, Kui Ren

    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$ .


  • Open Access

    Multimodal Transportation with Ridesharing of Personal Vehicles

    by Qian-Ping Gu, Jiajian Leo Liang

    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

    by Qian-Ping Gu, Jiajian Leo Liang, Guochuan Zhang

    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.