{"entities":{"Q2713933":{"pageid":2724672,"ns":120,"title":"Item:Q2713933","lastrevid":82947569,"modified":"2026-05-06T22:31:38Z","type":"item","id":"Q2713933","labels":{"en":{"language":"en","value":"A generalization of the notion of the rank function of a matroid"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1603194"}},"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":"Q2713933$EAFE1B9C-7AAF-47F1-9CBD-140E214A18F8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"014755f9ea5ff3b08271c5164f85d2e629c008e5","datavalue":{"value":"0962.90026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2713933$8838A8A2-8456-4FFA-B5F8-D725BF69DFCE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4f37cc8bb662cd7f5cb2e3539b4c100a929f564a","datavalue":{"value":{"entity-type":"item","numeric-id":2713930,"id":"Q2713930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2713933$68093FF7-95F0-48A8-8508-796E51559889","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d399175a75045d6e68cdfc363866ce63dcafb225","datavalue":{"value":{"time":"+2001-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":"Q2713933$86765025-77F7-48FC-A62A-F4B1723897D8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2713933$80280282-D486-4CDC-A102-B5FE4FDEACF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2713933$1BA198E1-F799-4D05-941E-01C501B8FB2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2713933$AB07DBAB-8AA4-4DCB-B488-D9A54D064562","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"078e6eee212eea11f16ef1a83a39fe0dd9f426a5","datavalue":{"value":"1603194","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2713933$A589FCEE-0545-46A0-8937-47ECF4626219","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"68082f1427efc058bae38252345111a0a8fbb3cc","datavalue":{"value":"efficiency of the greedy algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2713933$B200FC85-D27E-45A2-9BDA-5DB96C71C8BF","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":"Q2713933$6D43EE35-A5B4-4AFC-8E19-93CA75F997EC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4f08d54694a3d01f322f1381dbefc39bc66c573d","datavalue":{"value":{"text":"A generalization of the notion of the rank function of a matroid","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2713933$AF98EC56-BD89-4A4E-A99A-52604E6FBD68","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"75dbe44001945ccc889d4ace23e71d51974d13f4","datavalue":{"value":{"entity-type":"item","numeric-id":6768473,"id":"Q6768473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2713933$4C9B2122-BC1B-4481-AB6F-92D067C49DB3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2c3d191a9a80708fcbb068a550106a58642baaa4","datavalue":{"value":"The author introduces two functions which generalize the notions of the rank function for independence systems and, in particular, of the rank function of a matroid. In terms of those functions, the author describes accuracy of an approximate solution obtained by a greedy algorithm to a maximum problem of integer programming with a linear objective function. Some interrelations are found between optimality of the greedy algorithm and submodularity of rank functions. As a corollary, it is shown that the greedy algorithm ``go to the farthest unpassed town'' solves the travelling salesman maximum problem on an unordered graph with relative accuracy 1/2.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2713933$C52FD9CB-B4EA-4E85-8199-B99F067B586F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e2dc442f8110e9da1c86938ce70f0536c26eb15","datavalue":{"value":{"entity-type":"item","numeric-id":790044,"id":"Q790044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86c6f1db51f9c41bf162701457c96505173323db","datavalue":{"value":{"amount":"+0.8330278396606445","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":"Q2713933$8ED371A9-0CD7-477F-A7F7-7AD65782A2BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cbd5c244fccc12045d7195420a6b5d4c65e6294","datavalue":{"value":{"entity-type":"item","numeric-id":2429474,"id":"Q2429474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b968be23c5d0d066fc5b7bc6cccb9446c03333a2","datavalue":{"value":{"amount":"+0.8149539232254028","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":"Q2713933$858180D7-8EB5-4A7B-9632-2F8138027CE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16ac05537a78b9c98cabc444f2867f50f972d822","datavalue":{"value":{"entity-type":"item","numeric-id":3682497,"id":"Q3682497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6a0c1d7b86f0972e3f729b10f7339a0c7784d5d","datavalue":{"value":{"amount":"+0.8093611598014832","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":"Q2713933$D23623F5-7ADE-4CDE-880F-FD09801DAAC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"679d77a589f1daba249e46cf61ffa3f306a929b5","datavalue":{"value":{"entity-type":"item","numeric-id":3225892,"id":"Q3225892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41de14c16196608b1db7af659c72d6d937e8291a","datavalue":{"value":{"amount":"+0.8083993792533875","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":"Q2713933$5531954B-7A08-41EE-993E-1136E3E4F03D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb4b135992bfc28331ecb94ddaf0713b26e82c81","datavalue":{"value":{"entity-type":"item","numeric-id":4038320,"id":"Q4038320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5772bbf31a13b5b58669bc1f1ef01bc9ffa89aec","datavalue":{"value":{"amount":"+0.7992533445358276","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":"Q2713933$C2A6F025-E176-4CEC-8138-7D84752C02C5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A generalization of the notion of the rank function of a matroid","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_generalization_of_the_notion_of_the_rank_function_of_a_matroid"}}}}}