1 citations · 1 across the 7 of their papers we have counts for
5 papers · 1 filter
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…
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…
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…