Author name cluster

Xiaoming Sun

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.

25 papers

1 author row

EAAI Journal 2025 Journal Article

A single-valued neutrosophic affinity propagation approach for engineering geological zoning of open-pit mine slopes

Jibo Qin
Xiaoming Sun
Shigui Du
Jun Ye

Engineering geological zoning is an important foundation for assessing the stability of open-pit mine (OPM) slopes. Because of the complexity and uncertainty of geological conditions, this work brings great challenges to mining engineers and researchers. This paper presents a single-valued neutrosophic affinity propagation (SVNS-AP) approach for engineering geological zoning of OPM slopes. The approach utilizes the concept of a single-valued neutrosophic set (SVNS) to express the inconsistent and indeterminate information present in the influencing factors of engineering geological conditions through truth, indeterminate and falsity membership functions. Then, the similarity measure of SVNS is integrated into the affinity propagation (AP) algorithm to calculate the degree of similarity between the data points. Finally, the modified silhouette index is used to evaluate the clustering results and decide the optimal number of clusters. The practical application results of the engineering geological zoning of Lanping lead-zinc OPM demonstrate that the SVNS-AP method is an effective way for engineering geological zoning of OPM slopes in the uncertain environment. Clustering results based on datasets in the literature and the UC Irvine Machine Learning Repository show that the proposed method can be used as a general clustering algorithm.

TCS Journal 2025 Journal Article

Efficient deterministic algorithms for maximizing symmetric submodular functions

Zongqi Wan
Jialin Zhang
Xiaoming Sun
Zhijie Zhang

Symmetric submodular maximization is an important class of combinatorial optimization problems, including MAX-CUT on graphs and hyper-graphs. The state-of-the-art algorithm for the problem over general constraints has an approximation ratio of 0. 432 [16]. The algorithm applies the canonical continuous greedy technique that involves a sampling process. It, therefore, suffers from high query complexity and is inherently randomized. In this paper, we present several efficient deterministic algorithms for maximizing a symmetric submodular function under various constraints. Specifically, for the cardinality constraint, we design a deterministic algorithm that attains a 0. 432 ratio and uses O ( k n ) queries. Previously, the best deterministic algorithm attains a 0. 385 − ϵ ratio and uses O ( k n ( 10 9 ϵ ) 20 9 ϵ − 1 ) queries [12]. For the matroid constraint, we design a deterministic algorithm that attains a 1 / 3 − ϵ ratio and uses O ( k n log ⁡ ϵ − 1 ) queries. Previously, the best deterministic algorithm can also attain 1 / 3 − ϵ ratio but it uses much larger O ( ϵ − 1 n 4 ) queries [24]. For the packing constraints with a large width, we design a deterministic algorithm that attains a 0. 432 − ϵ ratio and uses O ( n 2 ) queries. To the best of our knowledge, there is no deterministic algorithm for the constraint previously. The last algorithm can be adapted to attain a 0. 432 ratio for single knapsack constraint using O ( n 4 ) queries. Previously, the best deterministic algorithm attains a 0. 316 − ϵ ratio and uses O ˜ ( n 3 ) queries [2].

I&C Journal 2025 Journal Article

Exact counting of subtrees with diameter no more than d in trees: A generating function approach

Yu Yang
Bang-Bang Jin
Xiaoming Sun
Xiao-Dong Zhang
Bo Li
Kai Zhao
Hua Wang

Network motifs, regarded as fundamental building blocks, offer crucial insights into the structure and function of complex networks, with broad applications across disciplines including sociology, computer science, bioinformatics, chemoinformatics, and pharmaceutics. However, the identification of network motifs remains a significant and computationally challenging problem. Among various motifs, subtree enumeration has garnered substantial attention in recent years, particularly due to its relevance in network science and bioinformatics. For an n-vertex tree T, by introducing novel generating functions with ( d + 2 ) variables, we propose an innovative algorithm for the exact enumeration of T's subtrees rooted at fixed vertex v, where the distance between v and the farthest leaf is k = 0, 1, …, d, and the distance between any two leaves is no more than d. Building on this algorithm, we develop novel recursive algorithms for exact enumerating various diameter no more than d subtrees (abbreviated as DNMT-d subtrees) of T. As applications, we apply these algorithms to derive the number of DNMT-d subtrees in a full binary tree B h with h ≥ 2 levels, and briefly discuss the density of DNMT-d subtrees in general trees. Our research generalizes the work of Frank Ruskey on Listing and Counting Subtrees of a Tree in 1981 and makes it a special case of our study where d equals the diameter of the tree T. Moreover, the proposed O ( d n 2 ) algorithms introduce new approaches for enumerating subtrees under diameter constraints and lay the groundwork for counting diameter-constrained subgraphs (motifs) in complex networks.

