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 Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Truthful Mechanisms for Steiner Tree Problems
Authors: Jinshan Zhang, Zhengyang Liu, Xiaotie Deng, Jianwei Yin
AAAI 2023 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present a truthful-in-expectation mechanism that achieves the approximation ratio ln 4 + Ο΅ β 1.39, which matches the current best algorithmic ratio for STP. |
| Researcher Affiliation | Academia | 1 Zhejiang University 2 Beijing Institute of Technology 3 Peking University |
| Pseudocode | No | The paper describes algorithmic steps in prose (e.g., 'The mechanism M for k-DCR works as follows. 1. The allocation rule X: select the solution xβwith the probability Ξ»β. 2. The payment rule P: for each edge e, the payment for e is...'), but it does not present any formal pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access information (e.g., a link or explicit statement of code release) for the source code of the described methodology. |
| Open Datasets | No | This is a theoretical paper focused on algorithm design and analysis; it does not involve the use of datasets for training in an empirical machine learning sense. Therefore, there is no mention of publicly available datasets or access information for them. |
| Dataset Splits | No | This is a theoretical paper focused on algorithm design and analysis, not empirical experiments. Therefore, there is no discussion of training/validation/test dataset splits. |
| Hardware Specification | No | This is a theoretical paper discussing mechanism design and approximation algorithms. It does not report on experimental setups or hardware specifications used for running experiments. |
| Software Dependencies | No | This is a theoretical paper that focuses on mathematical proofs and algorithm design. It does not mention any specific software dependencies with version numbers that would be required to replicate experiments. |
| Experiment Setup | No | This is a theoretical paper focused on algorithm design and analysis, not empirical experiments. Therefore, it does not provide details about experimental setup, hyperparameters, or training configurations. |