Showing cs.CCShow all
3 papers · 1 filter
cs.CC2011
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…
cs.CC2007
On Exponential Time Lower Bound of Knapsack under Backtracking
Xin Li, Tian Liu
M.Aleknovich et al. have recently proposed a model of algorithms, called BT model, which generalizes both the priority model of Borodin, Nielson and Rackoff, as well as a simple dy…
cs.CC2006
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…