TCS Journal 2024 Journal Article

Improved deterministic algorithms for non-monotone submodular maximization

Xiaoming Sun
Jialin Zhang
Shuo Zhang
Zhijie Zhang

Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithms have been proposed for this problem. However, most of the state-of-the-art algorithms are randomized. There remain non-negligible gaps with respect to approximation ratios between deterministic and randomized algorithms in submodular maximization. In this paper, we propose deterministic algorithms with improved approximation ratios for non-monotone submodular maximization. Specifically, for the matroid constraint, we provide a deterministic 0. 283 − o ( 1 ) approximation algorithm, while the previous best deterministic algorithm only achieves a 1/4 approximation ratio. For the knapsack constraint, we provide a deterministic 1/4 approximation algorithm, while the previous best deterministic algorithm only achieves a 1/6 approximation ratio. For the linear packing constraints with large widths, we provide a deterministic 1 / 6 − ϵ approximation algorithm. To the best of our knowledge, there is currently no deterministic approximation algorithm for the constraints.

AAAI Conference 2023 Conference Paper

Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets

Zongqi Wan
Zhijie Zhang
Tongyang Li
Jialin Zhang
Xiaoming Sun

Multi-arm bandit (MAB) and stochastic linear bandit (SLB) are important models in reinforcement learning, and it is well-known that classical algorithms for bandits with time horizon T suffer from the regret of at least the square root of T. In this paper, we study MAB and SLB with quantum reward oracles and propose quantum algorithms for both models with the order of the polylog T regrets, exponentially improving the dependence in terms of T. To the best of our knowledge, this is the first provable quantum speedup for regrets of bandit problems and in general exploitation in reinforcement learning. Compared to previous literature on quantum exploration algorithms for MAB and reinforcement learning, our quantum input model is simpler and only assumes quantum oracles for each individual arm.

PDF Details DOI

IJCAI Conference 2022 Conference Paper

Bounded Memory Adversarial Bandits with Composite Anonymous Delayed Feedback

Zongqi Wan
Xiaoming Sun
Jialin Zhang

We study the adversarial bandit problem with composite anonymous delayed feedback. In this setting, losses of an action are split into d components, spreading over consecutive rounds after the action is chosen. And in each round, the algorithm observes the aggregation of losses that come from the latest d rounds. Previous works focus on oblivious adversarial setting, while we investigate the harder nonoblivious setting. We show nonoblivious setting incurs Omega(T) pseudo regret even when the loss sequence is bounded memory. However, we propose a wrapper algorithm which enjoys o(T) policy regret on many adversarial bandit problems with the assumption that the loss sequence is bounded memory. Especially, for K armed bandit and bandit convex optimization, our policy regret bound is in the order of T to the two third. We also prove a matching lower bound for K armed bandit. Our lower bound works even when the loss sequence is oblivious but the delay is nonoblivious. It answers the open problem proposed in [Wang, Wang, Huang 2021], showing that nonoblivious delay is enough to incur the regret in the order of T to the two third.

PDF Details DOI

I&C Journal 2022 Journal Article

Higher order monotonicity and submodularity of influence in social networks: From local to global

Wei Chen
Qiang Li
Xiaohan Shan
Xiaoming Sun
Jialin Zhang

