{"entities":{"Q5091208":{"pageid":7120784,"ns":120,"title":"Item:Q5091208","lastrevid":55417699,"modified":"2026-02-17T15:58:58Z","type":"item","id":"Q5091208","labels":{"en":{"language":"en","value":"A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7561546"}},"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":"Q5091208$8D68D3C9-DB48-4E66-A36D-7C397F1F83B5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ae3e014d42c3e727189349ca8167d2ae32144d1","datavalue":{"value":{"time":"+2022-07-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5091208$712BC2EC-71F4-4559-954C-D3A6558E6139","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cc527648987a4b18821dc8182f40c6221de9ac1e","datavalue":{"value":"https://arxiv.org/abs/1709.09767","type":"string"},"datatype":"url"},"type":"statement","id":"Q5091208$8EDFCEF7-80B6-4364-979E-BB9C33FFB9BF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1a86519cb3571ebce07f2774b2a00a0f17e12c3e","datavalue":{"value":"68Nxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5091208$E7DAC550-A1ED-438F-ADC2-250CB60B84C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f969879f531643f058f8dd4c87a7dd4eb7b8c4c8","datavalue":{"value":"68Qxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5091208$0D0A82F9-18F3-4054-899B-8D5581282BEF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3e051acdcea420d7259436fcb2419940819c3e2e","datavalue":{"value":"7561546","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5091208$DF7BA849-8CAD-428C-BA05-CC6740D1658C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1abb336161ff4deef82963d0b7a45aad4ca53006","datavalue":{"value":"submodular maximization","type":"string"},"datatype":"string"},"type":"statement","id":"Q5091208$9FFE07A2-1540-4E6C-9D74-401DEC1A7E18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d6d9c45802133dbf06d2d91ca2ce49b8d91ac816","datavalue":{"value":"knapsack constraint","type":"string"},"datatype":"string"},"type":"statement","id":"Q5091208$A1B39D96-4457-4B1D-9154-AEB84F00588E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6c3d0e43fbb4f9f417e06ac9436fc30c40aa3654","datavalue":{"value":"fast algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q5091208$C0C7F338-B0F8-4EEB-AB87-81227BF2DE58","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":"Q5091208$B7342B77-E7B7-4239-9C61-55FA40645DAD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4031ff26749c23fab9d4e75e69291960d77acde2","datavalue":{"value":{"entity-type":"item","numeric-id":5384072,"id":"Q5384072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5091208$56FF0853-0F69-4C05-A148-5E7BD44D24B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7738f205688a5ed21704048de0610306b2a8ad94","datavalue":{"value":{"entity-type":"item","numeric-id":2913805,"id":"Q2913805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5091208$1D533F6F-E221-40AA-A73F-1531C22D4346","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b601e2a8622ed3bed24be9098d56eda05977be07","datavalue":{"value":{"entity-type":"item","numeric-id":517305,"id":"Q517305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5091208$7F469605-168C-4B1F-AE61-67492C3BD6F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be5f1aa9294846cde8376d837af26608b9f41054","datavalue":{"value":{"entity-type":"item","numeric-id":2941641,"id":"Q2941641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5091208$03CEEE62-3B44-43F8-BC2C-A18C43473F34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b58031c6af924091b563c813c2578873fc8da1f","datavalue":{"value":{"entity-type":"item","numeric-id":1606925,"id":"Q1606925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5091208$97CCB9BF-3956-407A-AB60-F0E99D4C8CF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e6f2521f9ee7a0316d4b7815bef4b51c61a20c6","datavalue":{"value":{"entity-type":"item","numeric-id":3096108,"id":"Q3096108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5091208$3284C588-BDD5-4E20-B1E9-1F482AA71291","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9840c2934f54d1d6cbb7a8580f4146d9f2fbf08","datavalue":{"value":{"entity-type":"item","numeric-id":5169688,"id":"Q5169688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5091208$EA16C9D5-F6FF-4ECF-8F87-8B8A7FA210B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"521236195e8c1b65dfc0d8a560fecc45a7c4539e","datavalue":{"value":{"entity-type":"item","numeric-id":1433658,"id":"Q1433658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5091208$90230DE7-F6E9-4BEC-AC44-4D91D637E73D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7607705e7006c59cc64170d82df981347f7e9c9","datavalue":{"value":{"entity-type":"item","numeric-id":3964292,"id":"Q3964292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5091208$3329AE85-B15E-438C-934B-E8FAA5701740","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36f272bb27ef5224ac6f7695c0bb0247ad88c2b8","datavalue":{"value":{"entity-type":"item","numeric-id":5232162,"id":"Q5232162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5091208$4BC61DE2-7E93-474D-9465-AFEE075DE1B7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8dc6e4647be2df5c2edfeecad84f5df40ade75d0","datavalue":{"value":"W2964501918","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5091208$1D2BFCB6-49FF-4003-A644-C86B2EF58CD0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"53fe7a73e691044c6d4092a27983b96742523927","datavalue":{"value":{"text":"A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5091208$6DA31376-EB59-43BE-9EDC-B4BF14167FFE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4374e03c55b080b6865df75c086eaa884e418f32","datavalue":{"value":"10.4230/LIPICS.ICALP.2019.53","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5091208$797C05F8-D7D6-4FA9-BBC2-1CE7E7AEBF19","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a64c3f294b9c7debcf510a614c4fb46557392622","datavalue":{"value":{"entity-type":"item","numeric-id":5384072,"id":"Q5384072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec7ee068b22f81b2a418d61cf058fa84b7889a63","datavalue":{"value":{"amount":"+0.8987858891487122","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":"Q5091208$C111AD98-64E6-4A40-B4F8-C1AE672DEADD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8198c0fd4ff8fd34bb9a6e46fd7516eb00b07d51","datavalue":{"value":{"entity-type":"item","numeric-id":6646748,"id":"Q6646748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d97f39621c8e66525b4718953f44132bd1e63133","datavalue":{"value":{"amount":"+0.89481520652771","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":"Q5091208$56A0CAA2-C2CB-41AD-9914-9FB3951533CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33e0be985b22bed691f551890f600c8724a6ebb3","datavalue":{"value":{"entity-type":"item","numeric-id":2071828,"id":"Q2071828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"232a95ee015554b27f002996db74bb81a96cc203","datavalue":{"value":{"amount":"+0.8828594088554382","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":"Q5091208$3849DB90-11AE-42D2-9256-21A5CBF63E74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b190cd2e59e1f199de12d881d8838f57bacc237a","datavalue":{"value":{"entity-type":"item","numeric-id":5232162,"id":"Q5232162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1bf9f1ae778dbc37f334afb57447fbfc1e7008a7","datavalue":{"value":{"amount":"+0.8720808625221252","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":"Q5091208$7DD27E96-2B0E-4562-9E3D-5F4F4DF92E4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ec0c04601f9ed85d0408b2d5bfc068a06913236","datavalue":{"value":{"entity-type":"item","numeric-id":5091209,"id":"Q5091209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aceeaa629bbcf305835dcb78ad273c571b20da10","datavalue":{"value":{"amount":"+0.8650249242782593","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":"Q5091208$B1D8387D-412B-49FC-AC8B-CB7876CAF75B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5091208","badges":[]}}}}}