TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publication References
  4. Problems, Models and Complexity. Part I: Theory
 
Options

Problems, Models and Complexity. Part I: Theory

Publikationstyp
Journal Article
Date Issued
2003
Sprache
English
Author(s)
Brüggemann, Wolfgang  
Fischer, Kathrin  orcid-logo
Jahnke, Hermann  
TORE-URI
http://hdl.handle.net/11420/5081
Journal
Journal of mathematical modelling and algorithms in operations research  
Volume
2
Issue
2
Start Page
121
End Page
151
Citation
Journal of Mathematical Modelling and Algorithms 2 (2): 121-151 (2003)
Publisher DOI
10.1023/A:1024998617280
Publisher
Springer Science + Business Media B.V.
The meaning of the term 'problem' in operations research (OR) deviates from the understanding in the theoretical computer sciences: While an OR problem is often conceived to be stated or represented by model formulations, a computer-science problem can be viewed as a mapping from encoded instances to solutions. Such a computer-science problem turns out to be rather similar to an OR model formulation. This ambiguity may cause difficulties if the computer-science theory of computational complexity is applied in the OR context. In OR, a specific model formulation is commonly used in the analysis of the underlying problem and the results obtained for this model are simply lifted to the problem level. But this may lead to erroneous results, if the model used is not appropriate for such an analysis of the problem. To resolve this issue, we first suggest a new precise formal definition of the term problem which is identified with an equivalence class of models describing it. Afterwards, a new definition is suggested for the size of a model which depends on the assumed encoding scheme. Only models which exhibit a minimal size with respect to a 'reasonable' encoding scheme finally turn out to be suitable for the model-based complexity analysis of an OR problem. Therefore, the appropriate choice (or if necessary the construction) of a suitable representative of an OR problem becomes an important theoretical aspect of the modelling process.
Subjects
philosophy of modelling
problem complexity
terminology
DDC Class
330: Wirtschaft
600: Technik
TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback