{"entities":{"Q1593534":{"pageid":1604274,"ns":120,"title":"Item:Q1593534","lastrevid":67940832,"modified":"2026-04-12T20:22:10Z","type":"item","id":"Q1593534","labels":{"en":{"language":"en","value":"Approximability of hard combinatorial optimization problems: an introduction"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1554229"}},"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":"Q1593534$F2EE032A-16E0-4A1E-8496-12F1435374BE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cba009f6909136bcb94df8d288f4825dccbd82b0","datavalue":{"value":{"text":"Approximability of hard combinatorial optimization problems: an introduction","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1593534$386F22F8-4028-4177-88F3-05738EC70CFA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ef458e6c69ae70ea8879fec5c60e574408b41940","datavalue":{"value":"0997.90069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1593534$7A385BD9-3CAA-42C1-B553-9B76612DABCE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6d6ff9dab468d97c714f8acbc796728f1e731a63","datavalue":{"value":"10.1023/A:1018987015651","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1593534$5B450E0A-ECEE-4D59-9C2A-A6011760B750","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9ca552b5a09a951163fe2671a2056a7d7d226e25","datavalue":{"value":{"entity-type":"item","numeric-id":496638,"id":"Q496638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1593534$BCB8D486-E82A-4611-8CBE-EFA25D90EEFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8e8a4cbafc5130c02a2279bc0001c65082f6c60c","datavalue":{"value":{"entity-type":"item","numeric-id":496636,"id":"Q496636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1593534$F4F7E8FB-B8F4-431C-BBCF-4D6E59031698","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8f57d1123ebbbd10d621b3552a672e7729202712","datavalue":{"value":{"entity-type":"item","numeric-id":59875,"id":"Q59875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1593534$9174E6EA-3EB4-4591-A671-C708E7DB23C3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3592adebaf5375a0aca8d0c2df6b20cb85499565","datavalue":{"value":{"time":"+2001-01-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1593534$A47D0ECF-19A6-4A1B-8EF7-260966C53878","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d161a95d628b1b5e45188dfe649bc361b44dccb5","datavalue":{"value":"Most combinatorial optimization problems are NP-complete, and therefore in practice approximating methods are impotent. In this introductory survey the authors follow a historical path up to more recent developments in the theoretical characterization of approximation classes. The reader must be familiar with the main concepts of NP-completeness.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1593534$0913AF07-E9D1-4139-B6FD-52A2B6F0914B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1593534$50C5A2FB-3E63-4548-8BB4-B6851FF4A40B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1593534$1006BB4E-DCA9-48BC-9CF6-3D02BBB0283F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"65ea4544be56ff9a7a06f4c627f7a244e0c10e91","datavalue":{"value":"1554229","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1593534$504B2A4E-BBF2-4DCB-9404-88C349E0264D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a65cc46adc318e4042bf16d3974c1ef4b35a8e98","datavalue":{"value":"combinatorial optimization problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1593534$31C3A383-BAB1-425B-BD63-E6B25AEBF8DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bb8bb734139f668a840f28123c57e59537738dd9","datavalue":{"value":"introductory survey","type":"string"},"datatype":"string"},"type":"statement","id":"Q1593534$1ADB01A3-18C7-4B5B-BCBA-93E2C69A0453","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1fbac784d5822f1841542a4d350e1eb2210ae62","datavalue":{"value":"characterization of approximation classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1593534$5FFE793E-81D3-4B4B-BF2A-1FDF79158E55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1593534$4AE716C6-2776-4F26-AA28-9BD5CAFC48AA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a045f63318f1de593d90eef7099e020a13de6579","datavalue":{"value":{"entity-type":"item","numeric-id":593501,"id":"Q593501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1593534$0B55691C-0E8B-467F-90B7-5A89B5472E06","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":"Q1593534$C204C265-0218-490B-A3B2-063BEAA28DF2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fed412b06a1691778eb4d4a0ca740216772ebe26","datavalue":{"value":{"entity-type":"item","numeric-id":3059320,"id":"Q3059320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4dd2fd9dd6e7b538dd815869745f098217a9026a","datavalue":{"value":{"amount":"+0.8574222326278687","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":"Q1593534$0F54CFB1-FE5B-4D3C-B2B4-54978F225375","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5461d59b3ce0f5e6c2075b3fabd9117b897a572","datavalue":{"value":{"entity-type":"item","numeric-id":4258216,"id":"Q4258216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed1da4a3ccc6d4a1b9821658687bd0815634ac79","datavalue":{"value":{"amount":"+0.8391240835189819","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":"Q1593534$9F22DC25-2416-458E-BBCB-F3B063AE1000","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70204bee0f40291be8c196d40a5be7a9ccb5febe","datavalue":{"value":{"entity-type":"item","numeric-id":672315,"id":"Q672315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed1da4a3ccc6d4a1b9821658687bd0815634ac79","datavalue":{"value":{"amount":"+0.8391240835189819","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":"Q1593534$A49D7B73-6DB8-43CF-93AF-693050B3B526","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06217e9fc4fe3832d30ecdacfa592c3f5161348a","datavalue":{"value":{"entity-type":"item","numeric-id":4407450,"id":"Q4407450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33ff02fd8e1ace83ec351be229d51693e687f468","datavalue":{"value":{"amount":"+0.8366780877113342","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":"Q1593534$53C7353C-A8B9-4F7E-A1E2-1C6F2EB869CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"800fa30514a24f8fec61c4d7fc3353cc17601ef2","datavalue":{"value":{"entity-type":"item","numeric-id":4864960,"id":"Q4864960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7252e759ebcf1ccab6dcf77a2374c1a435ee5b9b","datavalue":{"value":{"amount":"+0.831652045249939","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":"Q1593534$2C04892D-A469-4C78-AEAA-CBAD0C2DE868","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Approximability of hard combinatorial optimization problems: an introduction","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Approximability_of_hard_combinatorial_optimization_problems:_an_introduction"}}}}}