{"entities":{"Q4229405":{"pageid":6259006,"ns":120,"title":"Item:Q4229405","lastrevid":46633662,"modified":"2025-12-25T07:30:00Z","type":"item","id":"Q4229405","labels":{"en":{"language":"en","value":"A Constant-Factor Approximation Algorithm for the Geometric<i>k</i>-MST Problem in the Plane"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1252568"}},"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":"Q4229405$FD204C70-66C2-47B6-A2FE-F2E47BD7FBD9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3d020376e8528a7ad2eef1a77be8126fb94990e3","datavalue":{"value":{"text":"A Constant-Factor Approximation Algorithm for the Geometric<i>k</i>-MST Problem in the Plane","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4229405$BB459B68-BC1E-45C7-9664-20DC6E1D3A18","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3d5792b50d32b73536e5853d46ba67528e38ada0","datavalue":{"value":"0918.68045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4229405$7C81631D-7FF9-472B-B8FE-E7EFBBDEBBB8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"403bce3c6f40856936cf774d3cd862b176839206","datavalue":{"value":"10.1137/S0097539796303299","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4229405$2E234ADA-C594-4044-9E0D-F46DF140F1F3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"58051942065352f1019453b7eb1d17c25a542cb8","datavalue":{"value":{"entity-type":"item","numeric-id":244519,"id":"Q244519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4229405$388F759C-F802-4C91-A1FE-138003BDD075","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7e40e731616c4777b7737f0bcc6c9eae91f21b36","datavalue":{"value":{"entity-type":"item","numeric-id":375472,"id":"Q375472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4229405$5B7F14F2-0BFC-45BD-AE52-2CD386440D56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"101ae1bcc09211073cdb7a91c130563a798d619f","datavalue":{"value":{"entity-type":"item","numeric-id":1127356,"id":"Q1127356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4229405$5D276FD8-CF71-4512-BCC1-E4F323BACF31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0b69652026ab5cd3403f51ea14f724a8b3ebf94","datavalue":{"value":{"entity-type":"item","numeric-id":298157,"id":"Q298157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4229405$A268230B-FC33-487E-829D-148ECFF90A54","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2a1c45d0f0997786c62faf9f7fcd603424632e8","datavalue":{"value":{"entity-type":"item","numeric-id":84798,"id":"Q84798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4229405$8B4A5289-064F-4F04-A8A1-7C70B4EE698A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"51f6e9accdba24089d0af8ad200c252ff2ed2384","datavalue":{"value":{"time":"+1999-02-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4229405$00B4A8CF-7DD4-4F3B-AE64-053835B6FC72","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4229405$1D02788A-1DA8-4C38-BAF7-BE4033FA27DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4229405$489CDFC7-4D69-4218-853A-DD99EDA67D3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4229405$85E65185-7A75-4C2E-85A1-525B46F0EA03","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8b1d6bcf2d2ad7dd2cba43d56d2661a78907b5c6","datavalue":{"value":"1252568","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4229405$7222E98F-9B1C-4462-BEAD-D4C55A827640","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"930816699e323987bf987f4de63664e42a9aab61","datavalue":{"value":"minimum spanning trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q4229405$4EA65DF1-6424-4EB9-AF48-8B1438DCA8EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0824f119365205472fb62774c68d0c8925c4cf9d","datavalue":{"value":"\\(k\\)-MST","type":"string"},"datatype":"string"},"type":"statement","id":"Q4229405$4DC8873C-1AEC-493D-9755-5AA5BB62AD93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"137f411028c0db4dac8369de614360d016fde538","datavalue":{"value":"guillotine subdivisions","type":"string"},"datatype":"string"},"type":"statement","id":"Q4229405$12418BD2-B360-4C9E-83EE-18952CA2EDA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7a4a184683bc0d90a86f1bebac907dedfeae015","datavalue":{"value":"quota traveling salesman problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q4229405$58CBD08F-47E8-4443-9B72-21B3C733A36F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0fa5611503d95b47eddbebd26f4ca2d4ef2dbdf0","datavalue":{"value":"prize-collecting salesman problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q4229405$0B66DC73-B6D9-4A78-848D-7ECEB2BAFF89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2562b25e25d1e671f78f509457b3128466c70891","datavalue":{"value":"bank robber (orienteering) problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q4229405$E619A7CC-27E7-4C47-8B20-C860D448A4ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8ee5ef508667994dc3d48d2c52caeaa576e6d96","datavalue":{"value":"network optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q4229405$E4531960-0BC0-4A92-89DF-33C796C01BCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q4229405$6F75A93A-A281-45EC-8AB2-D42E6268BF68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d82cfa81638332a8c825bcbbd9d7f7f9c0c45be","datavalue":{"value":"dynamic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q4229405$3C5F17E4-BC1D-4256-9B7D-E0702AD8D27A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"013fc252e81b7bc701b6cba3363cf82f3cf35053","datavalue":{"value":"approximation algorithms polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q4229405$98B31279-263B-4A79-BCAC-7A565140CC7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6298d726c933840c3a6c7f1f6c7a1542c6c1f451","datavalue":{"value":"guillotine","type":"string"},"datatype":"string"},"type":"statement","id":"Q4229405$01912679-D98C-406B-A714-0EC02FA62EC6","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":"Q4229405$8CC26D97-A65E-45CE-BBB7-23312EB3D619","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9db4ac1169e0c9d2cd18451b945f8d645aa7edea","datavalue":{"value":"https://doi.org/10.1137/s0097539796303299","type":"string"},"datatype":"url"},"type":"statement","id":"Q4229405$588F02DD-0AE0-4DD9-8854-327DF8CD75D1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0115e23b22cfca46d68dc9957a6eb52fc148cc78","datavalue":{"value":"W2017698201","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4229405$755B4297-23CA-4B49-8A67-4AC3555D1E48","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f9d74be115085c0f7f6893df98b11386afee1e0","datavalue":{"value":{"entity-type":"item","numeric-id":4875213,"id":"Q4875213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ccb318fd8761da4cac815f56ba7814daa89944a5","datavalue":{"value":{"amount":"+0.9513235092163086","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":"Q4229405$1D4DC5C9-9A8D-4896-9173-EF8E0E80A6CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9afe66ef57c66bbb6a8df7fcc00266e759e6d78","datavalue":{"value":{"entity-type":"item","numeric-id":4268710,"id":"Q4268710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a172a27bdb5dee7cb4b06e8bb6cafce25b4f2598","datavalue":{"value":{"amount":"+0.8763381838798523","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":"Q4229405$D473651B-142E-4BCD-A40A-D537E2EF9D10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8629e6e3351e7841888bc00cb40bccdc3440cab","datavalue":{"value":{"entity-type":"item","numeric-id":4234076,"id":"Q4234076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a8d7821fbb4cc9e63626418c459afa10a5e4873","datavalue":{"value":{"amount":"+0.8684682250022888","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":"Q4229405$92A5C1AD-BE25-464B-8A2D-A8F7BC418DFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0116b51a9b85143690b72313010b04549fa25d25","datavalue":{"value":{"entity-type":"item","numeric-id":1305925,"id":"Q1305925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94ad33994680f99eef40cfabbecc11e41b5a6216","datavalue":{"value":{"amount":"+0.8189895749092102","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":"Q4229405$2CAB199B-F94B-454A-8B12-22765033FBF8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4229405","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4229405"}}}}}