5 papers
A New Probabilistic Algorithm for Approximate Model Counting
Cunjing Ge, Feifei Ma, Tian Liu +1
Constrained counting is important in domains ranging from artificial intelligence to software analysis. There are already a few approaches for counting models over various types of…
Algorithms for Cut Problems on Trees
Iyad Kanj, Guohui Lin, Tian Liu +7
We study the {\sc multicut on trees} and the {\sc generalized multiway Cut on trees} problems. For the {\sc multicut on trees} problem, we present a parameterized algorithm that ru…
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…
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…
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…