{"entities":{"Q666411":{"pageid":668260,"ns":120,"title":"Item:Q666411","lastrevid":63637857,"modified":"2026-04-11T14:31:23Z","type":"item","id":"Q666411","labels":{"en":{"language":"en","value":"Inapproximability and polynomial-time approximation algorithm for UET tasks on structured processor networks"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6013014"}},"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":"Q666411$887F45F9-F1E7-4E44-8036-7D145CD7A0C4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2b0b22969833d68e7ae48d9a04fe30dc16f64f23","datavalue":{"value":{"text":"Inapproximability and polynomial-time approximation algorithm for UET tasks on structured processor networks","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q666411$4E20AF8E-805A-4B39-AADE-B49117A8990E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"069f32fa30649a2cdd4376810fd3e286852a143f","datavalue":{"value":"1233.90149","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666411$1D5D0287-55F3-4ACB-A3EC-292BE3BFE3E8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"090959a37d507661522802ddde716440644cde96","datavalue":{"value":"10.1155/2011/476939","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666411$4C59B302-5893-4248-908B-3475D56FF339","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c90045b28e6ad989f3a861522b4089c286c055dc","datavalue":{"value":{"entity-type":"item","numeric-id":260266,"id":"Q260266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666411$3439F5CC-FB9C-41BE-B27E-F340517A36BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ef4ef0556cf02cf317da9cc594ea9b60e45a45a3","datavalue":{"value":{"entity-type":"item","numeric-id":442399,"id":"Q442399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666411$9153EE1F-577B-497A-AC92-0C07C2B97C1D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"76a9d9a0baf762804f757cc839f33fba5b98847b","datavalue":{"value":{"entity-type":"item","numeric-id":447553,"id":"Q447553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666411$5DB39DD0-2BC4-44F0-AACE-DD861EAFF6B1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"086baaac6cfff2b3761aa8ffbeed776449d2b918","datavalue":{"value":{"time":"+2012-03-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q666411$F431F26F-61E5-4351-9FCA-D988BC68111A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"691ee43b21358306ff1b92a8236851ceae42c19a","datavalue":{"value":"Summary: We investigate complexity and approximation results on a processor networks where the communication delay depends on the distance between the processors performing tasks. We then prove that there is no heuristic with a performance guarantee smaller than 4/3 for makespan minimization for precedence graph on a large class of processor networks like hypercube, grid, torus, and so forth, with a fixed diameter \\(\\delta \\in \\mathbb N\\). We extend complexity results when the precedence graph is a bipartite graph. We also design an efficient polynomial-time \\(O(\\delta^2)\\)-approximation algorithm for the makespan minimization on processor networks with diameter \\(\\delta\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q666411$3D17F8D8-9995-4CDA-98FE-9624C45001B4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666411$0B4E1B03-BB68-4CD2-ACCE-5FF0938C945A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666411$349F3E2F-C236-4A1C-AD7A-22DBD3C056BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666411$C84B3CA5-C92B-4F44-B731-0225FE90E367","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666411$29B7BF54-3704-40B3-B633-B1F26B2D7709","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"50ee2ed84bdaed509685d7df22ecf9a1cc3946e2","datavalue":{"value":"6013014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666411$DA214F74-38DD-43F3-AFE8-CFE983A4F508","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"3189a8c1b10f1f19885acb178334d91e3e32763a","datavalue":{"value":"Q58655028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666411$5DBC5ACC-D0F0-4A4D-8C2F-A31BC9E5786F","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":"Q666411$ED4DB39A-2CEF-4527-B1B2-5C9B11F8734C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"15b9ff4f95918e63a979847c7fd865076963934c","datavalue":{"value":"https://doi.org/10.1155/2011/476939","type":"string"},"datatype":"url"},"type":"statement","id":"Q666411$BDE05BC3-650B-472A-983C-CE95B978FA8C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"be8a3328736aafff3ea680f84185045d90fc9b2c","datavalue":{"value":"W2062851876","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q666411$26DA9325-A76E-4C28-8991-534229C9B61F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"206aac1fed08722358479159401448a8a87bf332","datavalue":{"value":{"entity-type":"item","numeric-id":4198327,"id":"Q4198327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666411$88A2D14E-40A8-463F-BD17-5D9803DEF98C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5dfbb819989e8c5db44d168fc79d8e8eaa7beaf4","datavalue":{"value":{"entity-type":"item","numeric-id":538278,"id":"Q538278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666411$652287DB-CE58-48B2-8D2C-8F6DD136F9F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7997070a1c112421aedb4a6fe3e0ab6e457a4fde","datavalue":{"value":{"entity-type":"item","numeric-id":1097163,"id":"Q1097163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666411$BCF693E0-C53B-4BFB-B7AC-ECF02E3EB987","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0cc81bece6da747b36cdb6e5a08a24517f9d2329","datavalue":{"value":{"entity-type":"item","numeric-id":3833608,"id":"Q3833608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666411$3497256C-B6EA-4A2F-AB57-817FCD3DC51C","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":"Q666411$B8C5B3C3-DA24-45DB-9692-61C0F7732BD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4c5f093fa06bb0de8a4291d6e4bcd8d95d5647b","datavalue":{"value":{"entity-type":"item","numeric-id":4367272,"id":"Q4367272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666411$E806CCFF-6B58-4ECE-ABE8-E9C272C2A57C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e5a7838c67bfd718bcbf45dfe9d3ceed099d43b","datavalue":{"value":{"entity-type":"item","numeric-id":935152,"id":"Q935152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666411$4665BBFC-E70B-4DFE-B932-D448BAF1DFCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4077de5ad21c6b78a25ec43c56119974484a370","datavalue":{"value":{"entity-type":"item","numeric-id":4401551,"id":"Q4401551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666411$D6B719C8-7A2B-49F3-9F21-D41AB31C819F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"061885fa573451da1302a78a271f913f69225f7d","datavalue":{"value":{"entity-type":"item","numeric-id":3249327,"id":"Q3249327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666411$E1892DA5-B381-4ED9-A434-28A19D9F22B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df399851d600f5fc66b83855263f74637e3a379d","datavalue":{"value":{"entity-type":"item","numeric-id":5555416,"id":"Q5555416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666411$E56DBD16-D3C3-4DDE-8114-522B3E01FBB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18c98e9ef2824d2bda99fd0c3e53923a2207a9e6","datavalue":{"value":{"entity-type":"item","numeric-id":5929309,"id":"Q5929309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666411$ED7A95A1-93C7-4F00-AFD3-EE0F1B6A86D6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbd60159d8789736969f7aafc3b65862aafe45f0","datavalue":{"value":{"entity-type":"item","numeric-id":538278,"id":"Q538278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e7cd1995de8eebe7f194ccd7f543c5cff655532","datavalue":{"value":{"amount":"+0.8679105639457703","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q666411$D42990FC-E523-460F-BCFC-D4CB3DFD8FE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b02ba77168360f9e18c8d9d5a71281ce36f383f","datavalue":{"value":{"entity-type":"item","numeric-id":2893338,"id":"Q2893338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7daf384c4ac591da4a8de179a18b662a4bb1972a","datavalue":{"value":{"amount":"+0.8504951000213623","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q666411$C176EDD6-0E28-468F-8875-5D28226F4116","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19cebf1ed634bbd194fd910c9a2aa681cf7e6db6","datavalue":{"value":{"entity-type":"item","numeric-id":935152,"id":"Q935152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0280255a6fc898ee31c9937bb81cbd7f0bad1f9","datavalue":{"value":{"amount":"+0.7980748414993286","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q666411$E6848A91-EFCF-4FA4-8047-226519D8D3BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d7c332b45ade2df2bce71b6e31d379d29141270","datavalue":{"value":{"entity-type":"item","numeric-id":880503,"id":"Q880503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ba2058f408e53eac82c9f8cb38e9f1745a3e13b","datavalue":{"value":{"amount":"+0.797874927520752","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q666411$D432476C-83EA-4C4E-BA89-DBF8CB8EB214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa5db80512481995457e43092f0802745f3fd17b","datavalue":{"value":{"entity-type":"item","numeric-id":3148374,"id":"Q3148374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3745f0c5dc6532751892b706f68ced058c416e7","datavalue":{"value":{"amount":"+0.79486083984375","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q666411$09B8AAFB-18DD-4BBE-BAFD-D419CF22B214","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q666411$32B55ECC-3BF7-47C3-B56B-0A678D25A703","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Inapproximability and polynomial-time approximation algorithm for UET tasks on structured processor networks","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Inapproximability_and_polynomial-time_approximation_algorithm_for_UET_tasks_on_structured_processor_networks"}}}}}