Pseudo-Tree Construction Heuristics for DCOPs with Variable Communication Times
Authors: Atena M Tabakhi
AAAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Empirical evaluations of DCOP algorithms are typically done in simulation and under the assumption that the communication times between all pairs of agents are identical, which is unrealistic in many real-world applications. In this abstract, we incorporate non-uniform communication times in the default DCOP model and propose heuristics that exploit these communication times to speed up DCOP algorithms that operate on pseudo-trees. Our experimental results show that our heuristics find pseudo-trees with smaller depths than the existing max-degree heuristic by up to 20%. |
| Researcher Affiliation | Academia | Atena M Tabakhi Department of Computer Science New Mexico State University amtabakh@cs.nmsu.edu |
| Pseudocode | No | The paper describes algorithms and heuristics using mathematical formulas and descriptive text but does not include structured pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | No statement or link providing concrete access to open-source code for the described methodology was found. |
| Open Datasets | No | The paper uses random graphs generated with specific parameters but does not provide access information for a publicly available or open dataset. |
| Dataset Splits | No | The paper describes the generation parameters for the random graphs used in evaluation but does not specify training, validation, or test dataset splits in the typical machine learning sense. |
| Hardware Specification | No | No specific hardware details (e.g., GPU/CPU models, memory) used for running the experiments are mentioned in the paper. |
| Software Dependencies | No | No specific ancillary software details, such as library or solver names with version numbers, are provided. |
| Experiment Setup | Yes | We vary the number of variables |X| = {10, 20, 30, 40, 50, 60} and set the constraint density p1 = 0.3. For each configuration, we sample the physical distances di of the constraints from two possible truncated distributions uniform and Gaussian N(50, 25) from the range [1,100] and define the communication time ci = C di with these distances, where we set C = 1 millisecond per meter. |