{"entities":{"Q1346702":{"pageid":1357441,"ns":120,"title":"Item:Q1346702","lastrevid":70208649,"modified":"2026-04-13T13:10:33Z","type":"item","id":"Q1346702","labels":{"en":{"language":"en","value":"Weighted fractional and integral \\(k\\)-matching in hypergraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 741478"}},"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":"Q1346702$9914CF3F-A4B9-4410-9781-27219FC79AE1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a1a02d19d6b7c92b0a9154b99f0f1af4e22fdbb9","datavalue":{"value":{"text":"Weighted fractional and integral \\(k\\)-matching in hypergraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1346702$64EF6907-1F8C-458D-9D41-F8FE90298850","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"38be3306219dd750c7dbc81888bf30293bd557b6","datavalue":{"value":"0823.90131","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346702$8DCD775B-AC78-4506-89F1-04AD98E7FEFB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7d55770c1ea54aba1bb7284bee7ccbbdb75306b8","datavalue":{"value":"10.1016/0166-218X(94)00107-O","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346702$BC5DB8E6-0A23-433B-BA40-70AD2B5E23C1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"afee67896574e0646c3ab5dc5b7fef009a143542","datavalue":{"value":{"entity-type":"item","numeric-id":247943,"id":"Q247943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346702$BE030D09-D56D-41E0-8905-21634F9C437A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5051c783f07f0fd5a8c661e45043326cf06071dd","datavalue":{"value":{"entity-type":"item","numeric-id":1346701,"id":"Q1346701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346702$D98BC934-CE6C-4B4C-9E69-79E7D918C512","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":"Q1346702$547B4FCA-1BBE-45BA-9EF3-19367FDD5BA3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c22fff5067af428041487b6a008ee6b0a5e2859","datavalue":{"value":{"time":"+1995-04-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":"Q1346702$03B03884-61ED-4D86-9ADB-25911310F7BE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cf6634e45c451e4624b7e12c3682fdda237d65ea","datavalue":{"value":"It is well-known that the problem of maximum \\(K\\)-matching in a weighted hypergraph is strongly NP-hard, i.e. it is most unlikely that a fully polynomial approximation algorithm for solving it exists.   The main result of the paper is the following: Let the edge weights be rational numbers in \\([0, i]\\). If \\(K\\geq 24\\ln(n/\\varepsilon^ 2)\\) and every \\(k\\) edges have total weight at least \\(18\\varepsilon^{-2}\\), then the derandomized algorithm can find a \\(K\\)-matching \\(M\\) with \\(M\\geq (1- \\varepsilon) M_{\\text{opt}}\\) in \\(O(m^ 2+ \\log m+ nm)\\)-time, where \\(i> \\varepsilon> 0\\) and \\(M_{\\text{opt}}\\) is the weight of the optimum \\(K\\)- matching.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1346702$DEC213AC-DE14-4914-A02C-615347465FCF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"07239940f627bb41653311a5b39a7820a8be90f7","datavalue":{"value":{"entity-type":"item","numeric-id":199348,"id":"Q199348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346702$B6B0D358-5CD4-4D5D-B148-032760846B6E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346702$60472EE7-0EF3-4A48-A668-50BD8A142C83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346702$F6A93E73-534F-477E-BB31-7E4325843548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346702$1D07DBC6-CB18-40AD-83DA-7469F6A14A4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346702$11E2C4C8-9847-431A-B505-FA3BE53FFF9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346702$DA151842-EE19-4251-8319-A99119110157","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346702$C186ED63-8A37-4FB4-9E46-8F8BB88400E7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4137a05948f72389ef279489b9f20b52c27d1245","datavalue":{"value":"741478","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346702$E5C132FF-A2BF-44E8-B3A1-4D627C61C0D9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2832e5ae4fc414c772c86f6023e26d563dd35e6","datavalue":{"value":"randomized algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1346702$C2B7AE99-F9EA-4155-B29F-BD1E56071511","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6b780876d6cd571fe1e41341c135a10b0acf751","datavalue":{"value":"derandomization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1346702$DB463C1A-5CBA-4AD9-AECC-7FA2EA8B82F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b3c848ea9db20b779df8bae33337d7cd6211065e","datavalue":{"value":"maximum \\(K\\)-matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1346702$E1338650-94FF-421A-846A-85DC34E325AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"578c06b916852446fc4f2f3ac7925fb71b99a538","datavalue":{"value":"weighted hypergraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1346702$03496302-8FBE-4C2A-9655-57CA4C00D007","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdf4ca3d9fb773e560a856fad1c1f12857df3e40","datavalue":{"value":"strongly NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1346702$134C2548-D9E2-4055-BA89-E84760100A6A","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":"Q1346702$A4D9480E-1827-464E-B07B-B0D480BB3A9D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"98398ceceaf7acf358398f01c8692c94ae4b9944","datavalue":{"value":{"entity-type":"item","numeric-id":3986106,"id":"Q3986106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346702$1D857B68-B157-4A83-AB92-F9C0F988B87F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83c6293f25e8bc7e1747aa6978fc2fd52b5104b6","datavalue":{"value":{"entity-type":"item","numeric-id":1141153,"id":"Q1141153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346702$5E3620C8-C3BA-4F84-9123-083D9339E6D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7258962f550bf808b8ce0edfe0f9b2099a09d076","datavalue":{"value":{"entity-type":"item","numeric-id":4230322,"id":"Q4230322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346702$5E311F6D-B580-4428-ADD2-EA544A871E90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eea8108228a3fb03cd6914491ae57fb9168aef1f","datavalue":{"value":{"entity-type":"item","numeric-id":3986105,"id":"Q3986105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346702$1FB8426B-31D9-461B-8428-EC63E169960A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02c76efcbd810dfb55ffbf9a3ef649004599cc82","datavalue":{"value":{"entity-type":"item","numeric-id":4302863,"id":"Q4302863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346702$5264881E-D398-45E1-9EE1-5B052CFA4D5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3aa37c52f22d71444ff2effa0fe3ce6d3f742d7","datavalue":{"value":{"entity-type":"item","numeric-id":5905678,"id":"Q5905678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346702$F320D2C0-E2D0-4FB5-999C-8F57D2B87A87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5670f34f7f97e1f73ed327c2ad2e07b09b07d505","datavalue":{"value":{"entity-type":"item","numeric-id":1168988,"id":"Q1168988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346702$0D36A446-0CD3-4F70-955C-196E6CBF0CB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5358f45dde506733eb850bb6e2321f4115a61410","datavalue":{"value":{"entity-type":"item","numeric-id":684403,"id":"Q684403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346702$60DED840-7A17-47F5-B89C-1E4DF201F2F6","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":"Q1346702$F5EDB198-05E8-471D-B7EE-D4F013F6D8C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7db3468346fcce29d2fe703e3816d1c0ffadbf3a","datavalue":{"value":{"entity-type":"item","numeric-id":1224109,"id":"Q1224109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346702$665A3B6B-A959-4974-BC52-65452581AF97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9387bbd38b0874a230355988a020913f3259fce1","datavalue":{"value":{"entity-type":"item","numeric-id":3219751,"id":"Q3219751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346702$C80E9DA3-8C89-4582-BCE7-5062C3E9F054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03789c1b867b6455d209db88a5ef320f8e404383","datavalue":{"value":{"entity-type":"item","numeric-id":1342858,"id":"Q1342858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346702$94752FF5-AE4A-4D6D-A477-2B61E5ADD470","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346702$A32C5E72-A526-4861-9029-3BF030D40CDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89324d361b37a034b5349ba872fc20e8e4a8c32c","datavalue":{"value":{"entity-type":"item","numeric-id":1112724,"id":"Q1112724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346702$7DD5AB15-EAF5-42A2-8908-DE7F8A522025","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0611c8fede42ac100885c81ef1a90e51ba7e3b3","datavalue":{"value":{"entity-type":"item","numeric-id":1106724,"id":"Q1106724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346702$26DEB463-4067-4EC4-8112-97D4C5400C25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcdf0f8c0387a6648a8c262f3b165c4b253ed983","datavalue":{"value":{"entity-type":"item","numeric-id":3481743,"id":"Q3481743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346702$8E6DC46F-E62A-4BA5-A3FB-1FA44105D369","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e27993bfa7027ca937386f237c9ace48aad19b4","datavalue":{"value":{"entity-type":"item","numeric-id":6077050,"id":"Q6077050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b20ff0293abe108cc1c47ee739307f54ce21d4c5","datavalue":{"value":{"amount":"+0.7979298233985901","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":"Q1346702$3EC893A1-D576-4CC4-8A82-944FA169A89F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dbcc0a2554837e792494ed689577bec375184654","datavalue":{"value":{"entity-type":"item","numeric-id":3010385,"id":"Q3010385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aebece3f50f4712f961bb0af2bf81a78adff5a17","datavalue":{"value":{"amount":"+0.7901976704597473","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":"Q1346702$51BBCC3C-FAC8-4D13-8E5A-CEE32D85E431","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb5430532b4dcc203369336e553ebc483162c33a","datavalue":{"value":{"entity-type":"item","numeric-id":3167362,"id":"Q3167362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73bd5df329fd109e94bde9aa8cb5e6899f6db8e8","datavalue":{"value":{"amount":"+0.7899778485298157","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":"Q1346702$5615025C-E7AC-49CA-B9A6-89BA572A5603","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8d92b0895f98053b08e59d3d4b204530545328a","datavalue":{"value":{"entity-type":"item","numeric-id":3078381,"id":"Q3078381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"190a5b7ccde1194c611ca2f573ee3817e7d3f423","datavalue":{"value":{"amount":"+0.7869433760643005","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":"Q1346702$4D32C092-8AB0-4613-96D9-3734B2D45AD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d18d69b2b969de066747bb94cff0d519aaf57f6","datavalue":{"value":{"entity-type":"item","numeric-id":1356038,"id":"Q1356038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a232dcbe8029c2973902cfa1b225a13c625c884","datavalue":{"value":{"amount":"+0.7824731469154358","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":"Q1346702$B02C779D-50C7-42CA-A3A2-79C6021322B6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Weighted fractional and integral \\(k\\)-matching in hypergraphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Weighted_fractional_and_integral_%5C(k%5C)-matching_in_hypergraphs"}}}}}