{"entities":{"Q1106724":{"pageid":1117473,"ns":120,"title":"Item:Q1106724","lastrevid":49193905,"modified":"2026-01-06T18:05:05Z","type":"item","id":"Q1106724","labels":{"en":{"language":"en","value":"Randomized rounding: A technique for provably good algorithms and algorithmic proofs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4062820"}},"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":"Q1106724$8FD6FBE0-45C1-4550-81CE-614B5096E5D5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"482c8fbcf69f39022f81685d76091133fc3a94e0","datavalue":{"value":{"text":"Randomized rounding: A technique for provably good algorithms and algorithmic proofs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1106724$F2B444BC-70C7-45AC-842D-CCDEE18866EF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"56727aff8f584b3404696edcb7125fd1c11e5bea","datavalue":{"value":"0651.90052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106724$E0AC9FD2-75F5-4CC1-8677-8849E2AF349C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8d0668a281ac804fba9cf9b9f8646f470f36c8d4","datavalue":{"value":"10.1007/BF02579324","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106724$775E6493-D589-4232-B08B-A92345AA6B29","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106724$D7413C94-E63C-400E-889C-9649A16709F1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1106724$53A034FA-108A-4157-A839-CFDB94A7C9DC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3a36ad7cb7b057a32f0cd08b8c2374a45dcd8b76","datavalue":{"value":"The relation between special 0-1 integer linear programs (routing in VLSI circuits, multicommodity flow problems, k-matching) and their rational relaxations is studied. The authors consider a randomized rounding for transforming an optimal solution of the relaxation problem into a provably good solution for the 0-1 problem. Some probabilistic estimations about the existence of good integer solutions are derived.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106724$C8228669-9F5B-40E8-A378-BD3A48C91261","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106724$2AC17F4E-1107-48AD-935E-1B4C9E09FA07","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5527142b9d303c27e2e28985d1414a635ee2a5c9","datavalue":{"value":"4062820","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106724$06BDBA02-1D47-4333-9075-2BF46A4227C4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aa57c0597b0ebce01e02b26e6cb06919e880e078","datavalue":{"value":"integer linear programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106724$B78C4C77-1279-4907-866F-9A4B78186E3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25f976143d8ee23b08d25ccd2745cac233318864","datavalue":{"value":"routing in VLSI circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106724$CFD1752A-B3E6-4EB4-BD73-2086E33E313D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1fe9a24a5083674e2c7cf820fa90e6f1d7fc564","datavalue":{"value":"multicommodity flow problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106724$51C649B8-7994-4D20-A3D8-FC3B0853285D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"61c80c0981e4f79281f514ef1b62e52315c4acf8","datavalue":{"value":"k-matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106724$33848549-B10F-4D0D-A68F-6BEC3F73F5C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88da40e844424aab6ca4b0ee0dfafbb0ed11aa56","datavalue":{"value":"rational relaxations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106724$F4B9F87B-31CE-49FB-A647-D100EF11A6F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88d4d94e4f7cb04320063f664166fa5ca067fe66","datavalue":{"value":"randomized rounding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106724$E5F31D9A-21B2-44C2-A859-70C43827E8B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b99ceabc8ae8e4271070938d3519095fc4ff047a","datavalue":{"value":"probabilistic estimations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106724$DE123C0B-1C9C-484D-85E5-C3FD6956C61B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3b0fb0f2c86e93cd39417ea5519157255e289364","datavalue":{"value":{"entity-type":"item","numeric-id":222782,"id":"Q222782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106724$FA570657-42D8-4A68-BBF8-6B08DBA7C0F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bb55ae0ce898894c0e343aba3ee3b0699e4bf3b9","datavalue":{"value":{"entity-type":"item","numeric-id":916368,"id":"Q916368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106724$F3FF1CE7-D4DB-4E37-9660-4F4A014FD405","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"428db2522b86322eddab35ce9ee5f612b48777eb","datavalue":{"value":{"entity-type":"item","numeric-id":915655,"id":"Q915655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106724$2701580B-D624-4C5C-BD6E-A4226537130E","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":"Q1106724$FE2781CB-6144-4753-92EC-A6DF2A755FCF","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"e85495373c78a3073b5a70fd607a2e4e334cb82a","datavalue":{"value":"Q29543656","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106724$1DD5FEAF-642B-4CE7-8E9D-D949D7F704CB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"83c6293f25e8bc7e1747aa6978fc2fd52b5104b6","datavalue":{"value":{"entity-type":"item","numeric-id":1141153,"id":"Q1141153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106724$7CD77F60-3F93-47A1-B5B0-F3BF83D3ACBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77d6452e54e5e6983bfa6dba10e55824db2fd929","datavalue":{"value":{"entity-type":"item","numeric-id":5814290,"id":"Q5814290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106724$3102D1AF-83CB-4C5C-9B1C-DFC0489008D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55223ae6f91a9a3c0f6a3be0cfb6236eaf5fcb6a","datavalue":{"value":{"entity-type":"item","numeric-id":4132234,"id":"Q4132234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106724$56F65290-8093-4F78-B1FE-C0B6B0595A64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5670f34f7f97e1f73ed327c2ad2e07b09b07d505","datavalue":{"value":{"entity-type":"item","numeric-id":1168988,"id":"Q1168988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106724$378AC84A-4E80-402C-BBD8-E1AD936C8C27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3aed9c30d7849fd99c487c08d026a8560723c763","datavalue":{"value":{"entity-type":"item","numeric-id":3234917,"id":"Q3234917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106724$E0B88C79-FBC3-4806-83D4-7B71168D2860","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f744b48e1b7262e1ddf22a98deec4513fab3e800","datavalue":{"value":{"entity-type":"item","numeric-id":3710289,"id":"Q3710289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106724$003FF8F8-4666-4051-AB3F-DB37008E590B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0b86da6901907b4b60c4d755cbdefb3d87af7f5","datavalue":{"value":{"entity-type":"item","numeric-id":761967,"id":"Q761967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106724$C783CAB7-3337-4DAF-B9E5-141B6180D4DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8104acbfbcda2b7a64c84031b5436962bb027ece","datavalue":{"value":{"entity-type":"item","numeric-id":1097238,"id":"Q1097238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106724$D88FF7CA-8874-4ECC-A99A-746FE530285F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7db3468346fcce29d2fe703e3816d1c0ffadbf3a","datavalue":{"value":{"entity-type":"item","numeric-id":1224109,"id":"Q1224109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106724$428AC450-C87A-4BC0-9138-03C284B26ABE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f19ad20105c30936c93f5697cec437ce6d4a0cf","datavalue":{"value":{"entity-type":"item","numeric-id":1251587,"id":"Q1251587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106724$72768070-7E37-4AE1-8371-6119EFA0A8F5","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"d4a024f0dab436d0685580beb2533b7df1b2668d","datavalue":{"value":"journals/combinatorica/RaghavanT87","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106724$BED81365-5252-47B5-AAF7-4ECB91C7E5A5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4cdcf97760be1d5b14cad5edd40918c07b0a07ae","datavalue":{"value":{"entity-type":"item","numeric-id":4470513,"id":"Q4470513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1758a8666b70615b5142f2bc8ae0b5c3050ea867","datavalue":{"value":{"amount":"+0.8277354836463928","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":"Q1106724$C8909FEB-CB0B-4A8D-8379-5FA3B0B2206D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"492ddf74b6399b6ec7806bf3655305d04bb40af1","datavalue":{"value":{"entity-type":"item","numeric-id":4938889,"id":"Q4938889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d19769196095122613a793f0fe3f0ba3e937dcf","datavalue":{"value":{"amount":"+0.8147947788238525","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":"Q1106724$7DCD33EA-13E8-47DF-A9D4-AB18B714BA28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef3ac78865e81d1c2ebcafbb54195eb767ea48d1","datavalue":{"value":{"entity-type":"item","numeric-id":4234073,"id":"Q4234073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d19769196095122613a793f0fe3f0ba3e937dcf","datavalue":{"value":{"amount":"+0.8147947788238525","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":"Q1106724$70FDD467-D760-488A-9220-B1CDDA4B6040","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c395bc3a279ed85721affa74e18f7eb61a9e4935","datavalue":{"value":{"entity-type":"item","numeric-id":1306458,"id":"Q1306458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5064a80300bfce9f8fb8ba239a7fe49ed5464ff","datavalue":{"value":{"amount":"+0.8129832148551941","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":"Q1106724$B4875C2A-CB13-4C02-9AE1-9932323F9C57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c1381114207d0ee786b8275925caa56101b9844","datavalue":{"value":{"entity-type":"item","numeric-id":4537626,"id":"Q4537626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b2b023b9ffad7b5d9145725856bf30e6d7ca65b","datavalue":{"value":{"amount":"+0.7867360711097717","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":"Q1106724$54AF59DA-CDD1-45E5-A574-6ACA09D308DA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1106724","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1106724"}}}}}