{"entities":{"Q1405006":{"pageid":1415746,"ns":120,"title":"Item:Q1405006","lastrevid":48161173,"modified":"2026-01-03T20:05:59Z","type":"item","id":"Q1405006","labels":{"en":{"language":"en","value":"A (\\(1+{\\varepsilon}\\))-approximation algorithm for 2-line-center"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1970593"}},"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":"Q1405006$2057859B-8B28-4E09-90EF-67B0D32048B3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b9c121d31e89e16bcaa311dfe52729192681fa86","datavalue":{"value":{"text":"A (\\(1+{\\varepsilon}\\))-approximation algorithm for 2-line-center","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1405006$38AF4CCD-C9D5-4537-B828-0FC75A1105DD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"de4ac26473abbb9279a750cfe5f92826f737bb06","datavalue":{"value":"1030.65011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1405006$6DFC8890-619A-486D-9DFA-C79204323252","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ced936e13ac30e79d59404e10f622abe6b97dc1d","datavalue":{"value":"10.1016/S0925-7721(03)00017-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1405006$3E698B27-257E-4223-9E06-AADA5FC115F7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"79065325f346858a7458ab26433a0149340e5bfd","datavalue":{"value":{"entity-type":"item","numeric-id":818651,"id":"Q818651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405006$BC5A3D65-91BB-4E51-89C1-819E0A85AE83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cce85b4d0d7087c3d8e248a5cdb4c3b856fdb3b1","datavalue":{"value":{"entity-type":"item","numeric-id":590541,"id":"Q590541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405006$25485651-3E30-4642-9557-BFD5EECBA761","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"677085c9ad30c4ba084dcc57c056b00b053188fc","datavalue":{"value":{"entity-type":"item","numeric-id":359871,"id":"Q359871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405006$95BD2F7D-FE8F-46A5-8576-9CF1AA36204C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405006$A0BC8000-3960-4D37-A356-F41A9ECE604F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"988a1f1f38c2f749de54c12ebc5774f827c2b17e","datavalue":{"value":{"time":"+2003-08-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1405006$0560F48D-1C04-4433-958B-5B9159705A8D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"eb7dcfa973c842d50395ced2ce1f72e3927f37df","datavalue":{"value":"Given a set \\(S\\) of \\(n\\) points in \\(\\mathbb R^2\\), the two-line center problem consists of finding two strips covering \\(S\\) such that the maximum width of the strips is minimized. Known algorithms giving the exact solution require run times that grow almost like \\(n^2\\). In the paper under review, an approximation algorithm is presented that gives a nearly optimal solution with strip width \\((1+\\varepsilon)w^*\\) instead of \\(w^*\\). The run time of this algorithm is only \\(O(n (\\log n + \\varepsilon^{-2} \\log \\varepsilon^{-1}) + \\varepsilon^{-7/2} \\log\\varepsilon^{-1})\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1405006$28467C51-F498-4846-B335-769BF14356AD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"32393268783de04b6a033f1165b75e03cfd1377f","datavalue":{"value":{"entity-type":"item","numeric-id":234349,"id":"Q234349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405006$0C8573E9-D1CD-4ACB-A3C7-F06ED14A488E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1405006$D1540E50-B30C-4D5C-B45D-5E35F899761A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0fa9ad61912d72647831ddb5bdea546333329d96","datavalue":{"value":"1970593","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1405006$C44AC40D-D2B9-4E4F-8F93-A29C6CD21FCE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"666329e21830069137965155dd28e4fa9e7cab64","datavalue":{"value":"projective clustering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1405006$5AE46ABB-9659-4CB6-A9C2-015649DCA379","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2282135881983829c4e6b6e54060193ddcb6f69b","datavalue":{"value":"shape fitting","type":"string"},"datatype":"string"},"type":"statement","id":"Q1405006$F5CF5FE9-5293-4D9E-9FE9-7C7B366E2C81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5dbf53a56bb147554948ab8fc380d66635f1228","datavalue":{"value":"2-line-center problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1405006$98EBFD87-9678-4367-BE6F-8341B6CD7FA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1405006$D9ECC80F-2D67-4DAF-840A-5EF5B69DD547","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":"Q1405006$822280A8-808C-4552-BDA1-19B33C800AD6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e2aa0fc2d054ebae72b1a4b46cd2c554608432d","datavalue":{"value":{"entity-type":"item","numeric-id":4225298,"id":"Q4225298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405006$9ADF9A22-1CF6-4E0D-960E-03E9E2CE125D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02efe493e96b3f410aa8f54e81db7d857be12013","datavalue":{"value":{"entity-type":"item","numeric-id":4952664,"id":"Q4952664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405006$176D90E3-E405-4541-A83F-0BE350B7DA2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1adb8826d7a2d5023210e842ecd461d425d2cac8","datavalue":{"value":{"entity-type":"item","numeric-id":4411345,"id":"Q4411345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405006$04836B96-F333-4F0E-A551-5ADF21E44C41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6fffda452aa745bf25131b56a0ba54ce76261f2","datavalue":{"value":{"entity-type":"item","numeric-id":1816458,"id":"Q1816458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405006$903B4F13-7036-4B92-A5D9-B3A137D0F57F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"344c5edb3b3479eefbee8591dddd381a97d10507","datavalue":{"value":{"entity-type":"item","numeric-id":5361541,"id":"Q5361541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405006$C7B4E28A-2223-421D-B534-A9511B4F734B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53ec07473fe54967fbac0a909d2dfb2bb633ae39","datavalue":{"value":{"entity-type":"item","numeric-id":5501788,"id":"Q5501788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405006$7C6FB525-A2DB-456A-A4C9-6D6869C7345E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0caf07c9ce1de8dfaf98559b92a8719a93b7ae2","datavalue":{"value":{"entity-type":"item","numeric-id":5057419,"id":"Q5057419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405006$52C34D8A-7EBD-404C-AE64-70C7BD21ABD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e35b334387839cd608a05746f09c54dd778b80df","datavalue":{"value":{"entity-type":"item","numeric-id":3809267,"id":"Q3809267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405006$0330E9DC-F9AC-41B2-A224-24A4E032369C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02b218ec1f10db3babda018bb65a9ba2ef4b77ff","datavalue":{"value":{"entity-type":"item","numeric-id":4527029,"id":"Q4527029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405006$31F0031A-D8F5-4B02-A4BA-846DBE9DEF02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc6885ab94bd355bce42bd5e8356998e647a6282","datavalue":{"value":{"entity-type":"item","numeric-id":5057418,"id":"Q5057418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405006$79BA8A4A-DBDD-43E8-B860-C5DBFF43F2D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc487bd38f7dfd529731251ee850b404f2fc236e","datavalue":{"value":{"entity-type":"item","numeric-id":4327373,"id":"Q4327373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405006$846EFF96-053D-4BCB-9003-F1C73F3C8F72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09abae86cc1ed38b7527e20b0a54f0f51ad25c1f","datavalue":{"value":{"entity-type":"item","numeric-id":1099951,"id":"Q1099951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405006$59A2FA4D-D08C-4B1E-BAAB-B6A760104CC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26736971b71f38c87ce58e186943954df95eb066","datavalue":{"value":{"entity-type":"item","numeric-id":1837617,"id":"Q1837617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1405006$1C3DA737-F86C-426D-AE9B-919DF801988D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01794b15039b928cbdb302b7f40c5798b7013178","datavalue":{"value":{"entity-type":"item","numeric-id":5057418,"id":"Q5057418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"036a6c032bd640ac1f52b94373b11a9473e88bd4","datavalue":{"value":{"amount":"+0.8327562808990479","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":"Q1405006$B3AE7F54-8F81-4FC6-A6BC-892282CB0CA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58df67c68b38f75c1159c11b8d089e5acc986e4a","datavalue":{"value":{"entity-type":"item","numeric-id":6166042,"id":"Q6166042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37e48488810d12a846305e04b3168526e39e09be","datavalue":{"value":{"amount":"+0.8266655206680298","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":"Q1405006$4E8DF0F5-1DB0-4017-971D-D2C3799A683A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"206ef77f4f25a0672e5af8b445db5041ca132292","datavalue":{"value":{"entity-type":"item","numeric-id":4411345,"id":"Q4411345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e53197e3cbf7e4114995623d2da4986a4715352","datavalue":{"value":{"amount":"+0.8065682053565979","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":"Q1405006$572E45B6-781F-465E-9972-B112B949FC0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39c891673bc6ac3bc5dfed15a691484e04b6e1bd","datavalue":{"value":{"entity-type":"item","numeric-id":1364134,"id":"Q1364134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63486a241bb15fdbe1694c99ea41ac3d4a4652f9","datavalue":{"value":{"amount":"+0.8029927015304565","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":"Q1405006$820B1F32-9175-47C6-A6C0-3141B1C5001F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99a1f9cf8e3c07da4624ea42971723118bca199e","datavalue":{"value":{"entity-type":"item","numeric-id":1272957,"id":"Q1272957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63486a241bb15fdbe1694c99ea41ac3d4a4652f9","datavalue":{"value":{"amount":"+0.8029927015304565","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":"Q1405006$853AC64B-5B61-4BC5-A647-76B75EC66612","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1405006","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1405006"}}}}}