ML Anthology

The Very Particular Structure of the Very Hard Instances

Dan R. Vlasie
AAAI 1996 pp. 266-270
doi:10.3760/cma.j.issn.0578-1310.2020.01.017 /aaai/1996/vlasie1996aaai-very/

Abstract

We show that the algorithms which behave well on average may have difficulty only for highly structured, non-random inputs, except in a finite number of cases. The formal framework is provided by the theory of Kolmogorov complexity. An experimental verification is done for graph 3-colorability with Brelaz's algorithm.

PDF AAAI Semantic Scholar

Cite

Text

Vlasie. "The Very Particular Structure of the Very Hard Instances." AAAI Conference on Artificial Intelligence, 1996. doi:10.3760/cma.j.issn.0578-1310.2020.01.017

Markdown

[Vlasie. "The Very Particular Structure of the Very Hard Instances." AAAI Conference on Artificial Intelligence, 1996.](https://mlanthology.org/aaai/1996/vlasie1996aaai-very/) doi:10.3760/cma.j.issn.0578-1310.2020.01.017

BibTeX

@inproceedings{vlasie1996aaai-very,
  title     = {{The Very Particular Structure of the Very Hard Instances}},
  author    = {Vlasie, Dan R.},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {1996},
  pages     = {266-270},
  doi       = {10.3760/cma.j.issn.0578-1310.2020.01.017},
  url       = {https://mlanthology.org/aaai/1996/vlasie1996aaai-very/}
}