{"entities":{"Q1116890":{"pageid":1127639,"ns":120,"title":"Item:Q1116890","lastrevid":69681606,"modified":"2026-04-13T08:40:39Z","type":"item","id":"Q1116890","labels":{"en":{"language":"en","value":"Optimization over the polyhedron determined by a submodular function on a co-intersecting family"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4089331"}},"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":"Q1116890$57C890EC-0768-442E-8AB0-E837D6F13009","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"12fb126398434b960245fd090c65e079e2c2e75b","datavalue":{"value":{"text":"Optimization over the polyhedron determined by a submodular function on a co-intersecting family","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1116890$4DE35570-66BB-4ECA-AA09-7BE416688104","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"df2bfddc0657797e7de892fe8b0cecabbcf56a5b","datavalue":{"value":"0665.90074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116890$3746A740-DE18-403A-BC40-3D8C2AD80C0C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0446ad70eccd0dbd99c04a82fc8d7169f8c4c2db","datavalue":{"value":"10.1007/BF01589419","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116890$919A1BCA-3C16-4FB4-AD4C-B1DC4607E6ED","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f96011a556b2e10829cd9de7e73be6f69c0e90d8","datavalue":{"value":{"entity-type":"item","numeric-id":308602,"id":"Q308602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116890$D11B94CD-479F-4980-970D-DAF9690219D2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116890$476A1657-3C51-4763-BA1C-108F072BACC3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1116890$E1686920-1B7E-42DC-922B-7B7DDB102347","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5341cf94ae7f9b67cc11524ee101c125c5bcd875","datavalue":{"value":"A greedy algorithm solves the problem of maximizing a linear objective function over the polyhedron (called the submodular polyhedron) determined by a submodular function on a distributive lattice or a ring family. We generalize the problem by considering a submodular function on a co-intersecting family and give an algorithm for solving it. Here, simple-minded greedy augmentations do not work any more and some complicated augmentations with multiple exchanges are required. We can find an optimal solution by at most \\(1/2\\;n(n-1)\\) augmentations, where n is the number of the variables and we assume a certain oracle for computing multiple exchange capacities.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116890$A9C0502F-B810-4006-9CAE-3CF04844FC25","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116890$F9E957BA-7FF3-4521-BFEA-7DA82A09AD8D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e69add2f72194b216286cd0aec3e92e4247afa5f","datavalue":{"value":"4089331","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116890$02EAD681-0F4D-4BF0-AE57-54E007570600","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e1e7eb452ae4c92c43fa47bb0afb8177365a429","datavalue":{"value":"greedy algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116890$2F571BC3-D0B2-4DBD-BB14-027011282D5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed90f9911101f86bb5a546aad00bc420580e1a77","datavalue":{"value":"submodular polyhedron","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116890$122BBB77-B162-44A6-B347-3E0E21ACCF4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ce6d3e05c67e7e482c47120f2d05461bf865564","datavalue":{"value":"submodular function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116890$847AEC41-8103-46CD-A23C-F65260DC2E72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5579ddf023a56f4856a8ee584af99380d23fb1f8","datavalue":{"value":"distributive lattice","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116890$5E18978B-9D5A-4DA6-B880-EC499D9FBBB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53c3c05adec17c83aed4eaaf68e7935fbfdf52f8","datavalue":{"value":"ring family","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116890$DF5F03AF-818B-4397-AF1E-479B9E1F99DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66fe1df894af18d4dffa488caa68091471ccbeb4","datavalue":{"value":"co-intersecting family","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116890$51322B19-F36E-417F-920A-6BA645C5F90E","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":"Q1116890$A0BE7C11-E122-44CF-8FBF-566F1453C156","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb97aa0ae022d4dc38b27f53ae16228cc4072891","datavalue":{"value":{"entity-type":"item","numeric-id":5684698,"id":"Q5684698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116890$77332850-324B-4974-9183-9CC5B7E9EA87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba07e54f50d0b7053d1d94c933758be0e016cc29","datavalue":{"value":{"entity-type":"item","numeric-id":796541,"id":"Q796541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116890$DF3C39C5-28CA-4663-936D-F5258299A321","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b71956cbfa836f94d8d1ed2cac40cd4173b1d49","datavalue":{"value":{"entity-type":"item","numeric-id":1116889,"id":"Q1116889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116890$DFCB0926-0F06-4453-9BD7-CEE2A1746E55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"202a081da6cf3441a6a0bfdc7c9bb9dff20ffb69","datavalue":{"value":{"entity-type":"item","numeric-id":3337243,"id":"Q3337243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116890$25865BB4-96C1-4ADE-A602-75E32AED2C88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bfb465119022165a5474f079589e42169495076","datavalue":{"value":{"entity-type":"item","numeric-id":1095780,"id":"Q1095780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116890$AD357553-83CA-425A-BEC0-E2FDA958137E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4b24afdc559d4dfafb8f042dc340fb9b4e2b9e4","datavalue":{"value":{"entity-type":"item","numeric-id":3313913,"id":"Q3313913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116890$61C6DFC1-613C-43E9-9F75-70C4D1B1414A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d16b4d29c0ba31b1bc8e06218af428a76fc8ce67","datavalue":{"value":{"entity-type":"item","numeric-id":1210712,"id":"Q1210712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116890$78B75E08-2619-42B6-82AA-8B579AA7D986","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4e5a50e1e90aeb19ca4ff2b3971a69ace23d33f","datavalue":{"value":{"entity-type":"item","numeric-id":3682236,"id":"Q3682236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116890$C305D03A-CC86-48BC-9755-39DEC56E95DF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"742a5077d4afd9235001b3bbc5dfc9d42e69002b","datavalue":{"value":"https://doi.org/10.1007/bf01589419","type":"string"},"datatype":"url"},"type":"statement","id":"Q1116890$CD095D3F-E5A9-4F52-A7A7-6A39F79EEA89","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e958d8566259b33711f50f165d6cc17ac41d273c","datavalue":{"value":"W1973651170","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116890$A3CFC6D2-0C92-4867-8E2C-2739FA18C5FA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3c3de2358bd7dd6eb6e8f13fbbff62e2bbddc3b","datavalue":{"value":{"entity-type":"item","numeric-id":3470254,"id":"Q3470254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec4b2b1006fe10b209a6b1c7455b2a983554c148","datavalue":{"value":{"amount":"+0.7852458953857422","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":"Q1116890$F9DDE658-29BB-474D-AEAE-85ECC53B6979","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9917f88bffa1c6348674bc8796b7f24b00048733","datavalue":{"value":{"entity-type":"item","numeric-id":4645927,"id":"Q4645927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9ca08bed3c03a7849009d917911c7edea8c4859","datavalue":{"value":{"amount":"+0.775673508644104","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":"Q1116890$74AF0BE7-996B-4585-82A3-15EE93C8C39A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c81bcb178da18ea2d827d035381fb0eec980b69","datavalue":{"value":{"entity-type":"item","numeric-id":1906848,"id":"Q1906848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86bd7a47a6350d654592860c9261c6d53b422128","datavalue":{"value":{"amount":"+0.772278904914856","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":"Q1116890$232D9189-A2E5-43CE-B14E-69BF634119B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62aad3044f1d61a4894cef4af8870c46800378ed","datavalue":{"value":{"entity-type":"item","numeric-id":2757558,"id":"Q2757558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94a3cfe3631b31db3b73419fe3b4d8f8d75b5cff","datavalue":{"value":{"amount":"+0.77027428150177","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":"Q1116890$C03B2132-6171-435B-8DBC-7DE134692821","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f16ac78eb3629a4de93f6e355b191a715271d756","datavalue":{"value":{"entity-type":"item","numeric-id":5951962,"id":"Q5951962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fadaef2cce1d8329c8878e3358f693fa4017d8b9","datavalue":{"value":{"amount":"+0.7656739354133606","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":"Q1116890$4704BA69-3E50-4408-8A6F-0EB648CA4372","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Optimization over the polyhedron determined by a submodular function on a co-intersecting family","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Optimization_over_the_polyhedron_determined_by_a_submodular_function_on_a_co-intersecting_family"}}}}}