Author name cluster

Deshi Ye

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers

1 author row

AAAI Conference 2026 Conference Paper

Multi-Agent Corridor Reasoning for Multi-Agent Path Finding

Yiran Ni
Deshi Ye

The Multi-Agent Path Finding (MAPF) problem is a computationally challenging task that involves coordinating collision-free trajectories for multiple cooperative agents. Although existing methods address corridor symmetry, where agents encounter repeated bidirectional conflicts in constrained environments, they typically focus exclusively on pairwise agent interactions. Our observations reveal that such pairwise symmetry frequently arises when multiple agents traverse shared corridors, necessitating repeated applications of the corridor reasoning technology over extended durations. To overcome this limitation, we propose a multi-agent corridor reasoning (MAC) technology capable of resolving group-level corridor symmetry in a single optimization step. Our theoretical analysis demonstrates that this technology preserves the completeness and optimality guarantees of Conflict-Based Search (CBS). By integrating MAC technology with CBSH-RTC, we developed CBSH-MACRT, which significantly outperforms state-of-the-art algorithms (CBSH-RTC and CBSH with mutex propagation) on standardized MAPF benchmarks, improving success rates by 8–40% and cutting runtimes by 14–67%.

PDF Details DOI

TCS Journal 2021 Journal Article

Profit maximization for competitive social advertising

Qihao Shi
Can Wang
Deshi Ye
Jiawei Chen
Sheng Zhou
Yan Feng
Chun Chen
Yanhao Huang

In social advertising, the social platform host may run marketing campaigns for multiple competing clients simultaneously. In this case, each client comes up with a budget and an influence spread requirement. The host runs campaigns by allocating a set of seed nodes for each client. If the influence spread triggered by a seed set meets the requirement, the host can earn the budget from the corresponding client. In this paper, we study the problem of Profit Maximization, considering that different seeds incur different costs. Given all the clients' requirements met, we aim to find the optimal seed allocation with minimum cost. Under the competitive K-LT propagation model, we show the Profit Maximization problem is NP-hard and NP-hard to approximate with any factor. To find a feasible solution, we propose an effective algorithm that iteratively selects a candidate set and obtains an approximate allocation. The experimental results over a real-world dataset validate the effectiveness of the proposed methods.

Details DOI

TCS Journal 2018 Journal Article

Mechanism design for one-facility location game with obnoxious effects on a line

Lili Mei
Deshi Ye
Guochuan Zhang

In this paper, we introduce obnoxious effects into obnoxious facility location games on a line, where each agent i has a private location x i on a closed interval [ 0, 1 ] and one facility will be built on a location y in the interval according to the bids of all the agents. In addition, there are two thresholds d 1 and d 2 in the utility function of each agent, where 0 ≤ d 1 ≤ d 2 ≤ 1. Denote d ( y, x i ) = | y − x i | to be the distance between agent i and the facility on the location y. The utility function of agent i is 0 if d ( y, x i ) is at most d 1; 1 if d ( y, x i ) is at least d 2; otherwise a linear increasing function between 0 and 1. Each agent attempts to get the largest utility while the social welfare is to maximize the sum of all the agents' utilities. The classic obnoxious facility game [4, 11] is a special case of our problem when d 1 = 0 and d 2 = 1. In this work, we first study the hardness of approximate mechanism design on this generalized problem, which states that our problem cannot admit any deterministic strategy-proof mechanism with bounded approximation ratio if d 1 ≥ 1 2. Then we limit the thresholds to some ranges, both deterministic and randomized strategy-proof mechanisms are studied, and the approximation ratios vary with the specific values of d 1 and d 2.

Details DOI

TCS Journal 2016 Journal Article

Approximate composable truthful mechanism design

Deshi Ye
Guochuan Zhang

This paper aims to study techniques for designing truthful mechanisms for a combinatorial optimization problem that might require composition algorithms. We show that the composition algorithm A ∘ B is monotone if the algorithm A and the algorithm B are both monotone. We apply this technique to the two-dimensional orthogonal knapsack problem with provable constant approximation bounds, improving the previous non-constant results in [5]. Moreover, we show that the technique can also be applied to the heterogeneous multiple clusters scheduling problem, and a truthful mechanism with provable approximation bounds was presented.

Details DOI

I&C Journal 2016 Journal Article

Approximate strip packing: Revisited

Xin Han
Kazuo Iwama
Deshi Ye
Guochuan Zhang

In this paper we establish an algorithmic framework between bin packing and strip packing, with which strip packing can be very well approximated by applying some bin packing algorithms. More precisely we obtain the following results: (1) Any off-line bin packing algorithm can be applied to strip packing maintaining almost the same asymptotic worst-case ratio. (2) A class of Harmonic-based algorithms for bin packing, such as Refined Harmonic, Modified Harmonic, Harmonic++, can be applied to online strip packing. In particular, we show that online strip packing admits an upper bound of 1. 58889 + ϵ on the asymptotic competitive ratio, for any arbitrarily small ϵ > 0. This significantly improves the previously best bound of 1. 6910 and affirmatively answers an open question posed by Csirik and Woeginger (1997). Moreover, the time complexity mainly depends on a sorting procedure and the bin packing algorithms employed.

Details DOI

AAMAS Conference 2016 Conference Paper

Strategy-Proof Mechanism Design for Facility Location Games: Revisited (Extended Abstract)

Lili Mei
Minming Li
Deshi Ye
Guochuan Zhang

In facility location games, one aims at designing a mechanism to decide the facility location based on the addresses reported by all agents. In the standard facility location game, each agent wants to minimize the distance from the facility, while in the obnoxious facility game, each agent prefers to be as far away from the facility as possible. In this paper we revisit the two games on a line network by finely defining more reasonable agent cost (utility) functions in terms of their satisfaction degree with respect to the facility location. Namely, a happiness factor within [0, 1] is introduced to measure the difference between the best facility location for an agent and the one given by the mechanism. Agents aim at a largest possible happiness factor while the social satisfaction is to maximize the total factors. For the standard facility location game, we observe that the median mechanism [4] is of 3/2-approximation. We then devise a 5/4-approximation group strategy-proof mechanism. For the obnoxious facility game, we show the majority mechanism [1] is best possible with approximation ratio of two.

PDF

TCS Journal 2015 Journal Article

An asymptotic competitive scheme for online bin packing

Lin Chen
Deshi Ye
Guochuan Zhang

In the online bin packing problem, a list of items with integral sizes between 1 to B arrive one by one. Each item must be irrevocably assigned into a bin of capacity B upon its arrival without any information on the subsequent items, and the goal is to minimize the number of used bins. In this paper, we deal with online bin packing from a new sight. We present an asymptotic competitive scheme, i. e. , for any ϵ > 0, the asymptotic competitive ratio is at most ρ ⁎ + ϵ, where ρ ⁎ is the smallest possible asymptotic competitive ratio among all online algorithms. Apart from the technical results, the analysis to bridge the online and the off-line approaches might be of particular interests.

Details DOI

TCS Journal 2014 Journal Article

Online algorithms for 1-space bounded 2-dimensional bin packing and square packing

Yong Zhang
Francis Y.L. Chin
Hing-Fung Ting
Xin Han
Chung Keung Poon
Yung H. Tsin
Deshi Ye

In this paper, we study 1-space bounded 2-dimensional bin packing and square packing. A sequence of rectangular items (square items) arrive one by one, each item must be packed into a square bin of unit size on its arrival without any information about future items. When packing items, 90°-rotation is allowed. 1-space bounded means there is only one “active” bin. If the “active” bin cannot accommodate the coming item, it will be closed and a new bin will be opened. The objective is to minimize the total number of bins used for packing all items in the sequence. Our contributions are as follows: For 1-space bounded 2-dimensional bin packing, we propose an online packing algorithm with a tight competitive ratio of 5. 06. A lower bound of 3. 17 on the competitive ratio is proven. Moreover, we study 1-space bounded square packing, where each item is a square with side length no more than 1. A 4. 3-competitive algorithm is achieved, and a lower bound of 2. 94 on the competitive ratio is given. All these bounds surpass the previously best known results.

Details DOI

TCS Journal 2011 Journal Article

Online multiple-strip packing

Deshi Ye
Xin Han
Guochuan Zhang

We study an online multiple-strip packing problem, whose goal is to pack the given rectangles into m vertical strips of unit width such that the maximum height used among the strips is minimized. Rectangles arrive one by one. The decision of delivering the rectangles to a strip as well as packing them into the strip must be done immediately and irrevocably without any information on the next rectangles. Both randomized and deterministic online algorithms are investigated, all of which are guaranteed a constant competitive ratio.

Details DOI

TCS Journal 2010 Journal Article

Deterministic on-line call control in cellular networks

Deshi Ye
Xin Han
Guochuan Zhang

We study an on-line call control problem in cellular networks that are based on the Frequency Division Multiplexing (FDM) technology. In such networks, interference may occur when the same frequency is assigned to two different calls emanating from the same cell or its neighboring cells. The number of frequencies supporting the networks is limited. The goal is to maximize the number of calls served without causing any interference. We focus on the case that the number of frequencies is sufficiently large and the calls stay forever. We give a deterministic on-line algorithm with asymptotic competitive ratio of 2. 5 and show a general lower bound of 2. For the special case of linear cellular networks, we achieve a best possible deterministic on-line algorithm with asymptotic competitive ratio of 3/2.

Details DOI

TCS Journal 2008 Journal Article

Online bin packing with arbitrary release times

Yongqiang Shi
Deshi Ye

We study a new variant of the online bin-packing problem, in which each item a i is associated with a size a i and also a release time r i so that it must be placed at least r i above the bottom of a bin. Items arrive in turn and must be assigned without any knowledge of subsequent items. The goal is to pack all items into unit-size bins using the minimum number of bins. We study the problem with all items have equal size. First, we show that the ANY FIT algorithm cannot be approximated within any constant. Then we present a best possible online algorithm with asymptotic competitive ratio of two.

Details DOI

TCS Journal 2007 Journal Article

On-line scheduling mesh jobs with dependencies

Deshi Ye
Guochuan Zhang

We study an on-line problem of scheduling parallel jobs on two-dimensional meshes. Parallel jobs arrive dynamically according to the dependencies between them, which are unknown before the jobs appear. Each job may need more than one processor simultaneously and is required to be scheduled on a submesh of the processors which are located on a two-dimensional mesh, i. e. , a job must be scheduled on a rectangle of given dimensions. The objective is to minimize the maximum completion time (makespan). We deal with a UET job system, in which all job processing times are equal. We show a lower bound of 3. 859 and present a 5. 25-competitive algorithm. It significantly improves a previous lower bound of 3. 25 and a previous upper bound of 46/7. We consider also the rotated two-dimensional mesh, in which the parallel jobs can be rotated and the rotation of all the jobs is feasible. A lower bound of 3. 535 is proven and an on-line algorithm with competitive ratio of at most 4. 25 is derived.

Details DOI