XGXiangyu Guo

Xiangyu Guo

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

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Xiangyu Guo has a total of 29 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Minimizing the Maximum Flow Time in the Online Food Delivery Problem

    by Xiangyu Guo, Shi Li, Kelin Luo, Yuhao Zhang


  • Open Access

    A Hierarchical Grouping Algorithm for the Multi-Vehicle Dial-a-Ride Problem

    by Kelin Luo, Alexandre M. Florio, Syamantak Das, Xiangyu Guo

    Ride-sharing is an essential aspect of modern urban mobility. In this paper, we consider a classical problem in ride-sharing - the Multi-Vehicle Dial-a-Ride Problem (Multi-Vehicle DaRP). Given a fleet of vehicles with a fixed capacity stationed at various locations and a set of ride requests specified by origins and destinations, the goal is to serve all requests such that no vehicle is assigned more passengers than its capacity at any point in its trip. We give an algorithm HGR, which is the first non-trivial approximation algorithm for the Multi-Vehicle DaRP. The main technical contribution is to reduce Multi-Vehicle DaRP to a certain capacitated partitioning problem, which we solve using a novel hierarchical grouping algorithm. Experimental results show that the vehicle routes produced by our algorithm not only exhibit less total travel distance compared to state-of-the-art baselines, but also enjoy a small in-transit latency, which crucially relates to each individual rider's traveling time. This suggests that HGR enhances rider experience while being energy-efficient.


  • Open Access

    The online food delivery problem on stars

    by Xiangyu Guo, Kelin Luo, Zhihao Gavin Tang, Yuhao Zhang


  • Open Access

    Finding Optimal Tangent Points for Reducing Distortions of Hard-label Attacks

    by Chen Ma, Xiangyu Guo, Li Chen, Jun-Hai Yong, Yisen Wang

    One major problem in black-box adversarial attacks is the high query complexity in the hard-label attack setting, where only the top-1 predicted label is available. In this paper, we propose a novel geometric-based approach called Tangent Attack (TA), which identifies an optimal tangent point of a virtual hemisphere located on the decision boundary to reduce the distortion of the attack. Assuming the decision boundary is locally flat, we theoretically prove that the minimum $\ell_2$ distortion can be obtained by reaching the decision boundary along the tangent line passing through such tangent point in each iteration. To improve the robustness of our method, we further propose a generalized method which replaces the hemisphere with a semi-ellipsoid to adapt to curved decision boundaries. Our approach is free of pre-training. Extensive experiments conducted on the ImageNet and CIFAR-10 datasets demonstrate that our approach can consume only a small number of queries to achieve the low-magnitude distortion. The implementation source code is released online at https://github.com/machanic/TangentAttack.

  • On Approximating Degree-Bounded Network Design Problems

    by Xiangyu Guo, Guy Kortsarz, Bundit Laekhanukit, Shi Li, Daniel Vaz, Jiayi Xian


  • Open Access

    Online Food Delivery to Minimize Maximum Flow Time

    by Xiangyu Guo, Shi Li, Kelin Luo, Yuhao Zhang

    We study a common delivery problem encountered in nowadays online food-ordering platforms: Customers order dishes online, and the restaurant delivers the food after receiving the order. Specifically, we study a problem where $k$ vehicles of capacity $c$ are serving a set of requests ordering food from one restaurant. After a request arrives, it can be served by a vehicle moving from the restaurant to its delivery location. We are interested in serving all requests while minimizing the maximum flow-time, i.e., the maximum time length a customer waits to receive his/her food after submitting the order. We show that the problem is hard in both offline and online settings: There is a hardness of approximation of $\Omega(n)$ for the offline problem, and a lower bound of $\Omega(n)$ on the competitive ratio of any online algorithm, where $n$ is number of points in the metric. Our main result is an $O(1)$-competitive online algorithm for the uncapaciated (i.e, $c = \infty$) food delivery problem on tree metrics. Then we consider the speed-augmentation model. We develop an exponential time $(1+\epsilon)$-speeding $O(1/\epsilon)$-competitive algorithm for any $\epsilon > 0$. A polynomial time algorithm can be obtained with a speeding factor of $\alpha_{TSP}+ \epsilon$ or $\alpha_{CVRP}+ \epsilon$, depending on whether the problem is uncapacitated. Here $\alpha_{TSP}$ and $\alpha_{CVRP}$ are the best approximation factors for the traveling salesman (TSP) and capacitated vehicle routing (CVRP) problems respectively. We complement the results with some negative ones.

  • A harmony search algorithm to operation sequencing optimization in process planning

    by Zhichao Wang, Lin Wang, Yongjian Zhang, Xiangyu Guo, Song Xu

    Aiming at the problem that the sequence of operation in the processing of complex parts directly affects the processing cost, an improved harmony search algorithm with the lowest processing cost as the optimization goal is proposed. The constraint relationship between the operation is represented by a process priority diagram. Then use the topological sorting method on the graph to generate the initial sequence as the initial harmony of the harmony memory. The crossover operator is introduced to ensure the feasibility of the new generation of harmony, and the local search method is used to change the machine and tool resources available for the operation to avoid falling into the local optimum. Experimental results show that the improved harmony search method can effectively solve the cost optimization problem of step sequencing.


  • Open Access

    Robust high dimensional expectation maximization algorithm via trimmed hard thresholding

    by Di Wang, Xiangyu Guo, Shi Li, Jinhui Xu


  • Open Access

    Robust High Dimensional Expectation Maximization Algorithm via Trimmed Hard Thresholding

    by Di Wang, Xiangyu Guo, Shi Li, Jinhui Xu

    In this paper, we study the problem of estimating latent variable models with arbitrarily corrupted samples in high dimensional space ({\em i.e.,} $d\gg n$) where the underlying parameter is assumed to be sparse. Specifically, we propose a method called Trimmed (Gradient) Expectation Maximization which adds a trimming gradients step and a hard thresholding step to the Expectation step (E-step) and the Maximization step (M-step), respectively. We show that under some mild assumptions and with an appropriate initialization, the algorithm is corruption-proofing and converges to the (near) optimal statistical rate geometrically when the fraction of the corrupted samples $\epsilon$ is bounded by $ \tilde{O}(\frac{1}{\sqrt{n}})$. Moreover, we apply our general framework to three canonical models: mixture of Gaussians, mixture of regressions and linear regression with missing covariates. Our theory is supported by thorough numerical results.

  • Open Access

    Estimating Stochastic Linear Combination of Non-linear Regressions Efficiently and Scalably

    by Di Wang, Xiangyu Guo, Chaowen Guan, Shi Li, Jinhui Xu

    Recently, many machine learning and statistical models such as non-linear regressions, the Single Index, Multi-index, Varying Coefficient Index Models and Two-layer Neural Networks can be reduced to or be seen as a special case of a new model which is called the \textit{Stochastic Linear Combination of Non-linear Regressions} model. However, due to the high non-convexity of the problem, there is no previous work study how to estimate the model. In this paper, we provide the first study on how to estimate the model efficiently and scalably. Specifically, we first show that with some mild assumptions, if the variate vector $x$ is multivariate Gaussian, then there is an algorithm whose output vectors have $\ell_2$-norm estimation errors of $O(\sqrt{\frac{p}{n}})$ with high probability, where $p$ is the dimension of $x$ and $n$ is the number of samples. The key idea of the proof is based on an observation motived by the Stein's lemma. Then we extend our result to the case where $x$ is bounded and sub-Gaussian using the zero-bias transformation, which could be seen as a generalization of the classic Stein's lemma. We also show that with some additional assumptions there is an algorithm whose output vectors have $\ell_\infty$-norm estimation errors of $O(\frac{1}{\sqrt{p}}+\sqrt{\frac{p}{n}})$ with high probability. We also provide a concrete example to show that there exists some link function which satisfies the previous assumptions. Finally, for both Gaussian and sub-Gaussian cases we propose a faster sub-sampling based algorithm and show that when the sub-sample sizes are large enough then the estimation errors will not be sacrificed by too much. Experiments for both cases support our theoretical results. To the best of our knowledge, this is the first work that studies and provides theoretical guarantees for the stochastic linear combination of non-linear regressions model.