Kempe, Kleinberg and Tardos (KKT) proposed the following conjecture about the general threshold model in social networks: local monotonicity and submodularity implies global monotonicity and submodularity. That is, if the threshold function of every node is monotone and submodular, then the spread function is monotone and submodular. The correctness of this conjecture has been proved by Mossel and Roch. In this paper, we first provide the concept AD-k (Alternating Difference-k) as a generalization of monotonicity and submodularity. Specifically, a set function f is called AD-k if all the ℓ-th order differences of f on all inputs have sign ( − 1 ) ℓ + 1 for every ℓ ≤ k. We propose a refined version of KKT's conjecture: in the general threshold model, local AD-k implies global AD-k. We prove the correctness of our conjecture when the social graph is a DAG. Furthermore, we affirm our conjecture on general social graphs when k = ∞.

AAAI Conference 2022 Conference Paper

Online Influence Maximization with Node-Level Feedback Using Standard Offline Oracles

Zhijie Zhang
Wei Chen
Xiaoming Sun
Jialin Zhang

We study the online influence maximization (OIM) problem in social networks, where in multiple rounds the learner repeatedly chooses seed nodes to generate cascades, observes the cascade feedback, and gradually learns the best seeds that generate the largest cascade. We focus on two major challenges in this paper. First, we work with node-level feedback instead of edge-level feedback. The edge-level feedback reveals all edges that pass through information in a cascade, whereas the node-level feedback only reveals the activated nodes with timestamps. The node-level feedback is arguably more realistic since in practice it is relatively easy to observe who is influenced but very difficult to observe from which relationship (edge) the influence comes. Second, we use standard offline oracles instead of offline pair-oracles. To compute a good seed set for the next round, an offline pair-oracle finds the best seed set and the best parameters within the confidence region simultaneously, and such an oracle is difficult to compute due to the combinatorial core of the OIM problem. So we focus on how to use the standard offline influence maximization oracle which finds the best seed set given the edge parameters as input. In this paper, we resolve these challenges for the famous independent cascade (IC) diffusion model. The past research only achieves edge-level feedback, while we present the first e O( √ T)-regret algorithm for the node-level feedback. For the first challenge above, we apply a novel adaptation of the maximum likelihood estimation (MLE) approach to learn the graph parameters and its confidence region (a confidence ellipsoid). For the second challenge, we adjust the update procedure to dissect the confidence ellipsoid into confidence intervals on each parameter, so that the standard offline influence maximization oracle is enough.

TCS Journal 2020 Journal Article

Coreness of cooperative games with truncated submodular profit functions

Wei Chen
Xiaohan Shan
Xiaoming Sun
Jialin Zhang

Coreness represents solution concepts related to core in cooperative games, which captures the stability of players. Motivated by the scale effect in social networks, economics and other scenario, we study the coreness of cooperative game with truncated submodular profit functions. Specifically, the profit function f ( ⋅ ) is defined by a truncation of a submodular function σ ( ⋅ ): f ( ⋅ ) = σ ( ⋅ ) if σ ( ⋅ ) ≥ η and f ( ⋅ ) = 0 otherwise, where η is a given threshold. In this paper, we study the core and three core-related concepts of truncated submodular profit cooperative game. We first prove that whether core is empty can be decided in polynomial time and an allocation in core also can be found in polynomial time when core is not empty. When core is empty, we show hardness results and approximation algorithms for computing other core-related concepts including relative least-core value, absolute least-core value and least average dissatisfaction value.

TCS Journal 2020 Journal Article

On the modulo degree complexity of Boolean functions

Qian Li
Xiaoming Sun

For each integer m ≥ 2, every Boolean function f can be expressed as a unique multilinear polynomial modulo m, and the degree of this multilinear polynomial is called its modulo m degree. In this paper we investigate the modulo degree complexity of total Boolean functions initiated by Parikshit Gopalan et al. [9], in which they asked the following question: whether the degree complexity of a Boolean function is polynomially related with its modulo m degree. For m be a power of primes, it is already known that the module m degree can be arbitrarily smaller compare to the degree complexity (see Section 2 for details). When m has at least two distinct prime factors, the question remains open. Towards this question, our results include: (1) we obtain some nontrivial equivalent forms of this question; (2) we affirm this question for some special classes of functions; (3) we prove a no-go theorem, explaining why this problem is difficult to attack from the computational complexity point of view; (4) we show a super-linear separation between the degree complexity and the modulo m degree.

AAAI Conference 2020 Conference Paper

