246 citations · 1.4k across the 50 of their papers we have counts for
4 papers · 1 filter
On Unique Games with Negative Weights
Peng Cui
In this paper, the author defines Generalized Unique Game Problem (GUGP), where weights of the edges are allowed to be negative. Two special types of GUGP are illuminated, GUGP-NWA…
Improved Exponential Time Lower Bound of Knapsack Problem under BT model
Xin Li, Tian Liu, Han Peng +2
M.Alekhnovich et al. recently have proposed a model of algorithms, called BT model, which covers Greedy, Backtrack and Simple Dynamic Programming methods and can be further divided…
Many Hard Examples in Exact Phase Transitions with Application to Generating Hard Satisfiable Instances
Ke Xu, Wei Li
This paper first analyzes the resolution complexity of two random CSP models (i.e. Model RB/RD) for which we can establish the existence of phase transitions and identify the thres…
An Average Analysis of Backtracking on Random Constraint Satisfaction Problems
Ke Xu, Wei Li
In this paper we propose a random CSP model, called Model GB, which is a natural generalization of standard Model B. It is proved that Model GB in which each constraint is easy to…