Xiaodong Hu

TCS Journal 2020 Journal Article

The efficiency of Nash equilibria in the load balancing game with a randomizing scheduler

• Xujin Chen
• Xiaodong Hu
• Chenhao Wang
• Xiaoying Wu

We study the efficiency of Nash equilibria for the load balancing game with a randomizing scheduler. In the game, we are given a set of facilities and a set of players along with a scheduler, where each facility is associated with a linear cost function, and the players are randomly ordered by the scheduler. Each player chooses exactly one of these facilities to fulfill his task, which incurs to him a cost depending on not only the cost function of the facility he chooses and the players who choose the same facility (as in a usual load balancing game), but also his uncertain position in the uniform random ordering. From an individual perspective, each player tries to choose a facility for optimizing his own objective that is determined by a certain decision-making principle. From a system perspective, it is desirable to minimize the maximum cost among all players, which is a commonly used criterion for load balancing. We estimate the price of anarchy and price of stability for this class of load balancing games under uncertainty, provided all players follow one of the four decision-making principles, namely the bottom-out, win-or-go-home, minimum-expected-cost, and minimax-regret principles. Our results show that the efficiency loss of Nash equilibria in these decentralized environments heavily rely on player's attitude toward the uncertainty.

IJCAI Conference 2017 Conference Paper

Efficient Mechanism Design for Online Scheduling (Extended Abstract)

• Xujin Chen
• Xiaodong Hu
• Tie-Yan Liu
• Weidong Ma
• Tao Qin
• Pingzhong Tang
• Changjun Wang
• Bo Zheng

This work concerns the mechanism design for online scheduling in a strategic setting. In this setting, each job is owned by a self-interested agent who may misreport the release time, deadline, length, and value of her job, while we need to determine not only the schedule of the jobs, but also the payment of each agent. We focus on the design of incentive compatible (IC) mechanisms, and study the maximization of social welfare (i. e. , the aggregated value of completed jobs) by competitive analysis. We first derive two lower bounds on the competitive ratio of any deterministic IC mechanism to characterize the landscape of our research: one bound is 5, which holds for equal-length jobs; the other bound is $\frac{\kappa}{\ln\kappa}+1-o(1)$, which holds for unequal-length jobs, where $\kappa$ is the maximum ratio between lengths of any two jobs. We then propose a deterministic IC mechanism and show that such a simple mechanism works very well for two models: (1) In the preemption-restart model, the mechanism can achieve the optimal competitive ratio of 5 for equal-length jobs and a near optimal ratio of $(\frac{1}{(1-\epsilon)^2}+o(1)) \frac{\kappa}{\ln\kappa}$ for unequal-length jobs, where $0<\epsilon<1$ is a small constant; (2) In the preemption-resume model, the mechanism can achieve the optimal competitive ratio of 5 for equal-length jobs and a near optimal competitive ratio (within factor 2) for unequal-length jobs.

I&C Journal 2017 Journal Article

Finding connected k -subgraphs with high density

• Xujin Chen
• Xiaodong Hu
• Changjun Wang

Given an edge-weighted connected graph G on n vertices and a positive integer k ≤ n, a subgraph of G on k vertices is called a k-subgraph in G. We design combinatorial approximation algorithms for finding a connected k-subgraph in G such that its weighted density is at least a factor Ω ( max ⁡ { 1 / k, k 2 / n 2 } ) of the maximum weighted density among all k-subgraph in G (which are not necessarily connected), where max ⁡ { 1 / k, k 2 / n 2 } ≥ n − 2 / 3 implies an O ( n 2 / 3 ) -approximation ratio. We obtain improved O ( n 2 / 5 ) -approximation for unit weights. These particularly provide the first non-trivial approximations for the heaviest/densest connected k-subgraph problem on general graphs. We also give O ( n log ⁡ n ) -approximation for the problem on general weighted interval graphs.

TCS Journal 2016 Journal Article

Approximation for the minimum cost doubly resolving set problem

• Xujin Chen
• Xiaodong Hu
• Changjun Wang

Locating source of diffusion in networks is crucial for controlling and preventing epidemic risks. It has been studied under various probabilistic models. In this paper, we study source location from a deterministic point of view by modeling it as the minimum cost doubly resolving set (DRS) problem, which is a strengthening of the well-known metric dimension problem. Let G be an undirected graph on n vertices, where each vertex has a nonnegative cost. A vertex subset S of G is a doubly resolving set (DRS) of G if for every pair of vertices u, v in G, there exist x, y ∈ S such that the difference of distances (in terms of number of edges) between u and x, y is not equal to the difference of distances between v and x, y. The minimum cost DRS problem consists of finding a DRS in G with minimum total cost. We establish Θ ( ln ⁡ n ) approximability of the minimum DRS problem on general graphs for both weighted and unweighted versions. This provides the first explicit lower and upper bounds on approximation for the minimum (cost) DRS, which are nearly tight. Moreover, we design the first known strongly polynomial time exact algorithms for the minimum cost DRS problem on general wheels and trees with additional constant k ≥ 0 edges.

JAIR Journal 2016 Journal Article

Efficient Mechanism Design for Online Scheduling

• Xujin Chen
• Xiaodong Hu
• Tie-Yan Liu
• Weidong Ma
• Tao Qin
• Pingzhong Tang
• Changjun Wang
• Bo Zheng