Revisiting Online Quantum State Learning

Feidiao Yang
Jiaqing Jiang
Jialin Zhang
Xiaoming Sun

In this paper, we study the online quantum state learning problem which is recently proposed by Aaronson et al. (2018). In this problem, the learning algorithm sequentially predicts quantum states based on observed measurements and losses and the goal is to minimize the regret. In the previous work, the existing algorithms may output mixed quantum states. However, in many scenarios, the prediction of a pure quantum state is required. In this paper, we ﬁrst propose a Follow-the-Perturbed-Leader (FTPL) algorithm that can guarantee to predict pure quantum states. Theoretical analysis shows that our algorithm can achieve an O( √ T) expected regret under some reasonable settings. In the case that the pure state prediction is not mandatory, we propose another deterministic learning algorithm which is simpler and more efﬁcient. The algorithm is based on the online gradient descent (OGD) method and can also achieve an O( √ T) regret bound. The main technical contribution of this result is an algorithm of projecting an arbitrary Hermitian matrix onto the set of density matrices with respect to the Frobenius norm. We think this subroutine is of independent interest and can be widely used in many other problems in the quantum computing area. In addition to the theoretical analysis, we evaluate the algorithms with a series of simulation experiments. The experimental results show that our FTPL method and OGD method outperform the existing RFTL approach proposed by Aaronson et al. (2018) in almost all settings. In the implementation of the RFTL approach, we give a closed-form solution to the algorithm. This provides an efﬁcient, accurate, and completely executable solution to the RFTL method.

TCS Journal 2020 Journal Article

The one-round multi-player discrete Voronoi game on grids and trees

Xiaoming Sun
Yuan Sun
Zhiyu Xia
Jialin Zhang

Basing on the two-player Voronoi game introduced by Ahn et al. [1] and the multi-player diffusion game introduced by Alon et al. [2], we investigate the following one-round multi-player discrete Voronoi game on grids and trees. There are n players playing this game on a graph G = ( V, E ). Each player chooses an initial vertex from the vertex set of the graph and tries to maximize the size of the nearest vertex set. As the main result, we give sufficient conditions for the existence/non-existence of a pure-strategy Nash equilibrium in 4-player games on grids and only a constant gap leaves unknown. We further consider this game with more than 4 players and construct a family of strategy profiles, which are pure-strategy Nash equilibria on sufficiently narrow graphs. Besides, we investigate the game with 3 players on trees and design a linear time/space algorithm to decide the existence of a pure-strategy Nash equilibrium.

IJCAI Conference 2019 Conference Paper

A Quantum-inspired Classical Algorithm for Separable Non-negative Matrix Factorization

Zhihuai Chen
Yinan Li
Xiaoming Sun
Pei Yuan
Jialin Zhang

Non-negative Matrix Factorization (NMF) asks to decompose a (entry-wise) non-negative matrix into the product of two smaller-sized nonnegative matrices, which has been shown intractable in general. In order to overcome this issue, separability assumption is introduced which assumes all data points are in a conical hull. This assumption makes NMF tractable and widely used in text analysis and image processing, but still impractical for huge-scale datasets. In this paper, inspired by recent development on dequantizing techniques, we propose a new classical algorithm for separable NMF problem. Our new algorithm runs in polynomial time in the rank and logarithmic in the size of input matrices, which achieves an exponential speedup in the low-rank setting.

TCS Journal 2019 Journal Article

A tighter relation between sensitivity complexity and certificate complexity

Kun He
Qian Li
Xiaoming Sun

The sensitivity conjecture proposed by Nisan and Szegedy in 1994, which asserts that for any Boolean function, its sensitivity complexity is polynomially related to the block sensitivity complexity, is one of the most important and challenging problems in the study of decision tree complexity. Despite a lot of efforts, the best known upper bound of block sensitivity, as well as the certificate complexity, is still exponential in terms of sensitivity. In this paper, we give a better upper bound for certificate complexity and block sensitivity, b s ( f ) ≤ C ( f ) ≤ ( 8 9 + o ( 1 ) ) s ( f ) 2 s ( f ) − 1, where b s ( f ), C ( f ) and s ( f ) are the block sensitivity, certificate complexity and sensitivity, respectively. The proof is based on a deep investigation on the structure of the sensitivity graph. We also provide a tighter relationship between the 0-certificate complexity C 0 ( f ) and 0-sensitivity s 0 ( f ) for functions with small 1-sensitivity s 1 ( f ).

