Approximating solution structure
until further notice
Schloss Dagstuhl, Germany : IBFI
InDemaine, E.; Gutin, G.Z.; Marx, D. (ed.), Dagstuhl Seminar Proceedings 07281, pp. url
Article in monograph or in proceedings
Display more detailsDisplay less details
SW OZ DCC AI
SW OZ NICI KI
Demaine, E.; Gutin, G.Z.; Marx, D. (ed.), Dagstuhl Seminar Proceedings 07281
Subject(ISSN 1862 - 4405); Cognitive artificial intelligence; DI-BCB_DCC_Theme 2: Perception, Action and Control
Approximations can aim at having close to optimal value or, alternatively, they can aim at structurally resembling an optimal solution. Whereas value-approximation has been extensively studied by complexity theorists over the last three decades, structural-approximation has not yet been defined, let alone studied. However, structuralapproximation is theoretically no less interesting, and has important applications in cognitive science. Building on analogies with existing valueapproximation algorithms and classes, we develop a general framework for analyzing structural (in)approximability. We identify dissociations between solution value and solution structure, and generate a list of open problems that may stimulate future research.
Upload full text
Use your RU credentials (u/z-number and password) to log in with SURFconext to upload a file for processing by the repository team.