{"entities":{"Q1186548":{"pageid":1197297,"ns":120,"title":"Item:Q1186548","lastrevid":46252510,"modified":"2025-12-24T10:03:46Z","type":"item","id":"Q1186548","labels":{"en":{"language":"en","value":"Optimization, approximation, and complexity classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 36797"}},"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":"Q1186548$4A600508-80A6-424D-9F49-5FA38FA768AD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7fc44b6bb50f743a998b8ed87a80b7cab779c7db","datavalue":{"value":{"text":"Optimization, approximation, and complexity classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1186548$6055A55A-C3CF-491D-93E8-E61A0E8CDBAE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3cc75606fa4f22df6378b98876973514cfb5d7dd","datavalue":{"value":"0765.68036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186548$A6E60DB9-8BF6-4074-82A9-5BFF99FEB5C6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"496e8752fd0b62010762b9e2ba94e908f83707cd","datavalue":{"value":"10.1016/0022-0000(91)90023-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186548$F9A5F095-55DA-4B81-9990-2A1366F16B40","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4703623e4fcbefcd3931d7b75f8faed8c58b1ed6","datavalue":{"value":{"entity-type":"item","numeric-id":222484,"id":"Q222484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186548$14A9783C-5CA3-4EB7-81C1-EDDFF48180AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"64789e48fd3ab0a44b5ae0aa6d85c1c024312026","datavalue":{"value":{"entity-type":"item","numeric-id":458479,"id":"Q458479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186548$382C7989-8B4B-43F8-B950-99CAE964D4FC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186548$F2F62974-A765-4CBC-9490-B88280F57EEA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1186548$3DE6DFEE-C884-4B01-AEA3-580422A59BB3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1536ed7ce4dc46cd6dd25075345c61243206921f","datavalue":{"value":"The authors introduce a complexity class, called MAX NP, which is a variant of NP. They define also MAX SNP which is a subclass of MAX NP. These are classes of optimization problems that contain many known and well-studied problems. The main result of the paper is the proof that problems in these classes can be approximated with some bounded error. Additionally, the authors show that a number of common optimization problems are complete for MAX SNP under a specific transformation, \\textit{L-reduction}, that preserves approximability. It follows that such a complete problem has a polynomial-time approximation scheme if and only if the whole class does.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186548$FB9B31A4-55F7-4F20-A143-C1EDE0B0AB4A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186548$D8A57A19-B5C9-4D52-9844-66E429F9F10A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186548$BA303613-B8BA-4795-90D2-DB7799C70E51","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"033cc532fcb5c91431f7d7a15ea6c69d96191b0c","datavalue":{"value":"36797","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186548$5459C2F7-956E-4423-B0BF-3F1F6A5F1B40","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"721934b7d863ae9f04189d150896700b508e84db","datavalue":{"value":"MAX NP","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186548$8677CAB3-4638-4DAE-8ADF-F12B6F251A99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7bd728f9a35cc4d97b5cbdc4db7f9ca70822fe28","datavalue":{"value":"MAX SNP","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186548$21EBD2FF-21B0-4C50-83AE-86BE8890D1FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c27024bc3112e6fbf1cca0a9a4aacb8e7e4a77e0","datavalue":{"value":"optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186548$5F128928-0CD8-4BFB-8789-5DBCC6E34177","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"762537bc50f732e72b5a90a6c8258b47ac0f486c","datavalue":{"value":"approximability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186548$4EDA8CF3-C2B0-4DDF-8EA2-BEB2FA40DD51","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c5bd3c1f398eb3bf06a0af243f0673a8a59d7bf9","datavalue":{"value":{"entity-type":"item","numeric-id":240126,"id":"Q240126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186548$A414011C-55A1-456C-9721-8CAF493333FC","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":"Q1186548$A8951EC9-C3A5-4C0B-8856-8F66610253D1","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"3434d976ad39f28ffba49fca3d990113aa47d538","datavalue":{"value":"Q89894956","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186548$B3BD24F3-DB51-4D45-BDBE-62594E4C2610","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9dc4dc8695aaa4d0ec31340b16f1901c662b5229","datavalue":{"value":{"entity-type":"item","numeric-id":1143173,"id":"Q1143173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186548$62AC12A4-C5DF-40C2-8233-64C98E4C5899","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ed5651e7c87d511d2ce0af1f61c3115ddbea240","datavalue":{"value":{"entity-type":"item","numeric-id":1143789,"id":"Q1143789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186548$87D49DA1-8C3B-489E-A408-159B2321A475","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d065c583efdebca15b3be81cfc1ee4103b8d3a5","datavalue":{"value":{"entity-type":"item","numeric-id":1184733,"id":"Q1184733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186548$577A00BB-67DF-45D0-88EF-38762F4C1307","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef757ecac8e00102e8fe2d81d7657ee3391ff698","datavalue":{"value":{"entity-type":"item","numeric-id":4138187,"id":"Q4138187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186548$6D405A8C-2C3B-491B-9CED-3B8B2F49EA1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0839e7e46510112865b452a6ed8d8dd889a4c60","datavalue":{"value":{"entity-type":"item","numeric-id":4058132,"id":"Q4058132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186548$3DB81FD2-8B00-4011-B5C0-1D211E5DF1E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc4f0630ec86e5a0d3e96a9ce7ec4c2915d07620","datavalue":{"value":{"entity-type":"item","numeric-id":4083458,"id":"Q4083458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186548$01E615D7-BD0D-4AF2-8B3E-6027EE711555","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186548$145B3E38-2720-4277-9A84-8E336AA33037","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a567a0bd5149009c58baa277d371437f0fed769","datavalue":{"value":{"entity-type":"item","numeric-id":1213733,"id":"Q1213733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186548$91FA82FB-4F98-4BF6-A01A-CAF9E5E8E212","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186548$41457708-0866-4AD7-A0D1-DA8B72D70CA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c30f6e432ce9e9ae75031144ac1199e0b83ca0d7","datavalue":{"value":{"entity-type":"item","numeric-id":1107309,"id":"Q1107309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186548$B50B703C-AFFD-4C5B-B3CC-6E29AF70733D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca5090218963f7454eb65bbbfc3a5878c945557f","datavalue":{"value":{"entity-type":"item","numeric-id":4162995,"id":"Q4162995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186548$C9E32C50-FF4E-4202-98D9-85E42BCB0780","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df707866d55069e9c624e86b2f3ac5960ac5212d","datavalue":{"value":{"entity-type":"item","numeric-id":1152215,"id":"Q1152215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186548$92A35695-4113-4332-A90A-EAF53389A3DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf1d594e2a431d0227ff44696f5443cde01152ea","datavalue":{"value":{"entity-type":"item","numeric-id":1148324,"id":"Q1148324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186548$548CBEB7-7ADB-4A4D-A855-7021D9262145","rank":"normal"}],"P1643":[{"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":"b7e66441c9930148c33deb92a0a03f6972017583","datavalue":{"value":{"amount":"+0.8632099032402039","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":"Q1186548$087B2027-6B18-405B-9F00-B3D18258A031","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":"1fbe5a202a7d0908426cff178081b6d61a650c3a","datavalue":{"value":{"amount":"+0.850490391254425","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":"Q1186548$AB0E3DB8-F19A-4E09-9A00-D9A83E1B8DDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3732bd2f6b9128bf923392ffe319ea4be8b3d1a","datavalue":{"value":{"entity-type":"item","numeric-id":811119,"id":"Q811119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"edc5246eea9c45429f93239fdc56e9d1ab697536","datavalue":{"value":{"amount":"+0.8501688838005066","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":"Q1186548$C42A574C-7575-4FAD-8C2C-1955AA026342","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b294d8133ffa9d7f95f4b533aa3d075e3db39c20","datavalue":{"value":{"entity-type":"item","numeric-id":3974859,"id":"Q3974859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"faac989b0dbaecb9c0aad226c9801e2848dbe8d6","datavalue":{"value":{"amount":"+0.8451464176177979","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":"Q1186548$D4711D2C-1505-4DAD-80E1-6D21BD1E49D3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1186548","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1186548"}}}}}