{"entities":{"Q5958320":{"pageid":8135122,"ns":120,"title":"Item:Q5958320","lastrevid":41267958,"modified":"2025-04-26T21:05:49Z","type":"item","id":"Q5958320","labels":{"en":{"language":"en","value":"A priori optimization for the probabilistic maximum independent set problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1715321"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958320$2245149E-6395-49C6-BF3D-D58F0AAC329C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"54d9fae2e5ea64b12563fb6d374a965e7745538d","datavalue":{"value":{"text":"A priori optimization for the probabilistic maximum independent set problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5958320$F069B34F-500E-4C8B-8978-4481AEB53C22","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"09f830d20b91fba48a17a6e85679d5da88262136","datavalue":{"value":"0988.68135","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958320$A9C8CC19-6D41-48C9-961B-F23D4A767587","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c6f2573a6291e14d8e9e652878d58675c131407d","datavalue":{"value":"10.1016/S0304-3975(01)00005-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958320$B104DC18-3BB1-409F-A3D5-E656D2C7F373","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d3ba2a69555a32a063ac2d811456674ee4a9d37a","datavalue":{"value":{"entity-type":"item","numeric-id":235680,"id":"Q235680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958320$8FDE44EF-59B1-4755-B23A-07A0BF906124","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"704cea475e2d3cbf7f9b1e09c1add901045357ec","datavalue":{"value":{"entity-type":"item","numeric-id":218830,"id":"Q218830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958320$905B0D9F-EEFC-44B8-8F41-680EA2634BBE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958320$01AE47AB-1DD7-42AF-B011-EDB8C86F4E18","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"de0bbc1f0efc0eda52d8a37720ec217ae66c93cd","datavalue":{"value":{"time":"+2002-03-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5958320$36A104F5-DECE-4955-8BC1-A39984584DDC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0e1138aee3dc5415856ed9dcbc85e004cbfdc28e","datavalue":{"value":"We first propose a formal definition for the concept of probabilistic combinatorial optimization problem (under the a priori method). Next, we study the complexity of optimally solving probabilistic maximum independent set problem under several a priori optimization strategies as well as the complexity of approximating optimal solutions. For the different strategies studied, we present results about the restriction of probabilistic independent set on bipartite graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958320$02696ABC-D842-4F06-B8F3-EA22E49BF439","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958320$89AE3D5C-52D5-4A20-890E-61CDE3C57B96","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"992a99d398c6dfde1d048e0eb664447b084de969","datavalue":{"value":"1715321","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958320$BFE4DDC6-380D-447B-A3EB-097F17D3B604","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a579d0f9c95874b2f78e6dc6eea5d69fc167232d","datavalue":{"value":"probabilistic optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958320$34D9DAE6-09A4-447A-9A10-0BE0A3AAD279","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"832405e003d774dce822c65e9e01ce531ed8c899","datavalue":{"value":"NP-hard problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958320$2D1A5FC2-E3B9-48C6-927F-4482FB0DAAD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958320$B648D9BF-01C6-4A21-9772-E2E53BF20DF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b1c7c178bf1c7f35ae219fa5c07af16c9e2a4621","datavalue":{"value":"polynomial approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958320$F9C89E36-4A08-416C-8717-3B7D99578AAF","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958320$4098B7CD-E821-4CA3-A1C5-7E3D13A4DC30","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958320$49D43EFB-C9A9-400E-9DA3-6979742EB32C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e37495b38ad24de2c142223583725a38d6928404","datavalue":{"value":{"entity-type":"item","numeric-id":5753749,"id":"Q5753749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958320$2B8258B8-CA00-40CB-8960-2DCD33F09252","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72bdc200c096a90cb093d01083b69c58672a0aa3","datavalue":{"value":{"entity-type":"item","numeric-id":3682518,"id":"Q3682518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958320$B8C78021-FC98-4BA2-9E07-64B1F6B296EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8ae8bf01f116bb5adf895448a8445209d5be78e","datavalue":{"value":{"entity-type":"item","numeric-id":3222885,"id":"Q3222885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958320$CE129DD5-F316-45F8-8C96-402201F7D278","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8472c58ea8c4e573d804ab475a4e424b9fa62b9b","datavalue":{"value":{"entity-type":"item","numeric-id":1357776,"id":"Q1357776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958320$07209975-2645-4580-AF82-DAD743372028","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958320$58F267A6-67F4-4777-8AF1-BC4CC3D3F7AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958320$698ECEB0-8C8F-4583-B19C-446B51AD6239","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c837d56e04962823c1d7c934cd015e72d540d8c","datavalue":{"value":{"entity-type":"item","numeric-id":1588908,"id":"Q1588908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958320$565B7B1F-C33F-4B96-AC17-3C19AC951300","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42a2e66eb836284bb6dba8115cc99b9aeb79b368","datavalue":{"value":{"entity-type":"item","numeric-id":4021823,"id":"Q4021823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958320$76C52EDA-C280-4F8C-BB48-F35BC23D61C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56364b8da0a7bdaced7ee35c473629c73eb3fa5c","datavalue":{"value":{"entity-type":"item","numeric-id":4532541,"id":"Q4532541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958320$4FB07E4B-9E8D-4E01-B73C-37BD4F9A4E7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fe979badcb8bfb7a41b5de5f764eb66747617dd","datavalue":{"value":{"entity-type":"item","numeric-id":5781249,"id":"Q5781249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958320$51EDB892-4219-497F-843E-EF8A3715E5A0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30135833ad17dc3fac76b1a98da865a9479d6699","datavalue":{"value":{"entity-type":"item","numeric-id":4258251,"id":"Q4258251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7ce8158029a2e8d40bd8b25a6ac7bf2940f0955","datavalue":{"value":{"amount":"+0.989445","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958320$63D69FAF-D2A4-4E2F-AD25-DE7531C83153","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1fa48139afc10cd1896e588695d9da5e784b2009","datavalue":{"value":{"entity-type":"item","numeric-id":4305756,"id":"Q4305756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0bfaea267b7b6e2093d7c3d245ffb2c93791b98a","datavalue":{"value":{"amount":"+0.8774675","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958320$8CA8E29D-62EC-46D5-96C3-7F736D27AC56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cf93cefca3c98fb2ce9fe849f9e00662120fb2c","datavalue":{"value":{"entity-type":"item","numeric-id":4319768,"id":"Q4319768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec7af7938c542582c82c535cf9b379d266fef082","datavalue":{"value":{"amount":"+0.87701046","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958320$BB83080C-DFAC-442B-8C89-8689D79F82D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"911512664017e6d76111c701d0b6d8e646cc6b08","datavalue":{"value":{"entity-type":"item","numeric-id":3075512,"id":"Q3075512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"725add41e4f15413118ba21641c991c2608c0208","datavalue":{"value":{"amount":"+0.87485015","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958320$B800505A-1467-4499-A726-43027CC84253","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6eb09150fe32cb979778a514c8a226ceeb679346","datavalue":{"value":{"entity-type":"item","numeric-id":1195856,"id":"Q1195856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83bcdb80c5874eb67391c01727fc202815ed763c","datavalue":{"value":{"amount":"+0.87224615","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958320$8EA8E3BA-62F6-4B76-9DA8-6CD0AB6960CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a8930f0db0c20c7d0258f0fba65ae44a7dafd0d","datavalue":{"value":{"entity-type":"item","numeric-id":2870792,"id":"Q2870792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a5038c349e1bdfa0db7e258ae46db4a06b4607b","datavalue":{"value":{"amount":"+0.8718468","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958320$66B8B2F6-57C5-4A61-9B02-2EEA9615A4F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64d542e5bc7c076090429421dc9e92c519765477","datavalue":{"value":{"entity-type":"item","numeric-id":2149870,"id":"Q2149870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fef28ad8573548a4efb765ee9e911ebf9e18c7be","datavalue":{"value":{"amount":"+0.8707464","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958320$1CB57EB8-AB04-4FF9-BEF0-47F59B74A18B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac366afcd6996c6847dde0cd831029ceb106bf83","datavalue":{"value":{"entity-type":"item","numeric-id":920845,"id":"Q920845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c56bf0fce49e4db7b8439486113476313e2bba0e","datavalue":{"value":{"amount":"+0.86770236","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958320$294CFCFE-6803-4363-8EA3-A738D62CD7D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63f3580e6a41a1dda16f747ce9b5f11ad6599d77","datavalue":{"value":{"entity-type":"item","numeric-id":992507,"id":"Q992507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"595614433898691a44608e4620b9d5606c139aa7","datavalue":{"value":{"amount":"+0.86702067","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5958320$476518EA-3A33-4B20-9C27-D042B859D3C7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5958320","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5958320"}}}}}