{"entities":{"Q3020016":{"pageid":3030732,"ns":120,"title":"Item:Q3020016","lastrevid":45267991,"modified":"2025-12-04T00:15:27Z","type":"item","id":"Q3020016","labels":{"en":{"language":"en","value":"Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5934237"}},"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":"Q3020016$AE192AEA-E11B-4920-B819-9B47C2FCD2BE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b9418a53b3befdfb84560308bb902cdc68fcf366","datavalue":{"value":{"text":"Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3020016$2B30E8DE-3F85-4707-8DD3-49B4D8434E02","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cefc57074dea1727ff87b97e22825c282d74d05d","datavalue":{"value":"1223.68043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3020016$DC73DE34-2693-4208-BD0A-3AFF55DAF1BE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"47ff62599c5aae215182421184d0f0a920303773","datavalue":{"value":"10.1137/080729256","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3020016$6DB525BF-403F-4319-B373-0067B97D9310","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8522c9c3dc1d4f5ab36cdb95808d7ec3816cb5be","datavalue":{"value":{"entity-type":"item","numeric-id":486996,"id":"Q486996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3020016$185167DF-242B-4148-9F61-A14DB4F3D82F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"22b7956f6220228fa87c479909ab9136b211e3bc","datavalue":{"value":{"entity-type":"item","numeric-id":613332,"id":"Q613332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3020016$FBC9A0AA-6DFE-4646-8D77-9FAC48DEC98E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"019c683b2b6b2db6399db38cf29dcf5b370a7ec8","datavalue":{"value":{"entity-type":"item","numeric-id":813964,"id":"Q813964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3020016$054DF7E4-9F50-4B49-B064-B7697E75D285","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":"Q3020016$97B4B224-5B09-4EC1-BA8D-6E1B58524205","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d00523700407e21ae71debe0fbbbb012ba59e567","datavalue":{"value":{"time":"+2011-07-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3020016$FDF50C78-AD9F-4226-B1EE-35B7512C3158","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0046b829e4ecd3bf82a203114fae3c785b832ba6","datavalue":{"value":"https://semanticscholar.org/paper/72e02db1c04aacd1821bc54ad599d6ebe2da39f3","type":"string"},"datatype":"url"},"type":"statement","id":"Q3020016$84FF0DB5-F5FF-4648-A2C2-53FA939534F0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3020016$5AF7BDA8-6615-444E-A151-74492F9E72E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3020016$1BA57A74-A59E-449D-94B7-BDEE90869B48","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"33fc0726f8a9acbb8a802a7da86e54f52dd0764b","datavalue":{"value":"5934237","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3020016$5FCC89DC-C3A5-4F46-8D0A-BD55C91CEB81","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c932864c8d857b058190f9c7572ffef7f1e96210","datavalue":{"value":"hardness of approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q3020016$DA162EC8-2684-4C14-B73B-B7584F74ED9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdf4dc3db86d44e89a36d3ec12340c2571d04f06","datavalue":{"value":"graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q3020016$76229D7B-2434-47AA-AC0A-D3E36D5005CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"856690a05efdfc392cd5ef453b524f56674d314b","datavalue":{"value":"maximum edge biclique problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q3020016$1049DF1F-7304-428B-BBE8-D3E065F86DCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf9961407360e96488c01dd0d437e29026c5560b","datavalue":{"value":"minimum linear arrangement problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q3020016$D27AE67C-EE13-4077-86C4-084FD6E19F58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"47707cecca3e9198ba8d22847129e1c614378cd6","datavalue":{"value":"sparsest cut problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q3020016$F9E9F97A-F7C8-4766-8E04-F6B37A906D0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q3020016$7653E060-D12D-47A5-A4D9-ACEBF11F85BD","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":"Q3020016$4A9729DD-9078-473F-BFF9-6D2A2E4653CB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"aef18c4f4eb1d95182ac292f3e1f24909f326759","datavalue":{"value":"W1995472412","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3020016$EA15DAD7-93D5-44AE-BC0C-17CB59D0551E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a64e0489d28426b3513fe6e8386854fd45699b70","datavalue":{"value":{"entity-type":"item","numeric-id":5111410,"id":"Q5111410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49eb957e2a4448991f5a192dca698f5af567c5b3","datavalue":{"value":{"amount":"+0.9264744","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3020016$39417C0C-5083-42AE-B3B0-95D1BD2F147C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"703a4a6fe32bc957386ec7519c9236d30d6a0a72","datavalue":{"value":{"entity-type":"item","numeric-id":3502654,"id":"Q3502654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2905bc3c2037cd5e89563687f969d06275e2c6f0","datavalue":{"value":{"amount":"+0.9244238","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3020016$A951ED90-5C79-47E9-94C1-DDFFCFB62099","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"661fe5f467352728135653b804b7965add820de8","datavalue":{"value":{"entity-type":"item","numeric-id":2633244,"id":"Q2633244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45778226ab56464c30659b71e01ffbe8809df8fa","datavalue":{"value":{"amount":"+0.9144585","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3020016$EAD5C325-AAC2-4671-B63C-671BAC57D931","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70f6a052dc928e891d1ab0b37cf35f9449418333","datavalue":{"value":{"entity-type":"item","numeric-id":5375386,"id":"Q5375386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"712227af60fdfa733fc68ea9f22a44a54b2ac718","datavalue":{"value":{"amount":"+0.888395","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3020016$6F133C9F-5751-4CE5-8822-90C8D4609763","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c472e0d3c8bcd01798e1bfc7da9f6f9aaa231c4","datavalue":{"value":{"entity-type":"item","numeric-id":2085735,"id":"Q2085735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a2f73ce9990ae44ea9c9ea92df4a375d8884fdf","datavalue":{"value":{"amount":"+0.88444865","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3020016$428E983F-40C9-4A8B-81E0-CB2683B2C1B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec9c04dad7177c547580a549a93cf6bc3bcfedfc","datavalue":{"value":{"entity-type":"item","numeric-id":4632171,"id":"Q4632171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d6e0a29e72fb4ca29cd0b4579f86b6748c145ec","datavalue":{"value":{"amount":"+0.87980306","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3020016$DD30BC3B-E2F7-4A3D-A35E-E12492264833","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca38a88a7cbeda49321ae97647d1335a52f93a86","datavalue":{"value":{"entity-type":"item","numeric-id":3434272,"id":"Q3434272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"699d42df32e747c46d2965fd05ad339b9e9d33c9","datavalue":{"value":{"amount":"+0.878704","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3020016$C636A50A-883F-4947-A1F4-17E19D8405BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64612366877e14ef625a35cd545e1e11111e4e53","datavalue":{"value":{"entity-type":"item","numeric-id":873802,"id":"Q873802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86b4f20e5fce56f8e4caaada51220a77ad53c2c8","datavalue":{"value":{"amount":"+0.87736076","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3020016$B3D36BB1-7B26-41C2-91C9-F5FF5CB19865","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb08c0cc10fc3c5b9a54018721a8fb16443e4a9f","datavalue":{"value":{"entity-type":"item","numeric-id":742133,"id":"Q742133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ee0b9d853abe771b14d3793f39534172e64c5b4","datavalue":{"value":{"amount":"+0.8732307","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3020016$D4B13A80-694A-4B1D-BF5B-1F1E3AD2E4F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0e028c9adaee68f8845fc57c25523b8a88f158a","datavalue":{"value":{"entity-type":"item","numeric-id":2467485,"id":"Q2467485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ce410ce8cbb5f6301d1e901693f1cb16a6ddb27","datavalue":{"value":{"amount":"+0.87320006","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3020016$1B798C20-5347-495A-A897-88DA77D3F3EB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3020016","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3020016"}}}}}