{"entities":{"Q1825757":{"pageid":1836499,"ns":120,"title":"Item:Q1825757","lastrevid":69416508,"modified":"2026-04-13T06:51:31Z","type":"item","id":"Q1825757","labels":{"en":{"language":"en","value":"A multiply constrained matroid optimization problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4121763"}},"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":"Q1825757$8E8BB423-8CBE-4D31-8478-BAC74D8FACC0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ae96b8047fb48228dffef45c75a3f4af2407b0bd","datavalue":{"value":{"text":"A multiply constrained matroid optimization problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1825757$FC589248-A066-49AB-A1C8-378C9E232025","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c27e20cf1dcc7beaf48cd9879dc6c76726c1716a","datavalue":{"value":"0684.90072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825757$1A0F7A81-1421-4ED4-BD52-BB621BC609B1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ae7144259cab1adef48d8bed1e2b93b6e974992b","datavalue":{"value":"10.1016/0012-365X(88)90149-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825757$D8A78AAB-60C3-4052-AEF3-6D09C5124C20","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825757$E9969085-20AB-4BF5-B7E9-5B20CBEE16B6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825757$4B90D6C1-DDC2-47C5-8170-BA0CAA46B9E0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1825757$D156CD53-C3FA-4834-8B56-AEEF092BFB5E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6c2db8724be54100e877f53edf04db42ed799f79","datavalue":{"value":"Let \\(M=(E,J)\\) be a matroid, let E be partitioned sets \\(R_ i\\), \\(i=1,...,r\\), \\(E=R_ 1\\cup...\\cup R_ r\\), and \\(\\ell =(\\ell_ 1,...,\\ell_ r)\\in Z^ r_+\\). For a basis B the following side constraints are considered:  \\[  (1)\\quad | B\\cap R_ i| \\leq \\ell_ i,\\quad i=1,...r.  \\]  For a given cost function C: \\(E\\to Z\\) the multi-color matroid optimization problem is defined as the problem of finding a minimum cost basis satisfying the conditions (1).    Applications of this problem are: (1) Finding a minimum spanning tree in the network; (2) Finding a minimum cost schedule, containing at most \\(\\ell_ i\\) jobs of job class \\(R_ i.\\)    A direct algorithm for the multi-colour matroid optimization problem is proposed. This algorithm proceeds in two stages: in a preprocessing phase a minimum cost basis B of the matroid M is found (without constraints (1)); then, in the second (and main) stage a sequence of bases is generated, starting with B such the number of elements violating (1) strictly decreases. In this stage an optimal solution is found.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1825757$843C2DC6-FC52-4A63-B86D-F753026DB7C0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825757$8A292DDC-D68E-4DA5-A922-252003DF48E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825757$F6D837E6-1D99-421E-AA36-31F655AC0D3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825757$8956572C-294B-41DB-8E8F-4F60F0746F17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825757$82DC712D-3F13-4273-86F0-DAEA1658E53D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9524c89e1dd4f4a881a83fa7d8243f3c71330d42","datavalue":{"value":"4121763","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1825757$BCDA6371-C444-4B56-89A8-6BBB03423E30","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e172629663780e971698d7d841046893adba3be5","datavalue":{"value":"matroid","type":"string"},"datatype":"string"},"type":"statement","id":"Q1825757$4AAA7FB8-2107-4365-ACEE-506047958590","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1961213671f885c859af487ab2a2141224c918ec","datavalue":{"value":"multi-color matroid optimization problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1825757$B3BC5E0E-A145-43E9-B0F8-55F956440E18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e3bc19eaeabfbf693f7302c3604eed18458fb77","datavalue":{"value":"minimum cost basis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1825757$8E48B470-1DD2-471C-914A-77BE95189FBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"732e1592c53acfd9740f2cb8680bbb91fda5b0af","datavalue":{"value":"minimum spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1825757$B0577DC4-5A6C-41F3-83F9-A52F54BD89A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"83ed56008c38b9fd1a759d17bc0534980f4ce0ef","datavalue":{"value":"minimum cost schedule","type":"string"},"datatype":"string"},"type":"statement","id":"Q1825757$6A08692C-1726-4318-ACE5-A2B54E35E215","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e322e5ea623281b87278df8afa9635f950458f6c","datavalue":{"value":"preprocessing phase","type":"string"},"datatype":"string"},"type":"statement","id":"Q1825757$98C69660-8EE9-4D35-80E6-82FECFD617FF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f3ba912c6c747366fcbf58ca77660b129d8633c6","datavalue":{"value":{"entity-type":"item","numeric-id":1014034,"id":"Q1014034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825757$E1D53C07-4999-43D6-B918-5190F04178F4","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":"Q1825757$000EBB88-A4FA-4FE6-B5D3-57FE0F02C702","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"163439bf15333d78c5f11564941a2c37f94759b7","datavalue":{"value":{"entity-type":"item","numeric-id":3942972,"id":"Q3942972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825757$9F1CAA12-626B-4609-B0F0-B3A70DC132C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9beef10f14c1534c9b646b394bb6806fa6bcf5a6","datavalue":{"value":{"entity-type":"item","numeric-id":3335803,"id":"Q3335803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825757$C8C0543A-FD90-46EB-827D-D90B9F2A51E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1a7e29801581e9e5a5187db25cd480c84107d91","datavalue":{"value":{"entity-type":"item","numeric-id":793743,"id":"Q793743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825757$8C09DF4B-86D7-4CE5-83E5-2484DA1B5D02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fc80ff8bc78253674fdf2a04b4543ebb7790e4f","datavalue":{"value":{"entity-type":"item","numeric-id":3786484,"id":"Q3786484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825757$3CDE6DF7-DFDF-4577-B3FE-FB349806F662","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"242f6732c9aecb9180d76230dd0b3ce80be5a4cb","datavalue":{"value":{"entity-type":"item","numeric-id":4130999,"id":"Q4130999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825757$F30F2CF1-F095-4999-9497-78F5DE57A7BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16ee6ba21410efd14ddd2a024a73c0ed4e5a2745","datavalue":{"value":{"entity-type":"item","numeric-id":4111952,"id":"Q4111952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1825757$263510FC-6B86-4987-8D05-B72D63164EAB","rank":"normal"}],"P1643":[{"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":"f4dc66eb75861c773023aaa930f959b34060c0c8","datavalue":{"value":{"amount":"+0.94307995","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":"Q1825757$A93E9B89-3433-466B-AF1E-32039D1B25D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"979ea8e480c23662b372041a03fe3c4ca077565a","datavalue":{"value":{"entity-type":"item","numeric-id":1917230,"id":"Q1917230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a01e161b306cbed1bad6a086b3a949d22303777","datavalue":{"value":{"amount":"+0.9274817","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":"Q1825757$18609EA5-C77B-48CD-AF5C-27FD7F6BBB79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"201bfd3f21dfee13bd49775c44cedce845c1dfbc","datavalue":{"value":{"entity-type":"item","numeric-id":4443135,"id":"Q4443135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7fcbaf631bf017d2943588c934437d2aa5cf314","datavalue":{"value":{"amount":"+0.92445904","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":"Q1825757$640AEC75-4CD4-4AE5-831C-63327C150492","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60a9c35ef9d973054ce4a932c2e1a1bb84b37d53","datavalue":{"value":{"entity-type":"item","numeric-id":1824560,"id":"Q1824560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad6e74ad9d39563057590823feae7c0a1c170e14","datavalue":{"value":{"amount":"+0.9233782","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":"Q1825757$0002A870-7CD6-46AB-9D1F-34956F9FEBFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06ad0c5a6d59d3aaef1c7337d1cc8b38c3c93e0f","datavalue":{"value":{"entity-type":"item","numeric-id":1401298,"id":"Q1401298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a002f51cb55d86a4bf394f5f2ff910ab75706762","datavalue":{"value":{"amount":"+0.9216263","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":"Q1825757$59C1B8DD-0756-49A2-B2C7-8B0B2259651A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b84b0f672235823bce5eb94da53357fc2f4ad817","datavalue":{"value":{"entity-type":"item","numeric-id":1035682,"id":"Q1035682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1dc6d300d796975ca399fd53b30da372677f3748","datavalue":{"value":{"amount":"+0.9198957","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":"Q1825757$B3D21721-2BA6-4AA1-B49D-6F181AB3D894","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1db48d70ca39ce82bbe52ea1879b7a272a20bb4c","datavalue":{"value":{"entity-type":"item","numeric-id":3613798,"id":"Q3613798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1dc6d300d796975ca399fd53b30da372677f3748","datavalue":{"value":{"amount":"+0.9198957","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":"Q1825757$1A11C5E2-49F3-41B4-B2EB-0F41B2D502C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea8f9ebd9d8e6bcef8e4afc08e44f03b9238df97","datavalue":{"value":{"entity-type":"item","numeric-id":5406201,"id":"Q5406201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34a2daa98ce24454546ff9721ce3cef482b26158","datavalue":{"value":{"amount":"+0.9154694","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":"Q1825757$5A0E3EFC-6772-4CB4-8A39-FC8EB48348C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e4224df05a88ae58869823692bf5177745c8a71","datavalue":{"value":{"entity-type":"item","numeric-id":3768918,"id":"Q3768918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b83fb22d9ca4b603e41e462b1c8af97847b7efef","datavalue":{"value":{"amount":"+0.91206586","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":"Q1825757$3050125D-5355-4C08-98ED-C5FA627387FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d271148817964351dcde6ddaa50d2687c19c1e1","datavalue":{"value":{"entity-type":"item","numeric-id":2064281,"id":"Q2064281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2cb1a27038b4875991901b51de4bc13276975e1f","datavalue":{"value":{"amount":"+0.91170526","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":"Q1825757$79BF361D-3DA1-468F-B4FA-E4BD56891B82","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A multiply constrained matroid optimization problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_multiply_constrained_matroid_optimization_problem"}}}}}