REAL

Predicting algorithmic complexity through structure analysis and compression

Mann, Zoltán Ádám and Papp, Pál András (2013) Predicting algorithmic complexity through structure analysis and compression. Applied Soft Computing, 13 (8). pp. 3582-3596. ISSN 1568-4946

[img]
Preview
Text
Mann_Papp_ASOC_2013.pdf

Download (1MB) | Preview

Abstract

The complexity of an algorithm is usually specified by the maximum number of steps made by the algorithm, as a function of the size of the input. However, as different inputs of equal size can yield dramatically different algorithm runtime, the size of the input is not always an appropriate basis for predicting algorithm runtime. In this paper, we argue that the compressed size of the input is more appropriate for this purpose. In particular, we devise a genetic algorithm for compressing a graph by finding the most compact description of its structure, and we demonstrate how the compressed size of the problem instance correlates with the runtime of an exact algorithm for two hard combinatorial problems (graph coloring and Boolean satisfiability).

Item Type: Article
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Depositing User: Dr. Zoltán Ádám Mann
Date Deposited: 22 Sep 2014 18:50
Last Modified: 03 Apr 2023 08:16
URI: http://real.mtak.hu/id/eprint/15996

Actions (login required)

Edit Item Edit Item