{"entities":{"Q1932452":{"pageid":1943194,"ns":120,"title":"Item:Q1932452","lastrevid":73054620,"modified":"2026-04-14T09:58:50Z","type":"item","id":"Q1932452","labels":{"en":{"language":"en","value":"Faster optimal algorithms for segment minimization with small maximal value"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6126902"}},"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":"Q1932452$995426C8-9EED-46D2-B884-81C8F4554C7E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"68e87f2a2908be6e6871b039534f7f9e3ef60589","datavalue":{"value":{"text":"Faster optimal algorithms for segment minimization with small maximal value","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1932452$3417296C-CFC0-406A-84EB-D8929AAE498D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"17c67b95613d02714a5d3d41abac80c80727a329","datavalue":{"value":"1260.65043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1932452$1E9780F6-8F57-4410-BC32-D7AACB5CB770","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3e9bd1bfb140e662e6ea0631b6d3b66c5e782e0","datavalue":{"value":{"entity-type":"item","numeric-id":181833,"id":"Q181833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1932452$5990F13D-4569-433C-9A77-B8782C71DA0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fe1818fc3bc607033158b45b1bc7724d6c22ae86","datavalue":{"value":{"entity-type":"item","numeric-id":411239,"id":"Q411239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1932452$0E644841-275E-4350-BA26-726FFBFAD886","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6be138e27f4fbac72f6efdc6dc3eb9c65525ae8a","datavalue":{"value":{"entity-type":"item","numeric-id":210516,"id":"Q210516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1932452$AB4748B9-7593-419F-9D4A-3950636EE16C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"17e2018872af8525749d66fbc86c40480c09f876","datavalue":{"value":{"entity-type":"item","numeric-id":644798,"id":"Q644798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1932452$5050B357-FB10-4ED9-8D6E-722F8DB44877","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8be65cd66158c7fd5243610acab29184eef6acf8","datavalue":{"value":{"entity-type":"item","numeric-id":293200,"id":"Q293200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1932452$C9D1839F-EB1A-410E-96BA-A887B8586CAC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1932452$EF20FD51-4659-483E-8BCD-CC239A00050D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"79256387aebd47d6a8dc87509032c2f4d5e302a3","datavalue":{"value":{"time":"+2013-01-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1932452$16E3F5B6-79D0-40FB-8CD7-8F99E61CCE79","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"973bac54f7fc3073f26012cdcd9262461bbdd9f7","datavalue":{"value":"Let \\(A\\) be an \\(m\\times n\\) intensity matrix of non-negative integer values, whose entries represent the amount of radiation to be delivered through the corresponding bixel. In the special case where the largest value \\(H\\) in \\(A\\) small, the authors provide a fast exact algorithm for the single-row segmentation problem in \\(O(p(H)Hn)\\) time, which is polynomial in \\(n\\) as long as \\(H\\in O(\\log{2n})\\).  Three important results are: (a) For general \\(H\\), a new algorithm yields an optimal solution to the full-matrix segmentation problem in \\(O(mn^H/2^{(1-\\epsilon)(H-1)})\\) time for an arbitrarily small constant \\(\\epsilon>0\\). (b) For \\(H=2\\), the full matrix problem with only entries in \\(\\{0,1,2\\}\\) can be solved optimally in \\(O(mn)\\) time. (c) For general \\(H\\), the new algorithm yields an optimal solution to the full-matrix lex-min problem in \\(O(mn^H/2^{(1/2-\\epsilon)(H-1)})\\) time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1932452$946C99FF-9CE4-4D8D-AF8D-182A382D7847","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"dc96a1185c6ca67e17a98fbcdeda0f9aa229d3da","datavalue":{"value":{"entity-type":"item","numeric-id":402309,"id":"Q402309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1932452$CCF49322-E2F5-42D7-BF1B-8C4B6DDC2D11","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"604ac8781f7a7e53df7c131899440e555403be58","datavalue":{"value":"65F99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1932452$36305FD6-94B6-440F-8E56-5D121BBB2013","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e27beffea4779e8a96e7c5961e8cc7879483d808","datavalue":{"value":"92C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1932452$E18FBD13-5748-4B5E-881A-56AC3104AFD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"379993e49d6b3bf4f928ea97a76d4470fec7f1af","datavalue":{"value":"15B48","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1932452$87CFB116-3D75-4E57-AA85-19E6A82354CF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7e47a0160ae69e049345b1d49028d63147565f34","datavalue":{"value":"6126902","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1932452$80AF6051-8044-4328-A11F-AA0C151F5249","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f19c19fba6bbd024a1b736afc45725e70b5f4f51","datavalue":{"value":"intensity-modulated radiation therapy","type":"string"},"datatype":"string"},"type":"statement","id":"Q1932452$F070D934-1238-45D9-875E-E758BD911C80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f84da733a6bf16e8ab1471ad673f55c94eafd5ca","datavalue":{"value":"multileaf collimator","type":"string"},"datatype":"string"},"type":"statement","id":"Q1932452$5CF76AB7-3F19-43CA-A960-06AB4F0BCB8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"844c94882a3ce55880273c71f55e658bbc01719a","datavalue":{"value":"segmentation problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1932452$8FD46AEE-49F8-48FB-B025-EFA20A32DB01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1932452$B72549EF-DDDD-4ACE-88D7-73EA66171538","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"43fb634d93dff9dc968a18a83c4675059a192e88","datavalue":{"value":"nonnegative matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q1932452$C94C95C1-D322-481A-8F7F-FFEF5E031C79","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":"Q1932452$09662C41-6D85-441C-BD92-7B14CF6F3EA3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f22818e168ef73b4ff3577066e0b4e386457e7cc","datavalue":{"value":"https://doi.org/10.1016/j.dam.2012.09.011","type":"string"},"datatype":"url"},"type":"statement","id":"Q1932452$1120A77C-8E01-4E2A-A4B5-AC9F198A27A0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f0bbc39a0d83fd919d2ecbb43b9a948def9af8f7","datavalue":{"value":"W2066511028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1932452$78765082-6256-47C4-B8A4-1AB86C7E8537","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8cd1a6f254c9fe42ca6c84c1cb9f438bad7842a1","datavalue":{"value":"10.1016/J.DAM.2012.09.011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1932452$CFE9DF1F-E498-49AE-889E-8BBAC31928CC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b0f3d8cfb6d64c34dec8d36fc87325b7ec44a7d","datavalue":{"value":{"entity-type":"item","numeric-id":5199233,"id":"Q5199233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c621f170a523f8578b29b3f44bd4b76bf8716048","datavalue":{"value":{"amount":"+0.9868454933166504","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":"Q1932452$18EF5710-0B70-41A1-A49F-2FC1C5D9CC16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4bfb15aa686a2c9a98cc557c6e27b27c0980832d","datavalue":{"value":{"entity-type":"item","numeric-id":845938,"id":"Q845938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbeadf6b8c53a606dfa42e6219022790f70b3edc","datavalue":{"value":{"amount":"+0.8153798580169678","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":"Q1932452$A59A5DA5-29D6-496C-903E-E195D0870B34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60908d310bd1bfe0e2000bbeb43c2f3ecfb19ac1","datavalue":{"value":{"entity-type":"item","numeric-id":1944893,"id":"Q1944893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15d4e1196d0f420d1eb75ec5039bedf90ef45153","datavalue":{"value":{"amount":"+0.8058070540428162","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":"Q1932452$77A0C85F-83C4-4325-B534-6DB75DB629B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51bd9b320b195e14aa1f8cbbf5d914ab78713fc4","datavalue":{"value":{"entity-type":"item","numeric-id":4924115,"id":"Q4924115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be70995f2ee4a9c0d4f2a9c9b2f2f449be5b3fae","datavalue":{"value":{"amount":"+0.7746403217315674","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":"Q1932452$80C7E6D9-4AC1-44A4-A9EF-15AEAFB17D88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e257a9a0e67292318cb47f068637bee1d088d33","datavalue":{"value":{"entity-type":"item","numeric-id":3595380,"id":"Q3595380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f1f873a814d1ca5adb12cb586d4dcdaa705020b","datavalue":{"value":{"amount":"+0.7735465168952942","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":"Q1932452$8834E9AC-47AA-4E45-930F-540C06212D38","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Faster optimal algorithms for segment minimization with small maximal value","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Faster_optimal_algorithms_for_segment_minimization_with_small_maximal_value"}}}}}