{"entities":{"Q1122477":{"pageid":1133226,"ns":120,"title":"Item:Q1122477","lastrevid":66807801,"modified":"2026-04-12T13:00:52Z","type":"item","id":"Q1122477","labels":{"en":{"language":"en","value":"On the 0,1 facets of the set covering polytope"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4106601"}},"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":"Q1122477$B6A9F4C1-B474-41E4-AD30-D2556973EB2D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b1131319439ea71a0808e634050f4ee12acc4665","datavalue":{"value":{"text":"On the 0,1 facets of the set covering polytope","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1122477$7CDF9C98-80DF-43C8-BAE9-9B9B013F709D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9e31edd606272ac905cc1894987860e5f88604e1","datavalue":{"value":"0675.90054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122477$CE3BC683-0B51-40AD-A93A-C9496056C55F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d4543d607f17b090fe8d3aaae574747d447ca895","datavalue":{"value":"10.1007/BF01582277","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122477$24C8EAE5-66CE-4F77-B532-340126E2407D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3de34c40bbd436145163ee502934245d6246cef6","datavalue":{"value":{"entity-type":"item","numeric-id":173870,"id":"Q173870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122477$4B7B69AA-E600-4AFF-9F7F-908F7F4D48D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"feb07495fa8de76912d587852b3aa20404b344f1","datavalue":{"value":{"entity-type":"item","numeric-id":163019,"id":"Q163019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122477$FFC913BE-7875-4A39-956E-9BDDA9B3F8BA","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":"Q1122477$D294DE24-3349-417C-87E9-5A826E34C8AF","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":"Q1122477$F5DE5B99-41F7-4322-879D-65F8091BDAA0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e6d3f7c2749237b349f63f91572ded1229a64809","datavalue":{"value":"Necessary and sufficient conditions for an inequality with 0-1 coefficients to define a facet of the set covering polytope associated with the 0-1 constraint matrix A are given. The work is influenced by the results on the set packing problem, where also the notations are defined in the intersection graph of A. For the case that A is a matrix of odd order and the matrix \\(H<A\\) contains exactly two ones per row and per column it is shown how to decide in polynomial time whether \\(\\sum^{n}_{j=1}x_ j>(n+1)/2\\) is valid. This yields a facet of the set covering polytope.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122477$884A59D5-76CF-4E7C-85D8-36150E0ED660","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6958ea3363ca9244e0da0201efd237a8410f9a0c","datavalue":{"value":"90C09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122477$CBE484A5-A075-4DA9-A0CE-18C17D495EE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ddd8cb1932c6bc41681458db5f685a2a286fde55","datavalue":{"value":"52Bxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122477$D4E11881-9175-4BE7-A277-D36070A95FC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122477$FBA36731-A1C0-4730-8889-06F7A56E076E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122477$BC7B719A-FBB2-49A1-9478-11F22E5B4C92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122477$832641F0-7E07-4885-AA34-54EC4461597E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e28004808e04905de7013ae8449fa2688839cfda","datavalue":{"value":"4106601","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122477$57958BA0-2F1D-42E6-BD9C-8531E0081776","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"826588fa69c00b8a1a44fba987b4a4fd45caa4cb","datavalue":{"value":"facet","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122477$3C534BA6-F87D-49F0-BA03-B0B6332F6F47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b5391c4d2e8dab5ef32a09f3b8903133a4e5c2d","datavalue":{"value":"set covering polytope","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122477$BF995266-AAA6-49AC-8F59-B1C698BCA177","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"232bc32bbdcf46d57769ffd90174083620b57c68","datavalue":{"value":"set packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122477$8C832546-6456-4903-83A2-D0407FA641AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bc0d5058cf7773f67ff6548c4fa33edb07db16a","datavalue":{"value":"intersection graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122477$D696D7AF-D825-4C60-BD83-52F963F838DF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"773ccef7b8ad8b5275f8369121560572282db928","datavalue":{"value":{"entity-type":"item","numeric-id":976026,"id":"Q976026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122477$B6CF9179-5B81-4EE1-80BC-29991F2386FE","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":"Q1122477$7D31ECC2-0BD9-4816-9246-5B3E9C927B7F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"23b610d0e60efe078df928dad869df8d8b613489","datavalue":{"value":{"entity-type":"item","numeric-id":3875703,"id":"Q3875703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122477$83C3A7DD-2B92-4A69-BFFA-1FD874F538AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b49831ffa1b847141ffe4d70b0a36ebaa8beccc","datavalue":{"value":{"entity-type":"item","numeric-id":3875704,"id":"Q3875704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122477$1656E48D-6A08-4229-934D-33A297BF5D14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c67729b1304819cd23b80be0e5e92a17db360b2d","datavalue":{"value":{"entity-type":"item","numeric-id":4117604,"id":"Q4117604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122477$33CF6582-5F49-4123-B6CD-C5294CD3C311","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a136c278c64092e77d36d96bc00795316a9cdbc","datavalue":{"value":{"entity-type":"item","numeric-id":1121793,"id":"Q1121793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122477$8CA3E086-7B79-474C-9F97-FA249998976E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"371e47a1ddfcb244997f928630b9bc7dc228dccc","datavalue":{"value":{"entity-type":"item","numeric-id":3892882,"id":"Q3892882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122477$C5977330-7BCB-47B3-8058-F908752A734D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15abf164381e188ffaaaa88e1e51e9c0b99bc916","datavalue":{"value":{"entity-type":"item","numeric-id":5659570,"id":"Q5659570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122477$AE8B5B5D-5F81-439D-9B49-5FFAF59D7C04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3343fb8da9aa59a36e8eb915e75407d17b08e7f","datavalue":{"value":{"entity-type":"item","numeric-id":3321802,"id":"Q3321802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122477$1325C87A-765D-48D3-B161-F32F200A224A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3ecc4ed854f4c2fb93ed2e8327283eb9cc15cf0","datavalue":{"value":{"entity-type":"item","numeric-id":1393418,"id":"Q1393418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122477$B5AFB9DB-5B17-4781-9060-E0151338FB69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4994190b45c92d2283f1bee86b7a0b36b905564d","datavalue":{"value":{"entity-type":"item","numeric-id":1070249,"id":"Q1070249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122477$DE683B65-30B1-4B5B-B9BA-ED62EDC2E0EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4066ad3bb12ff73514def45aabe2664487cf38eb","datavalue":{"value":{"entity-type":"item","numeric-id":3945954,"id":"Q3945954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122477$3430DEFD-5C47-48C6-9F45-DB021CC29AA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78cd4360ea9f152efe54d233fc8cd48df1287364","datavalue":{"value":{"entity-type":"item","numeric-id":4133404,"id":"Q4133404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122477$15B613B9-DB75-46EB-9C04-DCE96954E80D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c72e5144fc35b1673d6188020da4e95cfd8a1344","datavalue":{"value":{"entity-type":"item","numeric-id":4766816,"id":"Q4766816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122477$9A397769-FCE1-49FE-8D19-F5E8169AEA6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e138268b388c59cc350422a307264a1cbe02595","datavalue":{"value":{"entity-type":"item","numeric-id":5181532,"id":"Q5181532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122477$A428B10F-BB13-4FC4-AD47-4249960FB639","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce8afc2154185528fabedbb37fbd1892c69b988b","datavalue":{"value":{"entity-type":"item","numeric-id":1122481,"id":"Q1122481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122477$B4BE0198-88BE-4019-BC12-882C22DD7643","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6542352e47dd34fbda695c41fd84595fda3ecebd","datavalue":{"value":{"entity-type":"item","numeric-id":1220520,"id":"Q1220520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122477$AA384F05-EC7F-4DEC-8CBF-7B946115A0CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81a237935a097d7239508d750e7c20bbe09cf677","datavalue":{"value":{"entity-type":"item","numeric-id":4119038,"id":"Q4119038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122477$450AFF4C-6D23-44C2-AC27-8A7054FC46D2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"649dc594510d3d097a9dd434f31531799c7641ac","datavalue":{"value":"https://doi.org/10.1007/bf01582277","type":"string"},"datatype":"url"},"type":"statement","id":"Q1122477$CFEED843-7DF2-410E-8894-8FF1B5F21FE2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d2ac669916c96032ffd75d849898e32e46631cc6","datavalue":{"value":"W1992197964","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122477$7767EF73-EC8B-47A1-A24F-B754A2E67C76","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c0cf9f3d07896fb2a2861b6d4df1c13c20df678","datavalue":{"value":{"entity-type":"item","numeric-id":1121793,"id":"Q1121793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef1ae861e60016dcb150d40cf8b2e468da05ded4","datavalue":{"value":{"amount":"+0.9026351571083068","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":"Q1122477$2CBC2237-9A0C-4C63-9479-031753DC0ED3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2955b3fe93aae90e5f3708abfc215f6d44dc284","datavalue":{"value":{"entity-type":"item","numeric-id":1122481,"id":"Q1122481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb813e61fa1c608a237c6321707ec0e4f1618427","datavalue":{"value":{"amount":"+0.8971483707427979","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":"Q1122477$5FBC3A99-6A73-4DB5-8157-7CC2F9429A30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5537a7284817b93a15d9e87e5cd0e1f1296accb5","datavalue":{"value":{"entity-type":"item","numeric-id":1265897,"id":"Q1265897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a889e9f9cd63511d3f269b0696a3fd2945c09f9","datavalue":{"value":{"amount":"+0.8846811056137085","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":"Q1122477$D2D1F962-13DD-4B70-864B-2ED92F5C7886","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d5a0d1c1764f7657baf79e584f1cc7b87127aba","datavalue":{"value":{"entity-type":"item","numeric-id":2636828,"id":"Q2636828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a889e9f9cd63511d3f269b0696a3fd2945c09f9","datavalue":{"value":{"amount":"+0.8846811056137085","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":"Q1122477$DFE68123-B81C-489D-8878-209A092881C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"202f12a5f1b79e992a931df11d4cef869b69cb77","datavalue":{"value":{"entity-type":"item","numeric-id":584072,"id":"Q584072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6403b8113d3f72f66d4abb884f7e3fcc10e3322d","datavalue":{"value":{"amount":"+0.8486701846122742","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":"Q1122477$F3C4EE79-719F-4712-802F-9BDCBE1AEDB6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the 0,1 facets of the set covering polytope","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_0,1_facets_of_the_set_covering_polytope"}}}}}