{"entities":{"Q2427738":{"pageid":2438481,"ns":120,"title":"Item:Q2427738","lastrevid":44069925,"modified":"2025-11-19T16:26:24Z","type":"item","id":"Q2427738","labels":{"en":{"language":"en","value":"A deterministic approximation algorithm for the densest \\(k\\)-subgraph problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5279639"}},"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":"Q2427738$DD358B4A-B395-454B-95AE-989E0AAB8915","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e372d125d32a78ac0453c7a5310ab4655a5cbc77","datavalue":{"value":{"text":"A deterministic approximation algorithm for the densest \\(k\\)-subgraph problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2427738$0B2658E9-A023-4A13-8DA6-E6D936187C07","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fcddc7b59a3f9ae75056215cd402f60de3108f72","datavalue":{"value":"1138.05322","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2427738$FD326A61-B85A-416C-A0AC-C56FCFC4A742","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f6c826cecc4595315ab7a0655167616adf78af66","datavalue":{"value":"10.1504/IJOR.2008.017534","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2427738$878BDB55-5C9B-46AF-B64A-45EFABD8C45F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc965ae716c844c126b9098d4bf542f5b333e4ea","datavalue":{"value":{"entity-type":"item","numeric-id":286995,"id":"Q286995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2427738$F9DCC3B5-B423-4CB7-B670-7E86EC9CBE80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1f1c6a8167c7f3e97dc242c6c4f58c64741e146","datavalue":{"value":{"entity-type":"item","numeric-id":176416,"id":"Q176416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2427738$DA3272EA-B62A-44AD-94A2-699F8DB9F762","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2416e8a5c76a3e001f6e57b132d70eaeca49c502","datavalue":{"value":{"entity-type":"item","numeric-id":541285,"id":"Q541285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2427738$7F761056-A819-4C1A-9D85-29FF8D3265A9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6183386ae8366a240584c653ce5ca2494433aedb","datavalue":{"value":{"time":"+2008-05-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2427738$616E66FA-33E2-4CF2-AA91-E5EC7B99E5B7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a03a96f3638d56ecd97bd061f994579e7b3a1215","datavalue":{"value":"Summary: In the Densest \\(k\\)-Subgraph Problem (DSP), we are given an undirected weighted graph \\(G = (V, E)\\) with \\(n\\) vertices \\((v_1,\\dots , v_n)\\). We seek to find a subset of \\(k\\) vertices (\\(k\\) belonging to \\({1,\\dots , n}\\)) which maximises the number of edges which have their two endpoints in the subset. This problem is NP-hard even for bipartite graphs, and no polynomial-time algorithm with a constant performance guarantee is known for the general case. Several authors have proposed randomised approximation algorithms for particular cases (especially when \\(k = n/c, c>1\\)). But derandomisation techniques are not easy to apply here because of the cardinality constraint, and can have a high computational cost. In this paper, we present a deterministic \\(\\max(d, 8/9c)\\)-approximation algorithm for the DSP (where d is the density of G). The complexity of our algorithm is only that of linear programming. This result is obtained by using particular optimal solutions of a linear programme associated with the classical 0-1 quadratic formulation of DSP.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2427738$CD406ED0-7C4C-4388-8060-4E92F8647095","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2427738$71C2866F-164D-44AB-9EE3-6973EFE0EDF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2427738$7CB1DC25-5AC3-4FD6-BC05-B774AB3567DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4d4b880941bb65ec306ce9d3141ff7e82566f56","datavalue":{"value":"90C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2427738$72DF2E33-52B8-4CA7-BFC7-70DE6EFA7642","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2427738$F7D56E50-99AC-426C-8B78-553311557C7F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d0f57e5321df90c5542f67f8a64d721f5607e8c5","datavalue":{"value":"5279639","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2427738$CE1E1931-FC35-4934-BA89-00C5C5D90218","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2427738$EAF34F70-00EB-436B-AE4E-CACF80543CEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2427738$C39B2F1F-4D48-4E1E-883A-0E30347AA915","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a08efa1a08a750d06fca0196004a17a02a35c592","datavalue":{"value":"linear programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q2427738$1E30AA9D-A513-4C52-90E1-F53B242BC430","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e69e213b51557cc1d7697165bed961e402ad508","datavalue":{"value":"quadratic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q2427738$BC303AF5-FEEC-42EB-8F07-E36B20BDEC09","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":"Q2427738$096382C6-CAAE-478D-858D-30FA1C10B65F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"46a7cde1d82ef6ab29d67e2f1d323f547260cbae","datavalue":{"value":"https://doi.org/10.1504/ijor.2008.017534","type":"string"},"datatype":"url"},"type":"statement","id":"Q2427738$A24C30EE-C878-4C12-B7E1-6432AE71F9B5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"852afea07d38b3ca14577f966080aec7cea80e0d","datavalue":{"value":"W1989483229","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2427738$BAC604D4-844D-4863-AD31-52525E9B0C87","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3320132e66da0c03d3cdd824621f9ece207756fc","datavalue":{"value":{"entity-type":"item","numeric-id":4914440,"id":"Q4914440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e47d5c7d938c039912e4cd9f41167880e668835","datavalue":{"value":{"amount":"+0.96717554","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2427738$64E2E578-D18E-4A33-A1C3-10CA37BDE7C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"758251c33e2d2c2ac7b598a0492f78f85976aabd","datavalue":{"value":{"entity-type":"item","numeric-id":1683124,"id":"Q1683124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea18fdcac43d924eae4f30a96e5fba9885cb727f","datavalue":{"value":{"amount":"+0.94707346","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2427738$A1B3DD60-3230-4FCA-8CDC-4AA711EADEF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa880a53ab4fa6dccf98c8ff237020051dd7fffc","datavalue":{"value":{"entity-type":"item","numeric-id":3467871,"id":"Q3467871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"359df99fd855be2e5db9310c36d50103ace3cb22","datavalue":{"value":{"amount":"+0.9468248","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2427738$A0F11E7D-85DD-4DC9-B338-C3FC8E398854","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de5e12c50d96adfee33b3260e13bcb922ea88915","datavalue":{"value":{"entity-type":"item","numeric-id":5930156,"id":"Q5930156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8d17e0c35d5f958c690ea2f6e2c607725b00159","datavalue":{"value":{"amount":"+0.9405037","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2427738$8FA6B01E-DE94-433E-BD0C-3FB2DDA9BF5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3d918385d2379259db503ee66cb0e7abc606161","datavalue":{"value":{"entity-type":"item","numeric-id":963469,"id":"Q963469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c11798ad4613af9be42bd014bd3a857784514de2","datavalue":{"value":{"amount":"+0.9399584","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2427738$0C8A755A-EFFE-4670-873E-FB7C452D9EB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1408c9609cc986646fa519b4bebcb64ee6c873e2","datavalue":{"value":{"entity-type":"item","numeric-id":5859000,"id":"Q5859000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b34e3f0eccd6cefa5c68cc70d5ba663cfba3a6e0","datavalue":{"value":{"amount":"+0.9376863","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2427738$B6B5906B-0E24-4321-B67E-4D749788D6F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4ae3552da2a0e706cf6d8a3924cae464f17ff7c","datavalue":{"value":{"entity-type":"item","numeric-id":1776068,"id":"Q1776068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d342a8ac5c3507f4d0972b03ca63807c3c6182c8","datavalue":{"value":{"amount":"+0.9355693","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2427738$896112E3-D38E-4C78-8F3A-3A9A4AEEBE1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c513e9d35e3705c99ac63908b82ec60ab6d07ea1","datavalue":{"value":{"entity-type":"item","numeric-id":2094387,"id":"Q2094387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03663a79413aaef04f39ff3ed39caf33b47d7aa8","datavalue":{"value":{"amount":"+0.9326592","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2427738$D9BEF40A-F91C-4013-9B64-F4B0B280A569","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0603e859b8ca14601e49c4740a5d13c73d6813f7","datavalue":{"value":{"entity-type":"item","numeric-id":3075452,"id":"Q3075452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec93d111c1f2e0e78ac322436a4ef80c6fcf0bb1","datavalue":{"value":{"amount":"+0.92720294","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2427738$40D6BB17-5D68-49AD-B376-D398286FE789","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5e7182d65706603baa4ceb026ac249ee6bd63c5","datavalue":{"value":{"entity-type":"item","numeric-id":3174693,"id":"Q3174693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4ee26311df5da31e09c252b26cc58bbb41f5567","datavalue":{"value":{"amount":"+0.92428505","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2427738$67D7D5DB-ACFE-4541-9712-920EE3EAB59F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2427738","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2427738"}}}}}