Loading…
The computational complexity of component selection in simulation reuse
Simulation composability has been much more difficult to realize than some initially imagined. We believe that success lies in explicit considerations for the adaptability of components. In this paper, we show that the complexity of optimal component selection for adaptable components is NP-complete...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Conference Proceeding |
| Language: | English |
| Subjects: | |
| Online Access: | Request full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | |
|---|---|
| cites | |
| container_end_page | |
| container_issue | |
| container_start_page | 10 pp. |
| container_title | |
| container_volume | |
| creator | Bartholet, R.G. Brogan, D.C. Reynolds, P.F. |
| description | Simulation composability has been much more difficult to realize than some initially imagined. We believe that success lies in explicit considerations for the adaptability of components. In this paper, we show that the complexity of optimal component selection for adaptable components is NP-complete. However, our approach allows for the efficient adaptation of components to construct a complex simulation in the most flexible manner while allowing the greatest opportunity to meet all requirements, all the while reducing time and costs. We demonstrate that complexity can vary from polynomial, to NP, and even to exponential as a function of seemingly simple decisions made about the nature of dependencies among components. We generalize these results to show that regardless of the types or reasons for dependencies in component selection, just their mere existence makes this problem very difficult to solve optimally. |
| doi_str_mv | 10.1109/WSC.2005.1574541 |
| format | conference_proceeding |
| fullrecord | <record><control><sourceid>ieee_CHZPO</sourceid><recordid>TN_cdi_ieee_primary_1574541</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>1574541</ieee_id><sourcerecordid>1574541</sourcerecordid><originalsourceid>FETCH-LOGICAL-i175t-5035c3e1fa0aec9515be430cf3c73548aacb1cb76ee15a619f918f5f8d8cfc663</originalsourceid><addsrcrecordid>eNotkM1Lw0AUxBc_wLR6F7zkH0h8r5uX3T1K0CoUPFjxWDbrW1zJR8kmYP97a-xp-MHMMIwQtwg5Ipj7j7cqXwFQjqQKKvBMJEiks0ICnYsFKA3SEBq4EAlog5lSsrwSixi_AVATrhKx3n5x6vp2P412DH1nm5ka_gnjIe39TH3H3ZhGbtj9edLQpTG0UzMn0oGnyNfi0tsm8s1Jl-L96XFbPWeb1_VL9bDJAioaMwJJTjJ6C5bdcRzVfJzrvHRKUqGtdTW6WpXMSLZE4w1qT15_auddWcqluPvvDcy82w-htcNhdzpA_gI6Dk7K</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>The computational complexity of component selection in simulation reuse</title><source>IEEE Xplore All Conference Series</source><creator>Bartholet, R.G. ; Brogan, D.C. ; Reynolds, P.F.</creator><creatorcontrib>Bartholet, R.G. ; Brogan, D.C. ; Reynolds, P.F.</creatorcontrib><description>Simulation composability has been much more difficult to realize than some initially imagined. We believe that success lies in explicit considerations for the adaptability of components. In this paper, we show that the complexity of optimal component selection for adaptable components is NP-complete. However, our approach allows for the efficient adaptation of components to construct a complex simulation in the most flexible manner while allowing the greatest opportunity to meet all requirements, all the while reducing time and costs. We demonstrate that complexity can vary from polynomial, to NP, and even to exponential as a function of seemingly simple decisions made about the nature of dependencies among components. We generalize these results to show that regardless of the types or reasons for dependencies in component selection, just their mere existence makes this problem very difficult to solve optimally.</description><identifier>ISSN: 0891-7736</identifier><identifier>ISBN: 0780395190</identifier><identifier>ISBN: 9780780395190</identifier><identifier>EISSN: 1558-4305</identifier><identifier>DOI: 10.1109/WSC.2005.1574541</identifier><language>eng</language><publisher>IEEE</publisher><subject>Buildings ; Computational complexity ; Computational modeling ; Computer science ; Computer simulation ; Cost function ; Polynomials ; Real time systems ; Research initiatives ; Software engineering</subject><ispartof>Proceedings of the Winter Simulation Conference, 2005, 2005, p.10 pp.</ispartof><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/1574541$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,780,784,789,790,2058,4050,4051,27925,54555,54920,54932</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/1574541$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Bartholet, R.G.</creatorcontrib><creatorcontrib>Brogan, D.C.</creatorcontrib><creatorcontrib>Reynolds, P.F.</creatorcontrib><title>The computational complexity of component selection in simulation reuse</title><title>Proceedings of the Winter Simulation Conference, 2005</title><addtitle>WSC</addtitle><description>Simulation composability has been much more difficult to realize than some initially imagined. We believe that success lies in explicit considerations for the adaptability of components. In this paper, we show that the complexity of optimal component selection for adaptable components is NP-complete. However, our approach allows for the efficient adaptation of components to construct a complex simulation in the most flexible manner while allowing the greatest opportunity to meet all requirements, all the while reducing time and costs. We demonstrate that complexity can vary from polynomial, to NP, and even to exponential as a function of seemingly simple decisions made about the nature of dependencies among components. We generalize these results to show that regardless of the types or reasons for dependencies in component selection, just their mere existence makes this problem very difficult to solve optimally.</description><subject>Buildings</subject><subject>Computational complexity</subject><subject>Computational modeling</subject><subject>Computer science</subject><subject>Computer simulation</subject><subject>Cost function</subject><subject>Polynomials</subject><subject>Real time systems</subject><subject>Research initiatives</subject><subject>Software engineering</subject><issn>0891-7736</issn><issn>1558-4305</issn><isbn>0780395190</isbn><isbn>9780780395190</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2005</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNotkM1Lw0AUxBc_wLR6F7zkH0h8r5uX3T1K0CoUPFjxWDbrW1zJR8kmYP97a-xp-MHMMIwQtwg5Ipj7j7cqXwFQjqQKKvBMJEiks0ICnYsFKA3SEBq4EAlog5lSsrwSixi_AVATrhKx3n5x6vp2P412DH1nm5ka_gnjIe39TH3H3ZhGbtj9edLQpTG0UzMn0oGnyNfi0tsm8s1Jl-L96XFbPWeb1_VL9bDJAioaMwJJTjJ6C5bdcRzVfJzrvHRKUqGtdTW6WpXMSLZE4w1qT15_auddWcqluPvvDcy82w-htcNhdzpA_gI6Dk7K</recordid><startdate>2005</startdate><enddate>2005</enddate><creator>Bartholet, R.G.</creator><creator>Brogan, D.C.</creator><creator>Reynolds, P.F.</creator><general>IEEE</general><scope>6IE</scope><scope>6IH</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIO</scope></search><sort><creationdate>2005</creationdate><title>The computational complexity of component selection in simulation reuse</title><author>Bartholet, R.G. ; Brogan, D.C. ; Reynolds, P.F.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i175t-5035c3e1fa0aec9515be430cf3c73548aacb1cb76ee15a619f918f5f8d8cfc663</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2005</creationdate><topic>Buildings</topic><topic>Computational complexity</topic><topic>Computational modeling</topic><topic>Computer science</topic><topic>Computer simulation</topic><topic>Cost function</topic><topic>Polynomials</topic><topic>Real time systems</topic><topic>Research initiatives</topic><topic>Software engineering</topic><toplevel>online_resources</toplevel><creatorcontrib>Bartholet, R.G.</creatorcontrib><creatorcontrib>Brogan, D.C.</creatorcontrib><creatorcontrib>Reynolds, P.F.</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan (POP) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE/IET Electronic Library</collection><collection>IEEE Proceedings Order Plans (POP) 1998-present</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Bartholet, R.G.</au><au>Brogan, D.C.</au><au>Reynolds, P.F.</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>The computational complexity of component selection in simulation reuse</atitle><btitle>Proceedings of the Winter Simulation Conference, 2005</btitle><stitle>WSC</stitle><date>2005</date><risdate>2005</risdate><spage>10 pp.</spage><pages>10 pp.-</pages><issn>0891-7736</issn><eissn>1558-4305</eissn><isbn>0780395190</isbn><isbn>9780780395190</isbn><abstract>Simulation composability has been much more difficult to realize than some initially imagined. We believe that success lies in explicit considerations for the adaptability of components. In this paper, we show that the complexity of optimal component selection for adaptable components is NP-complete. However, our approach allows for the efficient adaptation of components to construct a complex simulation in the most flexible manner while allowing the greatest opportunity to meet all requirements, all the while reducing time and costs. We demonstrate that complexity can vary from polynomial, to NP, and even to exponential as a function of seemingly simple decisions made about the nature of dependencies among components. We generalize these results to show that regardless of the types or reasons for dependencies in component selection, just their mere existence makes this problem very difficult to solve optimally.</abstract><pub>IEEE</pub><doi>10.1109/WSC.2005.1574541</doi></addata></record> |
| fulltext | fulltext_linktorsrc |
| identifier | ISSN: 0891-7736 |
| ispartof | Proceedings of the Winter Simulation Conference, 2005, 2005, p.10 pp. |
| issn | 0891-7736 1558-4305 |
| language | eng |
| recordid | cdi_ieee_primary_1574541 |
| source | IEEE Xplore All Conference Series |
| subjects | Buildings Computational complexity Computational modeling Computer science Computer simulation Cost function Polynomials Real time systems Research initiatives Software engineering |
| title | The computational complexity of component selection in simulation reuse |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-25T20%3A23%3A13IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_CHZPO&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=The%20computational%20complexity%20of%20component%20selection%20in%20simulation%20reuse&rft.btitle=Proceedings%20of%20the%20Winter%20Simulation%20Conference,%202005&rft.au=Bartholet,%20R.G.&rft.date=2005&rft.spage=10%20pp.&rft.pages=10%20pp.-&rft.issn=0891-7736&rft.eissn=1558-4305&rft.isbn=0780395190&rft.isbn_list=9780780395190&rft_id=info:doi/10.1109/WSC.2005.1574541&rft_dat=%3Cieee_CHZPO%3E1574541%3C/ieee_CHZPO%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i175t-5035c3e1fa0aec9515be430cf3c73548aacb1cb76ee15a619f918f5f8d8cfc663%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=1574541&rfr_iscdi=true |