This paper concerns the mechanism design for online scheduling in a strategic setting. In this setting, each job is owned by a self-interested agent who may misreport the release time, deadline, length, and value of her job, while we need to determine not only the schedule of the jobs, but also the payment of each agent. We focus on the design of incentive compatible (IC) mechanisms, and study the maximization of social welfare (i.e., the aggregated value of completed jobs) by competitive analysis. We first derive two lower bounds on the competitive ratio of any deterministic IC mechanism to characterize the landscape of our research. We then propose a deterministic IC mechanism and show that such a simple mechanism works very well for both the preemption-restart model and the preemption-resume model. We show the mechanism can achieve the optimal competitive ratio of 5 for equal-length jobs and a near optimal competitive ratio (within a constant factor) for unequal-length jobs.

IJCAI Conference 2015 Conference Paper

Selling Reserved Instances in Cloud Computing

• Changjun Wang
• Weidong Ma
• Tao Qin
• Xujin Chen
• Xiaodong Hu
• Tie-Yan Liu

In this paper, we study the problem of designing new mechanisms for selling reserved instances (also referred to as virtual machines) in cloud computing. Unlike the practice in today’s clouds in which users only have a few predefined options to reserve instances (i. e. , either 1-year reservation or 3-year reservation), we allow users to reserve resources for any length and from any time point in the future. Our goal is to maximize the social welfare. We propose two mechanisms, one for the case where all the jobs are tight (their lengths are exactly their reservation time intervals), and the other for the more general case where jobs are delayable and have some flexibility on their reservations. Both of the mechanisms are prompt in the sense that the acceptance and the payment for a job is determined at the very moment of its arrival. We use competitive analysis to evaluate the performance of our mechanisms, and show that both of the mechanisms have a competitive ratio of O(ln(kT)) under some mild assumption, where k (res. T) is the maximum ratio between per-instance-hour valuation (res. length) of any two jobs. We then prove that no algorithm can achieve a competitive ratio better than ln(2kT) under the same assumption. Therefore, our mechanisms are optimal within a constant factor.

TCS Journal 2013 Journal Article

Reducing price of anarchy of selfish task allocation with more selfishness

• Xujin Chen
• Xiaodong Hu
• Weidong Ma
• Changjun Wang

In this paper we consider the task allocation problem from a new game theoretic perspective. We assume that tasks and machines are both controlled by selfish agents with two distinct objectives, which stands in contrast to the passive role of machines in the traditional model of selfish task allocation. To characterize the outcome of this new game where two classes of players interact, we introduce the concept of dual equilibrium. We prove that the price of anarchy with respect to dual equilibria is 1. 4, which is considerably smaller than the counterpart 2 in the traditional model. Our study shows that activating more freedom and selfishness in a game may bring about a better global outcome.

TCS Journal 2012 Journal Article

Pairwise cooperations in selfish ring routing for minimax linear latency

• Xujin Chen
• Xiaodong Hu
• Weidong Ma

This paper studies the selfish routing game in ring networks with a load-dependent linear latency on each link. We adopt the asymmetric atomic routing model. Each player selfishly chooses a route to connect his source-destination pair, aiming at the lowest latency of his route, while the system objective is to minimize the maximum latency among all routes of players. The effectiveness of these routing games is often measured by the price of anarchy (PoA), the worst-case ratio between the maximum latencies in a Nash equilibrium (NE) and in a system optimum, where NE refers to a “stable state” among all players, from which no player has the incentive to deviate unilaterally. In classical setting, no cooperation is allowed and 16 stands as the current best upper bound on the PoA of such selfish ring routing. In this paper we show that the PoA is at most 10. 16 provided cooperations within pairs of players are allowed, where any two players could change their routes simultaneously if neither would experience a longer latency and at least one would experience a shorter latency.

TCS Journal 2011 Journal Article

Deterministic risk control for cost-effective network connections

• Eduardo Álvarez-Miranda
• Xujin Chen
• Jie Hu
• Xiaodong Hu
• Alfredo Candia-Véjar

This paper considers the minimum connection problem in networks with uncertain data. In such a network it is assumed that one can establish a link e by paying a cost c e in a given interval [ c e −, c e + ] while taking a risk ( c e + − c e ) / ( c e + − c e − ) of link failure. We develop polynomial time algorithms for minimum cost network connection with paths or spanning trees under risk-sum constraints.

TCS Journal 2011 Journal Article

Preface

• Ding-Zhu Du
• Xiaodong Hu
• Panos M. Pardalos

TCS Journal 2007 Journal Article

Algorithms for minimum m -connected k -tuple dominating set problem

• Weiping Shang
• Pengjun Wan
• Frances Yao
• Xiaodong Hu

In wireless sensor networks, a virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem and perform some other tasks such as area monitoring. Previous work in this area has mainly focused on how to set up a small virtual backbone for high efficiency, which is modelled as the minimum Connected Dominating Set (CDS) problem. In this paper we consider how to establish a small virtual backbone to balance efficiency and fault tolerance. This problem can be formalized as the minimum m -connected k -tuple dominating set problem, which is a general version of minimum CDS problem with m = 1 and k = 1. We propose three centralized algorithms with small approximation ratios for small m and improve the current best results for small k.

TCS Journal 2001 Journal Article

Wire segmenting for buffer insertion based on RSTP-MSP

• Bing Lu
• Jun Gu
• Xiaodong Hu
• Eugene Shragowitz

This paper presents an approximation algorithm for simultaneously constructing a rectilinear Steiner tree and buffer insertion points into the tree. The objective of the algorithm is to divide each wire into multiple smaller segments and minimize the number of the buffer insertion points (Steiner points) which are only located at the end of each segment. We show that (a) the Steiner ratio is 1 3, that is, the rectilinear minimum spanning tree yields a polynomial-time approximation with a performance ratio exactly 3; (b) there exists a polynomial-time approximation with a performance ratio 2.