A Scalable Scheme for Counting Linear Extensions
Authors: Topi Talvitie, Kustaa Kangas, Teppo Niinimäki, Mikko Koivisto
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | which in our experiments exhibits polynomial characteristics and significantly outperforms previous schemes. |
| Researcher Affiliation | Academia | 1 University of Helsinki 2 Aalto University |
| Pseudocode | No | The paper describes algorithms in prose (e.g., in Section 4.2 for the perfect sampler) but does not present them in a structured pseudocode block or a clearly labeled algorithm format. |
| Open Source Code | Yes | We will make our implementation for relaxation Tootsie Pop and the SAT encoding generators publicly available. 1github.com/ttalvitie/le-counting-practice |
| Open Datasets | Yes | We adopted the experimental setup and benchmark instances of Talvitie et al. [2018]: The instances are randomly generated and include posets of average indegree k {3, 5}, bipartite posets of density p {0.2, 0.5}, and posets extracted from subgraphs of the networks Andes, Diabetes, Link, Munin, and Pigs from the Bayesian Network Repository (www.cs.huji.ac.il/ galel/Repository). |
| Dataset Splits | No | The paper evaluates algorithms on benchmark instances (posets) but does not describe traditional machine learning dataset splits (training, validation, test sets) as the problem is counting linear extensions for given inputs, not training a model. |
| Hardware Specification | No | The paper mentions '24 hours of CPU time and memory limited to 8 gigabytes' but does not specify particular CPU or GPU models or other detailed hardware specifications. |
| Software Dependencies | No | The paper mentions specific software like 'sharp SAT', 'D4', and 'Approx MC2', but does not provide version numbers for these or any other ancillary software dependencies. |
| Experiment Setup | Yes | All the algorithms were instantiated to produce a (1, 1/4)-approximation. |