{"entities":{"Q2381817":{"pageid":2392560,"ns":120,"title":"Item:Q2381817","lastrevid":50167745,"modified":"2026-01-13T08:27:35Z","type":"item","id":"Q2381817","labels":{"en":{"language":"en","value":"Least and most colored bases"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5192000"}},"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":"Q2381817$2922F911-366F-4A06-97D9-4A488277EBC8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2b566b834f84e3a679d5b502ea64b7889f379c7f","datavalue":{"value":{"text":"Least and most colored bases","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2381817$33746357-6B18-4616-A245-9EE1F1CB9EE8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e55c9514bc1913714a7dbccd7bce47be4f1c4075","datavalue":{"value":"1124.05022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2381817$51EB7C9F-F457-43DC-87B2-3236BDBED7F2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9ca552b5a09a951163fe2671a2056a7d7d226e25","datavalue":{"value":{"entity-type":"item","numeric-id":496638,"id":"Q496638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2381817$58F259CE-F41E-418E-8F94-8974AEB614FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"186bb8da4d9a21e884eff28e3a0bd8547b44ac9e","datavalue":{"value":{"entity-type":"item","numeric-id":168651,"id":"Q168651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2381817$5158ED47-9FBA-47AD-A428-9EE6B3F5C67A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f087fae0f3567d60e670ed1b38fc78411fe65a08","datavalue":{"value":{"entity-type":"item","numeric-id":336927,"id":"Q336927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2381817$CDB14659-CD13-4634-9AD2-EBC160CC0AED","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2381817$660116D7-EDCE-4788-BEB8-24117FB29542","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8fd95f87b670d3b26d34ef2750f8342013822a91","datavalue":{"value":{"time":"+2007-09-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2381817$80465693-61C2-4792-ACFE-DAD3D1348D6E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cef2d95b47fca81f3277b2c342ae2b392c909913","datavalue":{"value":"From the authors' abstract: ``Consider a matroid \\({\\mathcal M} = (E,{\\mathcal B})\\), where \\({\\mathcal B}\\) denotes the family of bases of \\({\\mathcal M}\\), and assign a color \\(c(e)\\) to every element \\(e \\in E\\) (the same color can go to more than one element). The palette of a subset \\(F\\) of \\(E\\), denoted by \\(c(F)\\), is the image of \\(F\\) under \\(c\\). Assume also that colors have prices (in the form of a function \\(\\pi(\\ell)\\), where \\(\\ell\\) is the label of a color), and define the chromatic price as \\(\\pi(F) =\\sum_{\\ell\\in c(F)}\\pi(\\ell)\\). We consider the following problem: find a base \\(B \\in {\\mathcal B}\\) such that \\(\\pi(B)\\) is minimum. We show that the greedy algorithm delivers an \\(\\ln r({\\mathcal M})\\)-approximation of the unknown optimal value, where \\(r({\\mathcal M})\\) is the rank of the matroid \\({\\mathcal M}\\). By means of a reduction from SETCOVER, we prove that the \\(\\ln r({\\mathcal M})\\) ratio cannot be further improved, even in the special case of partition matroids, unless \\(\\text{NP} \\subseteq \\text{DTIME}(n^{\\log \\log n})\\). The results apply to the special case where \\({\\mathcal M}\\) is a graphic matroid and where the prices \\(\\pi(\\ell)\\) are restricted to be all equal. This speial case was previously known as the minimum label spanning tree (MLST) problem. For the MLST, our results improve over the \\(\\ln(n-1)+1\\) ratio achieved by \\textit{Y. Wan, G. Chen} and \\textit{Y. Xu} [Inf. Process. Lett. 84, No.~2, 99--101 (2002; Zbl 1042.68055)]. Inspired by the generality of our results, we study the approximability of coloring problems with different objective function \\(\\pi(F)\\), where \\(F\\) is a common independent set on matroids \\({\\mathcal M}_1,\\dots, {\\mathcal M}_k\\) and, more generally, to independent systems characterized by the \\(k\\)-for-1 property.''  The authors conclude this paper by giving a few open problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2381817$FA5E4925-1FD7-486E-9400-D1F0173A22BD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2381817$FE1AB9AA-171C-4263-8E32-89BA6D954557","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"887c64dc5f49efa09a3ccec80ce98c46ffc0ef35","datavalue":{"value":"5192000","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2381817$5A1FBF81-E629-4256-8029-256F6821D2FF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a39ec4307b26d786312cb390856b9060d3bf22c8","datavalue":{"value":"matroids","type":"string"},"datatype":"string"},"type":"statement","id":"Q2381817$8B7693C1-FF3B-4D4B-BB63-6B1DA3149A17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2381817$17FA53B3-89C1-4D3D-8BC4-40005453FCC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"833e91709dce420c488324e7ffcd50fd4f2d46f5","datavalue":{"value":"low chromatics","type":"string"},"datatype":"string"},"type":"statement","id":"Q2381817$EAD74C67-0F2A-456D-BC68-514C92BC1A2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36824c0645fdc4daa873973cca78f73d1e5468b","datavalue":{"value":"minimum label spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2381817$E6801874-1431-4248-9411-D21973D02C3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aa9bd8c737c286c4c97d7a8d7d7537d150ad7c57","datavalue":{"value":"MLST","type":"string"},"datatype":"string"},"type":"statement","id":"Q2381817$26359404-5DD4-4BE6-A684-9DB6D8AEB7D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4922190709d932b94748e5084fef7f6c1dad4950","datavalue":{"value":"matroid intersection","type":"string"},"datatype":"string"},"type":"statement","id":"Q2381817$C7E7174F-05E5-4CBB-A5E0-00B15D54BE8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eeaf6ede94ce849860a1c94fb2e0d3489a8466bc","datavalue":{"value":"\\(k\\)-for-1 property","type":"string"},"datatype":"string"},"type":"statement","id":"Q2381817$856AE71F-5B70-47FB-AF8E-29F3E5DE0D3F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"98a1a26433ed1e32f953e21c0b1330590dfc0cca","datavalue":{"value":{"entity-type":"item","numeric-id":1607941,"id":"Q1607941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2381817$1C3EC29D-AE5E-40BE-A82A-DFA37F60AC52","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":"Q2381817$9C542A8D-7EAD-4C68-AE1F-B6EEF2AEFCA0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"74da4d55c90821c7b96278ed2368168cdf1cb04b","datavalue":{"value":"https://doi.org/10.1016/j.dam.2007.04.015","type":"string"},"datatype":"url"},"type":"statement","id":"Q2381817$8A432CDA-B791-486B-94A9-ECCC73625E53","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a7f612df7d93f53da7854eba65e7333f8fcea335","datavalue":{"value":"W2125128537","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2381817$37691D45-A552-461C-8B79-09833FAB35CC","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":"Q2381817$AF4AE454-D8F5-444C-A04C-309B9B768EC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb109ec75d68e9d2444bbbc8d991af3883e4c1df","datavalue":{"value":{"entity-type":"item","numeric-id":4806595,"id":"Q4806595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2381817$1EB843E6-4A66-4567-A6F9-A091803FC0B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"caea1b9fae3c73230a03a25384422c4d9ad2d79c","datavalue":{"value":{"entity-type":"item","numeric-id":1567492,"id":"Q1567492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2381817$03F96E0C-2830-4050-A236-7F378BB8E5C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4042a6a8925d33e7ac25ffe3a11c3e8654542cc4","datavalue":{"value":{"entity-type":"item","numeric-id":5668601,"id":"Q5668601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2381817$503996F7-D84A-421A-92FA-6BE6D1456BCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c837d56e04962823c1d7c934cd015e72d540d8c","datavalue":{"value":{"entity-type":"item","numeric-id":1588908,"id":"Q1588908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2381817$C4BFF1F3-4DBC-45DA-8216-9E55746D8108","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"429924f0ddd3bc1c7dc54a3226f108e3ebc2b532","datavalue":{"value":{"entity-type":"item","numeric-id":922700,"id":"Q922700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2381817$496579CD-3079-4CAC-818C-E7EA9BA866F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a976a465819bef8de9d16113bd25533132d8062e","datavalue":{"value":{"entity-type":"item","numeric-id":5915481,"id":"Q5915481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2381817$395EA09B-9EED-4252-9644-9B6A0AB6E663","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5aaee5a7eb4380e24bf784b751d7633c396083f","datavalue":{"value":{"entity-type":"item","numeric-id":1567494,"id":"Q1567494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2381817$BB7FBD8C-378A-4A78-98ED-4E315B9A836C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1860b0031e2cbb9105661e4b1058c275782a39cf","datavalue":{"value":{"entity-type":"item","numeric-id":3135082,"id":"Q3135082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2381817$196587C9-2B85-4275-A659-27F2ABFA52B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c01149a6900c0f611a509645affd60c9a396109","datavalue":{"value":{"entity-type":"item","numeric-id":1854113,"id":"Q1854113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2381817$4DFB1871-A494-4D1E-88E8-71D534F5F9C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81ad59edd83c5a5922888485314cbd43fe65f847","datavalue":{"value":{"entity-type":"item","numeric-id":1853118,"id":"Q1853118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2381817$FF17FC00-0AEC-4B9E-A909-F6BCCF760BB0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"54f023fa7a9c04a33f0c64a894143c4bb8027afa","datavalue":{"value":"10.1016/J.DAM.2007.04.015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2381817$8635659D-6B2C-4F51-909D-A9C77BA208F6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"602284fcd76f40fe042bf377880f6fe0147f2855","datavalue":{"value":{"entity-type":"item","numeric-id":1825757,"id":"Q1825757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e20e78cd60f94714ed5b43aabfd77b4e5ce6c91","datavalue":{"value":{"amount":"+0.8157666921615601","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":"Q2381817$BF5305C5-2ADC-4DD4-8600-9A04472EB8F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dfe3cf4466ff8b94eb03832fb0c5ed48451f8361","datavalue":{"value":{"entity-type":"item","numeric-id":1116893,"id":"Q1116893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c97847930a0fe3dfac6edb8c76fee6ed9d4a3941","datavalue":{"value":{"amount":"+0.8085802793502808","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":"Q2381817$08BFB1FD-0F37-4AE5-BB79-7922AF4353E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"306282e58bbdfc0c70accbc5a4c6f35e6798eda9","datavalue":{"value":{"entity-type":"item","numeric-id":1902899,"id":"Q1902899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6bcc939f55649be62fd7223a15e30896efa0a24d","datavalue":{"value":{"amount":"+0.7982636094093323","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":"Q2381817$D9001068-6D1E-48E4-AC2F-76A5DE97C713","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77cf0f97e10e3672546b9c4d636f505170203657","datavalue":{"value":{"entity-type":"item","numeric-id":1567494,"id":"Q1567494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86f6e09b7127670debcf52de43417d17b6c60fdc","datavalue":{"value":{"amount":"+0.7903931736946106","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":"Q2381817$3571FC46-FE32-4999-9799-7B17517EB7D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d049b2867fc19c693dbf3c93c07edd6cb2817ab","datavalue":{"value":{"entity-type":"item","numeric-id":3823151,"id":"Q3823151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e92cbb307c9a1944f82d6b01107a6e3d1441dd85","datavalue":{"value":{"amount":"+0.7895224690437317","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":"Q2381817$16996DBF-AEC7-46AA-846B-158A2E72D2D9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2381817","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2381817"}}}}}