AAAI Conference 2017 Conference Paper

Efficient Delivery Policy to Minimize User Traffic Consumption in Guaranteed Advertising

Jia Zhang
Zheng Wang
Qian Li
Jialin Zhang
Yanyan Lan
Qiang Li
Xiaoming Sun

In this work, we study the guaranteed delivery model which is widely used in online advertising. In the guaranteed delivery scenario, ad exposures (which are also called impressions in some works) to users are guaranteed by contracts signed in advance between advertisers and publishers. A crucial problem for the advertising platform is how to fully utilize the valuable user trafﬁc to generate as much as possible revenue. Different from previous works which usually minimize the penalty of unsatisﬁed contracts and some other cost (e. g. representativeness), we propose the novel consumption minimization model, in which the primary objective is to minimize the user trafﬁc consumed to satisfy all contracts. Under this model, we develop a near optimal method to deliver ads for users. The main advantage of our method lies in that it consumes nearly as least as possible user trafﬁc to satisfy all contracts, therefore more contracts can be accepted to produce more revenue. It also enables the publishers to estimate how much user trafﬁc is redundant or short so that they can sell or buy this part of trafﬁc in bulk in the exchange market. Furthermore, it is robust with regard to priori knowledge of user type distribution. Finally, the simulation shows that our method outperforms the traditional state-of-the-art methods.

AAAI Conference 2017 Conference Paper

Randomized Mechanisms for Selling Reserved Instances in Cloud

Jia Zhang
Weidong Ma
Tao Qin
Xiaoming Sun
Tie-Yan Liu

Selling reserved instances (or virtual machines) is a basic service in cloud computing. In this paper, we consider a more ﬂexible pricing model for instance reservation, in which a customer can propose the time length and number of resources of her request, while in today’s industry, customers can only choose from several predeﬁned reservation packages. Under this model, we design randomized mechanisms for customers coming online to optimize social welfare and providers’ revenue. We ﬁrst consider a simple case, where the requests from the customers do not vary too much in terms of both length and value density. We design a randomized mechanism that achieves a competitive ratio 1 42 for both social welfare and revenue, which is a improvement as there is usually no revenue guarantee in previous works such as (Azar et al. 2015; Wang et al. 2015). This ratio can be improved up to 1 11 when we impose a realistic constraint on the maximum number of resources used by each request. On the hardness side, we show an upper bound 1 3 on competitive ratio for any randomized mechanism. We then extend our mechanism to the general case and achieve a competitive ratio 1 42 log k log T for both social welfare and revenue, where T is the ratio of the maximum request length to the minimum request length and k is the ratio of the maximum request value density to the minimum request value density. This result outperforms the previous upper bound 1 CkT for deterministic mechanisms (Wang et al. 2015). We also prove an upper bound 2 log 8kT for any randomized mechanism. All the mechanisms we provide are in a greedy style. They are truthful and easy to be integrated into practical cloud systems.

TCS Journal 2016 Journal Article

Computing the least-core and nucleolus for threshold cardinality matching games

Qizhi Fang
Bo Li
Xiaoming Sun
Jia Zhang
Jialin Zhang

Cooperative games provide a framework for fair and stable profit allocation in multi-agent systems. Core, least-core and nucleolus are such solution concepts that characterize stability of cooperation. In this paper, we study the algorithmic issues of the least-core and nucleolus of threshold cardinality matching games (TCMG). A TCMG is defined on a graph G = ( V, E ) and a threshold T, in which the player set is V and the profit of a coalition S ⊆ V is 1 if the size of a maximum matching in G [ S ] meets or exceeds T, and 0 otherwise. We first show that for a TCMG, the problems of computing least-core value, finding and verifying least-core payoff are all polynomial-time solvable. We also provide a general characterization of the least-core for a large class of TCMG (cf. Theorem 2). Next, based on Gallai–Edmonds Decomposition in matching theory, we establish a concise formulation of the nucleolus for a special case of TCMG (when the threshold T equals 1). For arbitrary T, we prove that the nucleolus of TCMG can be obtained in polynomial time for bipartite graphs and graphs with a perfect matching.

