Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Uniform Random Generation and Dominance Testing for CP-Nets
Authors: Thomas E. Allen, Judy Goldsmith, Hayden Elizabeth Justice, Nicholas Mattei, Kayla Raines
JAIR 2017 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We use the uniform generation algorithm to investigate the maximum and expected flipping lengths... Using our new statistical evidence, we conjecture that, for CP-nets with binary variables and complete conditional preference tables, the expected flipping length is polynomial in the number of preference variables. ... To understand the DT problem as fully as possible for small n, we first studied all DT instances up to n = 4 binary variables ... We performed these experiments using MATLAB and the Matlab BGL Boost Graphics Library package running under Windows 10 on a Dell Vostro 470 computer with an Intel i5-3450 processor and 8GB RAM. ... For our next experiment, we generated 100 binary-valued CP-nets for n from 5 to 9... In our last experiment, we generated 1000 binary-valued DT problem instances... |
| Researcher Affiliation | Collaboration | Thomas E. Allen EMAIL Centre College, Judy Goldsmith EMAIL University of Kentucky, Hayden Elizabeth Justice EMAIL Western Kentucky University, Nicholas Mattei EMAIL IBM T.J. Watson Research Center, Kayla Raines EMAIL University of Kentucky |
| Pseudocode | Yes | Figure 6: Algorithm Is-Function-Degenerate Decides Whether Function Vector F is Degenerate, Figure 8: Algorithm: Generate All DAGs that Extend Dagcode A<j, Figure 9: Algorithm: Generate All CP-Nets that Extend A<j, Figure 11: Algorithm: Generate a CP-Net Uniformly at Random, Figure 19: Generic Algorithm: Depth-Limited Dominance Testing, Figure 20: Solver Algorithm: Depth-Limited DT*, Figure 21: Solver Algorithm: DT-SAT |
| Open Source Code | Yes | We have released this code as a free and open source project. ... We provide novel algorithms and open source code to generate CP-nets uniformly at random in polynomial time with any number of variables and a bound on in-degree. ... The implementation is available at https://github.com/nmattei/Gen CPnet. ... All code and data is available on Git Hub at https://github.com/nmattei/Gen CPnet. |
| Open Datasets | Yes | All code and data is available on Git Hub at https://github.com/nmattei/Gen CPnet. |
| Dataset Splits | No | The paper generates its own data for experiments and describes the parameters for this generation (e.g., 'generated 100 binary-valued CP-nets for n from 5 to 9', 'generated 1000 binary-valued DT problem instances with n ranging from 10 to 15...'), but it does not specify traditional training/test/validation splits of a fixed dataset. |
| Hardware Specification | Yes | We performed these experiments using MATLAB and the Matlab BGL Boost Graphics Library package running under Windows 10 on a Dell Vostro 470 computer with an Intel i5-3450 processor and 8 GB RAM. ... For this experiment we again used MATLAB and Matlab BGL on a Windows 10 Dell Vostro 470 with an Intel i5-3450 processor and 8GB RAM. ... We reimplemented the iterative DLDT* in C++, allowing us to run the experiment for the 72000 binary problems in 50 minutes on a Mac Book Pro computer with a 2.7 GHz Intel Core i5 processor and 8 GB RAM, with the multivalued problems requiring about 100 minutes. |
| Software Dependencies | No | The paper mentions using 'MATLAB', 'Matlab BGL Boost Graphics Library', 'Windows 10', and 'C++', but does not provide specific version numbers for these software components. |
| Experiment Setup | Yes | Table 4 provides a practical example of how quickly one can generate CP-nets using the method described above. The table shows the average time (over 10 trials), in seconds, required to generate 100 CP-nets with n = 10 to 50 nodes, domains of size d = 2 to 4, and a bound of c = 4 on in-degree... For our next experiment, we generated 100 binary-valued CP-nets for n from 5 to 9, obtained the corresponding preference graph of each, and applied the Floyd Warshall algorithm to compute the maximin path length... we varied this bound from c = 1 to c = 4... In our last experiment, we generated 1000 binary-valued DT problem instances with n ranging from 10 to 15, bound c on in-degree ranging from 1 to 4, and Hamming distances of 2, n/2 , and n, a total of 72000 DT problems. |