Maximization of the Average Quality of Anytime Contract Algorithms over a Time Interval

Delhay, Arnaud; Dauchet, Max; Taillibert, Patrick; Vanheeghe, Philippe

Maximization of the Average Quality of Anytime Contract Algorithms over a Time Interval

Arnaud Delhay, Max Dauchet, Patrick Taillibert, Philippe Vanheeghe

Download BibTeX Cite

Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Automated Reasoning. Pages 212-220.

Abstract

Previous studies considered quality optimization of anytime algorithms by taking into account the quality of the final result. The problem we are interested in is the maximization of the average quality of a contract algorithm over a time interval. We first informally illustrate and motivate this problem with few concrete situations. Then we prove that the problem is NPhard, but quadratic if the time interval is large enough. Eventually we give empirical results.

Arnaud Delhay, Max Dauchet, Patrick Taillibert, and Philippe Vanheeghe. 1999. Maximization of the Average Quality of Anytime Contract Algorithms over a Time Interval. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99. IJCAI, 212–220. https://ijcai.org/proceedings/1999/32

@inproceedings{ijcai1999p32,
  title     = {Maximization of the Average Quality of Anytime Contract Algorithms over a Time Interval},
  author    = {Delhay, Arnaud and Dauchet, Max and Taillibert, Patrick and Vanheeghe, Philippe},
  booktitle = {Proceedings of the Sixteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-99}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Thomas Dean},
  pages     = {212--220},
  year      = {1999},
  note      = {Automated Reasoning},
  url       = {https://ijcai.org/proceedings/1999/32},
}

TY  - CPAPER
TI  - Maximization of the Average Quality of Anytime Contract Algorithms over a Time Interval
AU  - Delhay, Arnaud
AU  - Dauchet, Max
AU  - Taillibert, Patrick
AU  - Vanheeghe, Philippe
T2  - Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1999
SP  - 212
EP  - 220
UR  - https://ijcai.org/proceedings/1999/32
ER  -