AAAI Conference 2016 Conference Paper

Learning Market Parameters Using Aggregate Demand Queries

Xiaohui Bei
Wei Chen
Jugal Garg
Martin Hoefer
Xiaoming Sun

We study efﬁcient algorithms for a natural learning problem in markets. There is one seller with m divisible goods and n buyers with unknown individual utility functions and budgets of money. The seller can repeatedly announce prices and observe aggregate demand bundles requested by the buyers. The goal of the seller is to learn the utility functions and budgets of the buyers. Our scenario falls into the classic domain of “revealed preference” analysis. Problems with revealed preference have recently started to attract increased interest in computer science due to their fundamental nature in understanding customer behavior in electronic markets. The goal of revealed preference analysis is to observe rational agent behavior, to explain it using a suitable model for the utility functions, and to predict future agent behavior. Our results are the ﬁrst polynomial-time algorithms to learn utility and budget parameters via revealed preference queries in classic Fisher markets with multiple buyers. Our analysis concentrates on linear, CES, and Leontief markets, which are the most prominent classes studied in the literature. Some of our results extend to general Arrow-Debreu exchange markets.

TCS Journal 2015 Journal Article

Any monotone property of 3-uniform hypergraphs is weakly evasive

Raghav Kulkarni
Youming Qiao
Xiaoming Sun

For a Boolean function f, let D ( f ) denote its deterministic decision tree complexity, i. e. , minimum number of (adaptive) queries required in worst case in order to determine f. In a classic paper, Rivest and Vuillemin [11] show that any non-constant monotone property P: { 0, 1 } ( n 2 ) → { 0, 1 } of n-vertex graphs has D ( P ) = Ω ( n 2 ). We extend their result to 3-uniform hypergraphs. In particular, we show that any non-constant monotone property P: { 0, 1 } ( n 3 ) → { 0, 1 } of n-vertex 3-uniform hypergraphs has D ( P ) = Ω ( n 3 ). Our proof combines the combinatorial approach of Rivest and Vuillemin with the topological approach of Kahn, Saks, and Sturtevant [6]. Interestingly, our proof makes use of Vinogradov's Theorem (weak Goldbach Conjecture), inspired by its recent use by Babai et al. [1] in the context of the topological approach. Our work leaves the generalization to k-uniform hypergraphs as an intriguing open question.

TCS Journal 2013 Journal Article

On the sensitivity complexity of bipartite graph properties

Yihan Gao
Jieming Mao
Xiaoming Sun
Song Zuo

Sensitivity complexity, introduced by Cook, Dwork, and Reischuk (1982, 1986) in [2, 3], is an important complexity measure of Boolean functions. Turán (1984) [7] initiated the study of sensitivity complexity for graph properties. He conjectured that for any non-trivial graph property on n vertices, the sensitivity complexity is at least n − 1. He proved that it is greater than n / 4 in his paper. Wegener (1985) [8] verified this conjecture for all monotone graph properties. Recently Sun (2011) [6] improved the lower bound to 6 17 n for general graph properties. We follow their steps and investigate the sensitivity complexity of bipartite graph properties. In this paper we propose the following conjecture about the sensitivity of bipartite graph properties, which can be considered as the bipartite analogue of Turán’s conjecture: for any non-trivial n × m bipartite graph property f, s ( f ) ≥ max { ⌈ n + 1 m + 1 m ⌉, ⌈ m + 1 n + 1 n ⌉ }. We prove this conjecture for all n × 2 bipartite graph properties. For general n × m bipartite graph properties, we show a max { ⌈ n / 2 ⌉, ⌈ m / 2 ⌉ } lower bound. We also prove this conjecture when the bipartite graph property can be written as a composite function.

IJCAI Conference 2013 Conference Paper

Optimal Pricing for Improving Efficiency of Taxi Systems

Jiarui Gan
Bo An
Haizhong Wang
Xiaoming Sun
Zhongzhi Shi

