{"entities":{"Q555978":{"pageid":557745,"ns":120,"title":"Item:Q555978","lastrevid":62751750,"modified":"2026-04-11T08:13:17Z","type":"item","id":"Q555978","labels":{"en":{"language":"en","value":"Approximation algorithms for NP-hard problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2175109"}},"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":"Q555978$868DCBB5-8040-4796-A841-038885E8108B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"248feb3ee7837b54c3ecf9f0735b15511dab92a8","datavalue":{"value":{"text":"Approximation algorithms for NP-hard problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q555978$7E4BD830-ED6F-4CD0-9F34-C258D61C72C2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"630d1ef4f6d24a6f3539f58692ca8ea169eacb76","datavalue":{"value":"1078.90500","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q555978$ECEF8434-B149-42BF-9201-BA26C01B5D51","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5cd9df1ea94f44497a2fb96e7f3b9808870b37e0","datavalue":{"value":"10.4171/OWR/2004/28","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q555978$854EC234-012F-410D-8903-20E602C353A5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a9abe280024f1bf6d5dacc0d016ddbaccd65fb63","datavalue":{"value":{"entity-type":"item","numeric-id":269669,"id":"Q269669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q555978$C39DE4AA-AFD8-4AFC-8422-7672337ECED8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8f82118ca2793d21263f8941982493899f6fa842","datavalue":{"value":{"time":"+2005-06-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q555978$0741853C-96F6-4B9F-9EB2-667EF3D40515","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5d3c0d5267e36fdc7004a7a2b5fb80a18d55a18b","datavalue":{"value":"http://www.ems-ph.org/journals/show_issue.php?issn=1660-8933&vol=1&iss=3","type":"string"},"datatype":"url"},"type":"statement","id":"Q555978$1974DF76-370C-4288-B52B-35462A61BB9A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"be5d85f9f894346104595b6d152e12ae05113426","datavalue":{"value":"Contributions:  -- Alexander Barvinok (joint with Alex Samorodnitsky), Fast and Crude Combinatorial Counting p.1463  -- Markus Bl\u00e4ser, A 3/4-Approximation Algorithm for Maximum ATSP with Weights Zero and One p.1465  -- Janka Chleb\u00edkov\u00e1, Approximation Hardness of Optimization Problems p.1467  -- Amin Coja-Oghlan, Coloring Semirandom Graphs Optimally p.1470  -- Mary Cryan (joint with Martin Dyer, Haiko M\u00fcller and Leed Stougie), The Natural Random Walk on the Transportation Polytope when the Number of Sources is Constant p.1472  -- Artur Czumaj (joint with Christian Sohler and in part with Mihai B\u0103doiu, Piotr Indyk, and Anastasios Sidiropoulos), Sublinear Time Approximations for Metric MST and Facility Location Problems p.1474  -- Petros Drineas, Pass-Efficient Algorithms for Approximating Large Matrices p.1476  -- Martin Dyer, Counting knapsack solutions p.1480  -- Lars Engebretsen, More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP p.1482  -- Uriel Feige (joint with Shimon Kogan), The Hardness of Approximating Hereditary Properties p.1485  -- Sudipto Guha, An \\(\\Omega(\\log^*n)\\) Hardness of Approximation for the Asymmetric \\(k\\)-Center Problem p.1487  -- Johan H\u00e5stad (joint with S.Venkatesh), On the advantage over a random assignment p.1490  -- Mathias Hauptmann, PTAS for Dense Steiner Tree Problems p.1492  -- Tom Hayes (joint with Eric Vigoda), Coupling with Stationarity: Rapid Sampling for Graph Coloring p.1495  -- Dorit Hochbaum, Transformations to totally unimodular optimizations, Half Integrality and 2-Approximations p.1496  -- Stefan Hougardy (joint with Doratha E.Drake), Approximation Algorithms for the Weighted Matching Problem p.1499  -- Klaus Jansen, Improved approximation algorithm for the mixed fractional packing and covering problem p.1502  -- Ravi Kannan (joint with Noga Alon, W.Fernandez de la Vega, and Marek Karpinski), Random Sampling and Approximation of MAX-CSP Problems p.1505  -- Marek Karpinski (joint with Piotr Berman and Alex D.Scott), Approximation Hardness of Short Symmetric Instances of MAX-3SAT p.1507  -- Michael Langberg (joint with Adi Avidor), On Multicuts and Related Problems p.1509  -- Monique Laurent (joint with Etienne de Klerk and Pablo Parrilo), A PTAS for the minimization of polynomials of fixed degree over the simplex p.1513  -- R.Ravi (joint with Anupam Gupta and Amitabh Sinha), Boosted Sampling: Approximation Algorithms for Stochastic Optimization p.1516  -- R.Reischuk (joint with Jan Arpe), Robust Inference of Relevant Attributes p.1519  -- Angelika Steger (joint with Jan Remy and Alexander Souza), Average Case Analysis: Two Seemingly Simple Problems p.1520  -- Berthold V\u00f6cking (joint with Rene Beier), Typical Properties of Winners and Losers in Discrete Optimization p.1523  -- Lars Engebretsen, Uriel Feige and Johan H\u00e5stad, On three recent results by Subhash Khot p.1525  -- Mathias Hauptmann, Special Session on Steiner Tree Problems p.1526  -- Nicolas Schabanel, Special Session on Near Optimal Decentralized Routing in Long Range Contact Networks p.1527  -- Berthold V\u00f6cking (joint with Piotr Krysta), Special Session on Approximating Combinatorial Auctions without Randomized Routing p.1528  -- Open Problem Session p.1531","type":"string"},"datatype":"string"},"type":"statement","id":"Q555978$157BDA62-4462-4F2A-8775-099DC52E3953","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ecbbf3779c517fef97ab936b0a129d7ef035b583","datavalue":{"value":"90-06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q555978$57DDC20F-E615-4AFF-9046-0C006ECCEF93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9273ee9d6a850a5b4a9f2fe224e0804dc9e99b1f","datavalue":{"value":"00B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q555978$F7702A59-FF72-459A-904C-DC1BA04DA985","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q555978$E4EFA438-5824-429A-B51E-E615750927F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q555978$5CAC2CE8-98B8-41AF-AE70-D2419A2F0AB9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"01db2132a8a5c92774feb5e7b9cc312c43c57930","datavalue":{"value":"2175109","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q555978$A154E97B-8243-46C3-99F0-7884AF26B4ED","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":"Q555978$9E30E0EC-D39E-4D98-AF8F-A83445ECD9D4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c2f3e91c2b5f5b5e1d5430a641959da7405a9763","datavalue":{"value":"W2029830880","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q555978$C913B989-BDA5-432E-8E7B-AB0DE7BEFF47","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6ac43a312a82962d379f9f2c4a738fcd08c18a9","datavalue":{"value":{"entity-type":"item","numeric-id":3002852,"id":"Q3002852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af0b535278e3dbcdb0248adab0ab32ab96f6b2ea","datavalue":{"value":{"amount":"+0.9708849","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":"Q555978$3CD5623D-4A66-40F6-8128-A90CDDF6CA2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"050082dcd8173d3a4b9678af309977a44ca20289","datavalue":{"value":{"entity-type":"item","numeric-id":4298845,"id":"Q4298845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d9103146bb72792793f2c7404d6e00a7367c747","datavalue":{"value":{"amount":"+0.9553206","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":"Q555978$4419A172-6451-4929-8FDA-4A27876A85C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"908fad04dfc551c68dd9440837b8ffe2c376d7d2","datavalue":{"value":{"entity-type":"item","numeric-id":4542552,"id":"Q4542552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37d18e6b776bcbaf76d3c08dff131ccc774c0932","datavalue":{"value":{"amount":"+0.9492073","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":"Q555978$16AACA79-74F3-44DE-9BDC-5FB81AD5748C","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":"0271ccdb3c74031e2ae9ef05cc406f2c12b40abc","datavalue":{"value":{"amount":"+0.9413109","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":"Q555978$4EC8F17A-A276-4D57-B26D-DB27E6CBBBE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e924db86956c4ab1fc2cabdc35bb0aafda357e1","datavalue":{"value":{"entity-type":"item","numeric-id":4233365,"id":"Q4233365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0d3f504b6f76754a03afebc1226ff0483138201","datavalue":{"value":{"amount":"+0.93762594","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":"Q555978$9F3A8666-BEFE-4177-BC11-911649D60599","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02cab10c688479660b0711b6c9459d401e377c9a","datavalue":{"value":{"entity-type":"item","numeric-id":4258215,"id":"Q4258215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0d3f504b6f76754a03afebc1226ff0483138201","datavalue":{"value":{"amount":"+0.93762594","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":"Q555978$E3F4399F-A7A1-4B2D-A517-AEAA46C7A16E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5077876e9ac66a4f9b05e19ca2c81acce806647c","datavalue":{"value":{"entity-type":"item","numeric-id":4374975,"id":"Q4374975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0d3f504b6f76754a03afebc1226ff0483138201","datavalue":{"value":{"amount":"+0.93762594","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":"Q555978$D580ECCC-BB09-49BE-BAD3-84EB421DD3A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"821578afdcbc0c39307bdd5867512380da351a4c","datavalue":{"value":{"entity-type":"item","numeric-id":1126838,"id":"Q1126838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f54a1fe96d65e5ad139d0d0bb9552b91080627d","datavalue":{"value":{"amount":"+0.9373088","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":"Q555978$DD780D22-2CCB-46D8-890C-06A94977EAA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad2129038a997f0e92e7bb47c5328c2cc88ef43f","datavalue":{"value":{"entity-type":"item","numeric-id":4698461,"id":"Q4698461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45dd760d58cd46bb9f7c06a65d70631d044e48db","datavalue":{"value":{"amount":"+0.9364255","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":"Q555978$D6AD194C-DE07-4A45-8DD7-B8609E638D83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c21bdb2b5dcfb6c3e00fa92e272484fe347ac0ed","datavalue":{"value":{"entity-type":"item","numeric-id":4209084,"id":"Q4209084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"acebde116ecf06149f9282ee93f5be51972643bf","datavalue":{"value":{"amount":"+0.93218625","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":"Q555978$B9260410-3C43-455F-B729-64B897D0A62F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Approximation algorithms for NP-hard problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Approximation_algorithms_for_NP-hard_problems"}}}}}