11,079 research outputs found
LIPIcs, Volume 149, ISAAC'19, Complete Volume
No full textLIPIcs, Volume 149, ISAAC'19, Complete Volum
On the Complexity of Holant Problems
No full textIn this article we survey recent developments on the complexity of Holant problems. We discuss three different aspects of Holant problems: the decision version, exact counting, and approximate counting
Front Matter, Table of Contents, Preface, Symposium Organization
No full textFront Matter, Table of Contents, Preface, Symposium Organizatio
An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines
No full textWe study the scheduling problem on unrelated machines in the
mechanism design setting. This problem was proposed and studied in
the seminal paper (Nisan and Ronen 1999), where they gave a
-approximation randomized truthful mechanism for the case of
two machines. We improve this result by a -approximation
randomized truthful mechanism. We also generalize our result to a
-approximation mechanism for task scheduling with
machines, which improve the previous best upper bound of
$0.875m( Mu'alem and Schapira 2007
The Complexity of Weighted Boolean #CSP Modulo k
No full textWe prove a complexity dichotomy theorem for counting weighted Boolean CSP modulo k for any positive integer k1 . This generalizes a theorem by Faben for the unweighted setting. In the weighted setting, there are new interesting tractable problems. We first prove a dichotomy theorem for the finite field case where k is a prime. It turns out that the dichotomy theorem for the finite field is very similar to the one for the complex weighted Boolean #CSP, found by [Cai, Lu and Xia, STOC 2009]. Then we further extend the result to an arbitrary integer k .QC 20111013</p
Learning Reserve Prices in Second-Price Auctions
No full textThis paper proves the tight sample complexity of {\sf Second-Price Auction
with Anonymous Reserve}, up to a logarithmic factor, for each of all the value
distribution families studied in the literature: -bounded, -bounded, regular, and monotone hazard rate (MHR). Remarkably, the
setting-specific tight sample complexity
depends on the precision , but not on the number of
bidders . Further, in the two bounded-support settings, our learning
algorithm allows {\em correlated} value distributions.
In contrast, the tight sample complexity of {\sf Myerson Auction} proved by Guo, Huang
and Zhang (STOC~2019) has a nearly-linear dependence on , and holds
only for {\em independent} value distributions in every setting.
We follow a similar framework as the Guo-Huang-Zhang work, but replace their
information theoretical arguments with a direct proof.Comment: To appear in ITCS'2
the complexity of weighted boolean #csp modulo k
No full textWe prove a complexity dichotomy theorem for counting weighted Boolean CSP modulo k for any positive integer k > 1. This generalizes a theorem by Faben for the unweighted setting. In the weighted setting, there are new interesting tractable problems. We first prove a dichotomy theorem for the finite field case where k is a prime. It turns out that the dichotomy theorem for the finite field is very similar to the one for the complex weighted Boolean #CSP, found by [Cai, Lu and Xia, STOC 2009]. Then we further extend the result to an arbitrary integer k. © Heng Guo, Sangxia Huang, Pinyan Lu and Mingji Xia.We prove a complexity dichotomy theorem for counting weighted Boolean CSP modulo k for any positive integer k > 1. This generalizes a theorem by Faben for the unweighted setting. In the weighted setting, there are new interesting tractable problems. We first prove a dichotomy theorem for the finite field case where k is a prime. It turns out that the dichotomy theorem for the finite field is very similar to the one for the complex weighted Boolean #CSP, found by [Cai, Lu and Xia, STOC 2009]. Then we further extend the result to an arbitrary integer k. © Heng Guo, Sangxia Huang, Pinyan Lu and Mingji Xia
Deep Cooperation of Local Search and Unit Propagation Techniques
No full textLocal search (LS) is an efficient method for solving combinatorial optimization problems such as MaxSAT and Pseudo Boolean Problems (PBO). However, due to a lack of reasoning power and global information, LS methods get stuck at local optima easily. In contrast to the LS, Systematic Search utilizes unit propagation and clause learning techniques with strong reasoning capabilities to avoid falling into local optima. Nevertheless, the complete search is generally time-consuming to obtain a global optimal solution. This work proposes a deep cooperation framework combining local search and unit propagation to address their inherent disadvantages. First, we design a mechanism to detect when LS gets stuck, and then a well-designed unit propagation procedure is called upon to help escape the local optima. To the best of our knowledge, we are the first to integrate unit propagation technique within LS to overcome local optima. Experiments based on a broad range of benchmarks from MaxSAT Evaluations, PBO competitions, the Mixed Integer Programming Library, and three real-life cases validate that our method significantly improves three state-of-the-art MaxSAT and PBO local search solvers
FPTAS for Hardcore and Ising Models on Hypergraphs
No full textHardcore and Ising models are two most important families of two state spin systems in statistic physics. Partition function of spin systems is the center concept in statistic physics which connects microscopic particles and their interactions with their macroscopic and statistical properties of materials such as energy, entropy, ferromagnetism, etc. If each local interaction of the system involves only two particles, the system can be described by a graph. In this case, fully polynomial-time approximation scheme (FPTAS) for computing the partition function of both hardcore and anti-ferromagnetic Ising model was designed up to the uniqueness condition of the system. These result are the best possible since approximately computing the partition function beyond this threshold is NP-hard. In this paper, we generalize these results to general physics systems, where each local interaction may involves multiple particles. Such systems are described by hypergraphs. For hardcore model, we also provide FPTAS up to the uniqueness condition, and for anti-ferromagnetic Ising model, we obtain FPTAS under a slightly stronger condition
Two-state spin systems with negative interactions
No full textWe study the approximability of computing the partition functions of two-state spin systems. The problem is parameterized by a 2 × 2 symmetric matrix. Previous results on this problem were restricted either to the case where the matrix has non-negative entries, or to the case where the diagonal entries are equal, i.e. Ising models. In this paper, we study the generalization to arbitrary 2 × 2 interaction matrices with real entries. We show that in some regions of the parameter space, it’s #P-hard to even determine the sign of the partition function, while in other regions there are fully polynomial approximation schemes for the partition function. Our results reveal several new computational phase transitions
- …