In Beijing, most taxi drivers intentionally avoid working during peak hours despite of the huge customer demand within these peak periods. This dilemma is mainly due to the fact that taxi drivers’ congestion costs are not reﬂected in the current taxi fare structure. To resolve this problem, we propose a new pricing scheme to provide taxi drivers with extra incentives to work during peak hours. This differs from previous studies of taxi market by considering market variance over multiple periods, taxi drivers’ proﬁt-driven decisions, and their scheduling constraints regarding the interdependence among different periods. The major challenge of this research is the computational intensiveness to identify optimal strategy due to the exponentially large size of a taxi driver’s strategy space and the scheduling constraints. We develop an atom schedule method to overcome these issues. It reduces the magnitude of the problem while satisfying the constraints to ﬁlter out infeasible pure strategies. Simulation results based on real data show the effectiveness of the proposed methods, which opens up a new door to improving the ef- ﬁciency of taxi market in megacities (e. g. , Beijing).

PDF Details DOI

TCS Journal 2011 Journal Article

An improved lower bound on the sensitivity complexity of graph properties

Xiaoming Sun

Turán (1984) [11] initiated the study of the sensitivity complexity of graph properties. He conjectured that for any non-trivial graph properties on n vertices, the sensitivity complexity is at least n − 1. He proved an ⌊ n 4 ⌋ lower bound for sensitivity in his paper: Turán (1984) [11]. Wegener (1985) [12] proved this conjecture for all monotone graph properties. In this paper we improve Turán’s lower bound to 6 17 n ( ≈ 0. 35 n ). We hope that this will shed some light on the proof of Turán’s conjecture.

TCS Journal 2009 Journal Article

The antimagicness of the Cartesian product of graphs

Yuchen Zhang
Xiaoming Sun

An antimagic labeling of a graph with M edges and N vertices is a bijection from the set of edges to the set { 1, 2, 3, …, M } such that all the N vertex-sums are pairwise distinct, where the vertex-sum of a vertex v is the sum of labels of all edges incident with v. A graph is called antimagic if it has an antimagic labeling. The antimagicness of the Cartesian product of graphs in several special cases has been studied [Tao-Ming Wang, Toroidal grids are anti-magic, in: Proc. 11th Annual International Computing and Combinatorics Conference, COOCOON’2005, in: LNCS, vol. 3595, Springer, 2005, pp. 671–679, Yongxi Cheng, A new class of antimagic cartesian product graphs, Discrete Mathematics 308 (24) (2008) 6441–6448]. In this paper, we develop new construction methods that are applied to more general cases. We prove that the Cartesian product of paths is antimagic, if one of them has at least three edges. This (almost) answers the open problems in [Yongxi Cheng, Lattice grids and prisms are antimagic, Theoretical Computer Science 374 (2007) 66–73]. We also prove that the Cartesian product of an antimagic regular graph and a connected graph is antimagic, which extends the results of the latter of the two references, where several special cases are studied.

TCS Journal 2007 Journal Article

Block sensitivity of weakly symmetric functions

Xiaoming Sun

Block sensitivity, which was introduced by Nisan [Noam Nisan, CREW PRAMs and decision trees, SIAM Journal on Computing 20 (6) (1991) 999–1007. Earlier version in STOC’89], is one of the most useful measures of Boolean functions. In this paper we investigate the block sensitivity of weakly symmetric functions (functions invariant under some transitive group action). We prove a Ω ( N 1 / 3 ) lower bound for the block sensitivity of weakly symmetric functions. We also construct a weakly symmetric function which has block sensitivity O ̃ ( N 3 / 7 ).

TCS Journal 2004 Journal Article

Performance evaluation for energy efficient topologic control in ad hoc wireless networks

Minming Li
Shawn L. Huang
Xiaoming Sun
Xiao Huang

Minimizing total energy to keep an ad hoc wireless network symmetrically connected is an NP-hard problem. Recently, several greedy approximations have been proposed, based on k-restricted decompositions of the network. Their performance ratios are established through estimations of the least upper bound ρ k for the ratio between total powers of best possible k-restricted decomposition and the optimal solution. In this paper, we determine the exact value of ρ k for all k.