{"entities":{"Q5757457":{"pageid":7787008,"ns":120,"title":"Item:Q5757457","lastrevid":50159645,"modified":"2026-01-13T07:35:02Z","type":"item","id":"Q5757457","labels":{"en":{"language":"en","value":"Ruling Out PTAS for Graph Min\u2010Bisection, Dense k\u2010Subgraph, and Bipartite Clique"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5188163"}},"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":"Q5757457$4E66ADEF-C138-4671-8E55-664D69B06210","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ee29b59fa76ffa54603437f08a3e3bd44d884696","datavalue":{"value":{"text":"Ruling Out PTAS for Graph Min\u2010Bisection, Dense k\u2010Subgraph, and Bipartite Clique","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5757457$AA5A7B25-9C4E-4264-A42C-EA81ABD4CB5D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fdcd2d905a3c50be3902e473cfb1e94c16944690","datavalue":{"value":"1127.68035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5757457$83CEFB4A-E3D2-4F7E-A5BA-FDBED280FE42","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"70add28d25fdd49a732032646cc77440b9e07e04","datavalue":{"value":"10.1137/S0097539705447037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5757457$B4A8484F-D861-4965-9490-2AD0E640FA30","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc0f476358ab3d9fa7f8c58db4d920df08a5d274","datavalue":{"value":{"entity-type":"item","numeric-id":430831,"id":"Q430831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5757457$BCA38A48-96DA-4409-971B-335D74CB77D3","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":"Q5757457$383A5730-3E74-4CE0-8ABB-B2D8A5539309","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6a0f126e0f773412df6fca1aea3308e338ba6e0c","datavalue":{"value":{"time":"+2007-09-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5757457$F958FCA8-E6A2-458B-9877-FAEE565EF2B9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5757457$CE2AFD30-2B14-4D54-A4B7-BC8451BEFE4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5757457$01E0BC5D-EF91-4853-8CCF-E0799917F670","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5757457$15014CA0-EB2C-489A-BA13-5F738AAEB1BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5757457$11BB64DF-FD2A-4EF5-B4E7-A939CD33439A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b33627187b56aff90ad3e0feada5ffc8daaec280","datavalue":{"value":"5188163","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5757457$ED305C83-5E49-4856-84C7-9EE5717FA507","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"198526b3e16365d088b0d8e8cb1a48a9c3937632","datavalue":{"value":"probabilistically checkable proofs","type":"string"},"datatype":"string"},"type":"statement","id":"Q5757457$29726B7F-6068-464A-B083-17FE821A9259","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c932864c8d857b058190f9c7572ffef7f1e96210","datavalue":{"value":"hardness of approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q5757457$DA39F99B-77DC-4203-8498-DC25C9D8AA5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q5757457$8385C5AD-A476-4979-B749-AEF9731BC25C","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":"Q5757457$8D29C2DC-6060-4B4D-B109-6FF5D8162BFA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dedc7db549f0adb057e53dd1dc56e6b1c56e30b3","datavalue":{"value":{"entity-type":"item","numeric-id":4234075,"id":"Q4234075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce555516f0c016ac7fcf4e1af8978656d5de46d9","datavalue":{"value":{"amount":"+0.7749267816543579","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":"Q5757457$AB5308DF-497E-469E-A4F9-A628C6A403B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3b4f571f4b589c18fa8f904e281e4cb599eabd8","datavalue":{"value":{"entity-type":"item","numeric-id":3192022,"id":"Q3192022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55c5d4e3ba49d9815947249cb8e0c855b5a0aba6","datavalue":{"value":{"amount":"+0.7638955116271973","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":"Q5757457$030F9EEB-3047-449B-97BA-8F24A6F3D93A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"675f07747bc7bcf2bf7d7be05c1a14b04f08b705","datavalue":{"value":{"entity-type":"item","numeric-id":4417004,"id":"Q4417004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0c8ca11819cb6040f75049cf7435a2e9378bc44","datavalue":{"value":{"amount":"+0.7622044682502747","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":"Q5757457$00C03C2C-F169-4AE6-832F-1B49E1620BEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd916d98900c7fbbe1442ccdd8fe695d7718a0a5","datavalue":{"value":{"entity-type":"item","numeric-id":1305935,"id":"Q1305935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d861bd3cada576b56bd0ee129265c70e894fffa2","datavalue":{"value":{"amount":"+0.7603064179420471","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":"Q5757457$E525580B-6EA9-452C-8D6E-382D774C52C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1c9fae3fbb603373c87d66ca5cfc2eb1bdee893","datavalue":{"value":{"entity-type":"item","numeric-id":3020016,"id":"Q3020016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1527b6c41a168f5ccf4cb9e8eecaf3e07236b3d1","datavalue":{"value":{"amount":"+0.7525894641876221","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":"Q5757457$64339007-1BC6-467C-97F6-E769EAC8D9A0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5757457","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5757457"}}}}}