{"entities":{"Q1118612":{"pageid":1129361,"ns":120,"title":"Item:Q1118612","lastrevid":69684945,"modified":"2026-04-13T08:41:49Z","type":"item","id":"Q1118612","labels":{"en":{"language":"en","value":"A generalization of Robacker's theorem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4095500"}},"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":"Q1118612$478E5F45-00A6-4AC3-845A-A626579F5670","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"95fd2565bbc61e4ce9e6595d5949122e7fbabd44","datavalue":{"value":{"text":"A generalization of Robacker's theorem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1118612$27A14DE9-CCE7-48BB-9A5D-30C18291048B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8213319c6192e400830c0f81f7a7891d525a546e","datavalue":{"value":"0669.05040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118612$DEEEAEE9-FB3B-4091-9841-96823FF6B6C0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a4e12a70387fcaaa7fc7bfce9ae83b729a75070","datavalue":{"value":{"entity-type":"item","numeric-id":1118611,"id":"Q1118611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118612$8B3EF4F8-7FBA-4D73-B5B9-506A80C25691","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f69677a08f56ea4590edc787323131a4bdc2e419","datavalue":{"value":{"entity-type":"item","numeric-id":686727,"id":"Q686727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118612$DFA66BA3-C040-4185-9511-D8A2CFD1D7C9","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":"Q1118612$E61DF90D-2F4D-4681-B023-573325B689E9","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":"Q1118612$55C6BBA9-31D6-4B67-AEC5-6A182A2CFAF5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"97611000e6eae51ff7fdb64e716e756cce2cf175","datavalue":{"value":"Let \\({\\mathcal P}\\) be the polyhedron given by \\({\\mathcal P}=\\{x\\in R^ n:\\) \\(Nx=0\\), \\(a\\leq x\\leq b\\}\\), where N is a totally unimodular matrix and a and b are any integral vectors. For \\(x\\in R^ n\\) \\(let(x)^+\\) denote the vector obtained from x by changing all its negative components to zeros. Let \\(x^ 1,...,x^ p\\) be the integral points in \\({\\mathcal P}\\) and let \\({\\mathcal P}^+\\) be the convex hull of \\((x^ 1)^+,...,(x^ p)^+\\). In this paper we derive the blocking polyhedron for \\(\\{x\\in R^ n_+:\\) Mx\\(\\geq 1\\}\\) where the rows of M are integral points in \\({\\mathcal P}^+\\). We also show that the optimum objective function values of the integer programming problem max\\(\\{\\) \\(1\\cdot y:yM\\leq w\\), \\(y\\geq 0\\) and integral\\(\\}\\) and its linear programming relaxation differ by less than one for any nonnegative, integral vector w. As a special case of this result we derive Robacker's theorem which states that for a directed graph with two distinguished nodes a and t, the maximum value of an integral packing of forward edges in (s,t)-cuts into a nonnegative, integral weighting w of the edges is equal to the minimum w-weight of an (s,t)-path.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118612$EC693B40-5FAF-4408-93EF-FBFF17F56BA0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118612$B18C8D59-03D2-42A7-B4CE-56915D9B3DDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118612$65690B65-90F7-4F37-A64A-EAE9A30541C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118612$6018FF9D-FEDB-43A3-9B97-9E5AB958B2D7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9e9810e11639b90f1ce22737216ae358bbc9b89d","datavalue":{"value":"4095500","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118612$576DFF57-E1C6-4829-8C50-8125F2ACAAE3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9f2a96a2b64089759dd2d2593ced2328c88f9b6","datavalue":{"value":"polyhedron","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118612$768778F5-F125-4396-B585-3999A5D511F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8012a874fe85b6ae37dda8e04dee930cf246cc7f","datavalue":{"value":"blocking polyhedron","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118612$363E7796-5CE1-451D-85FA-821DF27075D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"54b964bd8f05d6c11aecfc13c94d815c7486420e","datavalue":{"value":"integer programming problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118612$EF435727-5721-4EC5-8568-3427A23F9766","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6bf023653318cc5b8c727563611596d2cf1a818a","datavalue":{"value":"directed graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118612$B080F2D7-FF9E-4006-9A68-633837C531A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dfb017dabe88e41f3994fb9f4f42e0e85511a44c","datavalue":{"value":"integral packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118612$42CB1F9B-C5E3-45EB-9D82-8517812021B0","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":"Q1118612$C2084FD7-B26D-486F-BE4C-D5889CB1CB6E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f70d362cfa7331a9394c39182700aab103850eb0","datavalue":{"value":{"entity-type":"item","numeric-id":5572841,"id":"Q5572841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118612$A8F45694-7BC5-4E52-B31F-DD9F5DA26070","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53e93f3e4d6e9828b6844029e6725d07275ebd57","datavalue":{"value":{"entity-type":"item","numeric-id":5620998,"id":"Q5620998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118612$414B765F-B182-41E6-8030-DC2FAFF7B842","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81d8a0ac67e074af2783991b082cd18a14315535","datavalue":{"value":{"entity-type":"item","numeric-id":5668263,"id":"Q5668263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118612$ACAEBE25-7DB7-41DF-A6DA-8A18874F696E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"838956d6be288d1dc8262556ca9ecc6197b91387","datavalue":{"value":{"entity-type":"item","numeric-id":4740329,"id":"Q4740329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118612$7EFCC403-7F9F-410D-A183-5BDC5939ECDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26424b49f4ae115f1942d0793dc574276746fa64","datavalue":{"value":{"entity-type":"item","numeric-id":3854942,"id":"Q3854942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118612$F8F7E333-166F-41D4-844A-6613B09AC6A2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"074b02014e575619c33afcc0bad277e89794ab2d","datavalue":{"value":{"entity-type":"item","numeric-id":4198784,"id":"Q4198784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5424969d1d2ab9b0ba65d0e76b03b78a5a61c06e","datavalue":{"value":{"amount":"+0.7703903913497925","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":"Q1118612$E33B4B12-36F6-4B8A-9928-5C7D135A35D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d92abc246ceecf96c02757043433c6c33918a541","datavalue":{"value":{"entity-type":"item","numeric-id":1082268,"id":"Q1082268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe6039313361547c5dd5512c8333a9964d560d30","datavalue":{"value":{"amount":"+0.7607553601264954","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":"Q1118612$DCE03D9B-B8AD-4006-A88F-C1F8F7769E03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06e7186583af144656bd2a4502cd5ec5b498390d","datavalue":{"value":{"entity-type":"item","numeric-id":3523273,"id":"Q3523273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e72cacaad581aa21003b5573e640af3778df387","datavalue":{"value":{"amount":"+0.7519049644470215","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":"Q1118612$14ABD996-26DA-4004-8CCE-7B2F1493C97A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83594eb6e977472a1d6044ae151ebf7254d578d9","datavalue":{"value":{"entity-type":"item","numeric-id":3565232,"id":"Q3565232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fcce101f382bc69c9f0db3878f22039c428d8ac","datavalue":{"value":{"amount":"+0.7454203367233276","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":"Q1118612$1AA229B7-6DCC-4E6B-B375-B684C27C4FFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"972c6cf5ab0fe64fec643b89b6e5e65e9f9f5de5","datavalue":{"value":{"entity-type":"item","numeric-id":3668292,"id":"Q3668292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63356bb94bbbf2288b9e95598b1ea100f97a3ee7","datavalue":{"value":{"amount":"+0.7390190362930298","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":"Q1118612$49BE6312-F2FA-4220-9E42-2F9F08A2104E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A generalization of Robacker's theorem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_generalization_of_Robacker%27s_theorem"}}}}}