Counting Linear Extensions in Practice: MCMC Versus Exponential Monte Carlo
Authors: Topi Talvitie, Kustaa Kangas, Teppo Niinimäki, Mikko Koivisto
AAAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | This work presents an empirical evaluation of the state-of-the-art schemes and investigates a number of ideas to enhance their performance. ... Through the empirical evaluation, we show that approximate counting is feasible on posets up to a few hundred elements. |
| Researcher Affiliation | Academia | Topi Talvitie Dept. of Computer Science University of Helsinki topi.talvitie@helsinki.fi Kustaa Kangas Dept. of Computer Science Aalto University juho-kustaa.kangas@aalto.fi Teppo Niinim aki Dept. of Computer Science Aalto University teppo.niinimaki@aalto.fi Mikko Koivisto Dept. of Computer Science University of Helsinki mikko.koivisto@helsinki.fi |
| Pseudocode | No | The paper describes algorithms verbally and with illustrative diagrams (e.g., Figure 2) but does not include formal pseudocode blocks or algorithms. |
| Open Source Code | Yes | We will make these instances as well as all algorithm implementations publicly available.1 (footnote refers to github.com/ttalvitie/le-counting-practice) |
| Open Datasets | Yes | Posets extracted from benchmark Bayesian networks, obtained from the Bayesian Network Repository (www.cs. huji.ac.il/ galel/Repository). We generated five posets from each instance class and size between 8 and 512 elements. We will make these instances as well as all algorithm implementations publicly available.1 (footnote refers to github.com/ttalvitie/le-counting-practice) |
| Dataset Splits | No | The paper does not mention specific training/validation/test dataset splits. It evaluates algorithms on generated instances and benchmark posets without describing such partitioning for model training. |
| Hardware Specification | No | Each run was limited to 24 hours of CPU time and 8 GB of RAM; all running times were measured. No specific CPU models, GPU models, or detailed hardware specifications are provided. |
| Software Dependencies | No | No specific software dependencies with version numbers (e.g., programming languages, libraries, frameworks, or solvers with version numbers) are mentioned in the paper. |
| Experiment Setup | Yes | Each algorithm was instantiated to produce a (1, 1/4)-approximation for the number of linear extensions, i.e., an estimate within a factor of 2 with probability at least 3/4. In the experiments we set α = 0.1, β = 10, and κ = 5, observed to perform well on average. |