1 citations · 1 across the 7 of their papers we have counts for
7 papers
Sampling permutations satisfying constraints within the lopsided local lemma regime
Kun He, Guoliang Qiu, Xiaoming Sun
Sampling a random permutation with restricted positions, or equivalently approximating the permanent of a 0-1 matrix, is a fundamental problem in computer science, with several not…
A Thorough Comparison Between Independent Cascade and Susceptible-Infected-Recovered Models
Panfeng Liu, Guoliang Qiu, Biaoshuai Tao +1
We study cascades in social networks with the independent cascade (IC) model and the Susceptible-Infected-recovered (SIR) model. The well-studied IC model fails to capture the feat…
FPTAS for Holant Problems with Log-Concave Signatures
Kun He, Zhidan Li, Guoliang Qiu +1
For an integer , a -matching in a graph is a set such that each vertex is incident to at most edges in . We design a fully polyn…
MMS Allocations of Chores with Connectivity Constraints: New Methods and New Results
Mingyu Xiao, Guoliang Qiu, Sen Huang
We study the problem of allocating indivisible chores to agents under the Maximin share (MMS) fairness notion. The chores are embedded on a graph and each bundle of chores assigned…
Improved Competitive Ratio for Edge-Weighted Online Stochastic Matching
Yilong Feng, Guoliang Qiu, Xiaowei Wu +1
We consider the edge-weighted online stochastic matching problem, in which an edge-weighted bipartite graph G=(I\cup J, E) with offline vertices J and online vertex types I is give…
Inapproximability of Counting Independent Sets in Linear Hypergraphs
Guoliang Qiu, Jiaheng Wang
It is shown in this note that approximating the number of independent sets in a -uniform linear hypergraph with maximum degree at most is NP-hard if …
A Perfect Sampler for Hypergraph Independent Sets
Guoliang Qiu, Yanheng Wang, Chihao Zhang
The problem of uniformly sampling hypergraph independent sets is revisited. We design an efficient perfect sampler for the problem under a condition similar to that of the asymmetr…