Distributed Breakout: Beyond Satisfaction
Authors: Steven Okamoto, Roie Zivan, Aviv Nahon
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our third contribution is an extensive empirical analysis of GDBA on three classes of DCOPs: random graphs with unstructured cost functions, weighted graph coloring, and meeting scheduling. Our results show that GDBA finds equal or better solutions than state-of-the-art competitors, in contrast to previous reported results [Zhang et al., 2005]." and "6 Experimental Results We tested GDBA on both abstract and realistic benchmark problems. Unless otherwise noted, all results reported are averages over 200 independent, randomly-generated instances with n = 200. We compared GDBA to six DCOP algorithms: DSA (type C, p = 0.4 and p = 0.8; settings of p from 0.1 to 0.9 were used and these performed best, each on different types of problems) [Zhang et al., 2005], MGM and MGM2 [Maheswaran et al., 2004a], Max-Sum with tiebreaking preferences [Farinelli et al., 2008] and damping factor 0.5 [Tarlow et al., 2010], DSAN [Arshad and Silaghi, 2004], and ADPOP (max Dims = 2) [Petcu and Faltings, 2005]. |
| Researcher Affiliation | Academia | Industrial Engineering and Management Department Ben-Gurion University of the Negev Beer-Sheva, Israel {okamotos,zivanr,nahona}@bgu.ac.il |
| Pseudocode | Yes | Algorithm 1: GDBA |
| Open Source Code | No | The paper does not provide any concrete statement or link regarding the public availability of the source code for the Generalized Distributed Breakout Algorithm (GDBA) described. |
| Open Datasets | No | The paper describes generating instances for random graphs, weighted graph coloring, and meeting scheduling problems based on specified parameters (e.g., 'randomly-generated instances', 'random graph topologies', 'meeting scheduling problems using EAV representation [Maheswaran et al., 2004b]'). However, it does not provide concrete access information (links, DOIs, repositories, or explicit citations to a downloadable dataset) for these generated instances or any other publicly available datasets used in the experiments. |
| Dataset Splits | No | The paper evaluates algorithms on multiple independent, randomly-generated problem instances rather than splitting a single dataset into train/validation/test sets. Therefore, it does not provide explicit dataset split percentages or counts in the context of training and validation. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware (e.g., CPU, GPU models, memory, or cloud instance types) used to run the experiments. |
| Software Dependencies | No | The paper mentions various algorithms used for comparison (e.g., DSA, MGM, Max-Sum) but does not provide specific software dependencies or library names with version numbers required for replication. |
| Experiment Setup | Yes | All algorithms were run for 2000 steps. For each algorithm we present the average anytime result following each step. Costs were random, with each entry in each table independently sampled from the discrete uniform distribution on [1..10]; zero was excluded to demonstrate GDBA s applicability to general-valued DCOPs. All domains had 10 values. DSA (type C, p = 0.4 and p = 0.8; settings of p from 0.1 to 0.9 were used...). Max-Sum with tiebreaking preferences [Farinelli et al., 2008] and damping factor 0.5 [Tarlow et al., 2010]. ADPOP (max Dims = 2) [Petcu and Faltings, 2005]. meeting scheduling problems using EAV representation [Maheswaran et al., 2004b] with 200 people and 50 meetings to be scheduled in a 10-hour workday from 8:00 AM to 6:00 PM discretized into 15-minute time slots. Each meeting has a duration uniformly distributed on [1..4] time slots, and a desired attendance uniformly distributed on [2..6] people; the specific individuals are chosen uniformly at random. The required traveling time between the locations of each pair of meetings is uniformly distributed on [1..2]. The preferences of the participants impose a cost that is uniformly distributed on [1..3] for each meeting and time. |