{"entities":{"Q879965":{"pageid":881813,"ns":120,"title":"Item:Q879965","lastrevid":65079588,"modified":"2026-04-12T00:10:51Z","type":"item","id":"Q879965","labels":{"en":{"language":"en","value":"Polyhedral properties of the \\(K\\)-median problem on a tree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5151336"}},"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":"Q879965$192C1CF4-5524-45E4-BF1C-24A80B37E11D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"914c0880309e03a18045d083fab18045dbdcb247","datavalue":{"value":{"text":"Polyhedral properties of the \\(K\\)-median problem on a tree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q879965$B8D2CA7D-1F11-4B5C-B167-8569F1ADF5CB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b884cc55e0a165391704e108b5cc3ffae9f68237","datavalue":{"value":"1130.90058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879965$93631E94-8970-4F67-BB07-7D5EC4E8B9A9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b5ebef6fa48ee85e4a2e4f09238a36b55b6a5d3c","datavalue":{"value":{"entity-type":"item","numeric-id":173864,"id":"Q173864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879965$BC882589-A826-40EA-B464-951676285743","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3aacf41965b3efad33788fa36f792533078bc783","datavalue":{"value":{"entity-type":"item","numeric-id":581215,"id":"Q581215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879965$7EE2AFFC-8F46-4C7A-85C9-284EE7C5F90E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"05537b32da8fc717ca6ec5ffba19249c61ae7bd8","datavalue":{"value":{"entity-type":"item","numeric-id":496436,"id":"Q496436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879965$8463F7DE-5BDF-43E8-8BD4-76DDFF9FA6FD","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":"Q879965$D337335F-A539-43B2-AE5A-42F3E816D8B2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3a7811dd6743febd92d5d1009397a7767778f669","datavalue":{"value":{"time":"+2007-05-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":"Q879965$2884D1FA-270B-493B-9521-260BB20D2C35","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7fec997f162b31fe06321c4d1498e5b7e27f8d06","datavalue":{"value":"This paper investigates the polyhedral structure of the \\(K\\)-median problem on trees. Despite the problem being solvable in polynomial time, no exact LP formulation is known. The authors give an IP formulation and show that for every tree with at least 4 vertices there is a dataset such that the polytope \\(Q_K\\) of the LP relaxation of this formulation is not integral for all \\(K \\geq 2\\).   They investigate the structure of \\(Q_K\\) and show that \\(x^{\\text{LP}}=z^*\\) if \\(T\\) is a path or a 1-star and that these are the only trees with this property. Furthermore, for general graphs, \\(Q_K\\) is shown to be integral if and only if \\(K\\in \\{1,n-1, n\\}\\).   The authors also show that \\(z^*/z^{LP} < 2-2/(K+1)\\) and that this bound is asymptotically tight. Next, they give a new proof that an alternative formulation for \\(K=2\\) is integral. This is followed by the identification of a class of constraints that they demonstrate to result in integer polytopes for all \\(K\\) if \\(T\\) is a 1-star.   Finally, a class of facets for general graphs and \\(K\\geq 2\\) is established. This class is then used to prove integrality of a new description of the problem for 2-stars.","type":"string"},"datatype":"string"},"type":"statement","id":"Q879965$7F814804-7CD6-4E32-8E54-501CA6F40B00","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ebec3fead859bfe042f90942bb009137165d63bc","datavalue":{"value":{"entity-type":"item","numeric-id":297048,"id":"Q297048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879965$5AFC886B-5D67-4515-A4E8-0DC15900C287","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"955a6ac68db8c67c1772255c707ed5eb1d2bad2b","datavalue":{"value":"90C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879965$20290ED9-9E53-4838-AA77-EA9791254C5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"78931806833c54190437f3675cf624ba3d256107","datavalue":{"value":"52B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879965$A6987893-C1DE-4069-AB0F-D65FFF6C4016","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6fc9ed28adf6c041e72138abc12e9460c821a545","datavalue":{"value":"5151336","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879965$664DB117-3CDD-4A34-9533-54AF134526A8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8da7014636974114679a3c504a7c408da3b1dbf9","datavalue":{"value":"\\(K\\)-median problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q879965$BA6B7039-31AA-424F-901B-3EB3CC7C58F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d65bfc3ff47bed0c2aa04f46b5ec6cca5d37629","datavalue":{"value":"polyhedral combinatorics","type":"string"},"datatype":"string"},"type":"statement","id":"Q879965$07D5D4C4-EAA6-40D8-BA92-8EEB62CF2EE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"747d0307b6dafcec6e50ba81d3396bbf3812302c","datavalue":{"value":"facets","type":"string"},"datatype":"string"},"type":"statement","id":"Q879965$512A3A1E-6043-4A92-9CFD-90D63BF8D8E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"716dac1111922ad89f28f3f7f9fca3441a4dfa26","datavalue":{"value":"valid inequalities","type":"string"},"datatype":"string"},"type":"statement","id":"Q879965$793469B0-65EC-4770-AE7F-231E8C4272D0","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":"Q879965$A7856651-CCE3-4FF7-AEF1-A4A2638CC89B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"516e2977dddd99aec873ba80b649a9ff12a86aed","datavalue":{"value":"https://doi.org/10.1007/s10107-006-0002-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q879965$B86EA91F-2B75-42C7-A6E6-78925C3FD7E2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b57a4c71663c9556abc782a7b06b9bf65f48e5a6","datavalue":{"value":"W2086058434","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879965$D0EBD098-5C18-4376-9CF4-562C24935B97","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2824c66b2ac5d07ef0caeb64cd87fdf93b22fce","datavalue":{"value":{"entity-type":"item","numeric-id":5175949,"id":"Q5175949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879965$920CC06F-D675-49EC-8B30-75FBB71D3D19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bab54c8603d5bb1a19bf0e6988434af78283a7a5","datavalue":{"value":{"entity-type":"item","numeric-id":5930734,"id":"Q5930734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879965$0DC8FC64-72DF-4909-B1C3-AB9AF7C4C5E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87e27f9402fae8f3cf272a4cfb7ed86f0611da43","datavalue":{"value":{"entity-type":"item","numeric-id":1101129,"id":"Q1101129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879965$71BB14B1-18AB-492F-8E85-6C30664E56BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"388f16881954e05287e7914a10c9ca4258368089","datavalue":{"value":{"entity-type":"item","numeric-id":3321801,"id":"Q3321801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879965$58AD57C1-8E6E-4373-B44A-953FDE49E0DD","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":"Q879965$EBD855FA-2C46-4F97-9A81-1AF84DEBF0BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2a0953824f4019c46487b0eea4e008f767bc46b","datavalue":{"value":{"entity-type":"item","numeric-id":3971521,"id":"Q3971521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879965$2FCC7A5A-4134-4935-A8C9-BE55E8FFE514","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"713e82ac9e8a1be90ecdf20e49c91764c51169c3","datavalue":{"value":{"entity-type":"item","numeric-id":3906433,"id":"Q3906433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879965$6268A45F-AD22-4B6D-8471-5884E2F0C6AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ce3dd1e6a6aeec7252a57f5331a4a5908bf3ad3","datavalue":{"value":{"entity-type":"item","numeric-id":2564302,"id":"Q2564302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879965$3F8CC273-1177-48A9-8DCB-160F52BBA964","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2812bfd9467b81f6bb8bd5396abbb0f9615e53fe","datavalue":{"value":"10.1007/S10107-006-0002-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879965$B3AA6569-ECAC-4CEC-8CA7-701F842BDD48","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cec5d2aaf7d918173b9ef6614adeccda885c443","datavalue":{"value":{"entity-type":"item","numeric-id":4779149,"id":"Q4779149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a38d9fddf309bdf48c0dbd3e8aa6fde799af8dad","datavalue":{"value":{"amount":"+0.9191319","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":"Q879965$53D5D152-6D1F-45CD-85E7-A53142DD1EC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b85aa59c1ed7571e6048cf9cdf1b998d6866b741","datavalue":{"value":{"entity-type":"item","numeric-id":2564302,"id":"Q2564302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"524d0f63490ae1cd680735867c822fff28a1aaec","datavalue":{"value":{"amount":"+0.90540034","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":"Q879965$9C2E7ED0-F258-48DA-917B-17762050DB1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c0b9f28eee10fbbc88fda57855100237bf2a202","datavalue":{"value":{"entity-type":"item","numeric-id":6163962,"id":"Q6163962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76a653d75279ccc7a5da5411cb4578547300db94","datavalue":{"value":{"amount":"+0.8995441","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":"Q879965$3063929B-540E-4CC8-9DC8-260E2528B072","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b1e886315390317fe554dac02b9a2aecf9a9501","datavalue":{"value":{"entity-type":"item","numeric-id":1923615,"id":"Q1923615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a673da632b375e52b835d7a390569a3db1b6d002","datavalue":{"value":{"amount":"+0.8975829","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":"Q879965$567F3C94-C215-4EB8-881B-8FDF2BDC3D46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d92d37378bb662d0861028f69b3feeaab975db91","datavalue":{"value":{"entity-type":"item","numeric-id":783030,"id":"Q783030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8035958a43ff7180202fc19ffadce8968295ba11","datavalue":{"value":{"amount":"+0.8971534","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":"Q879965$C253C0E3-273D-499A-9E8E-F5FA36AA24C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bacd963780351a5032a93abdd84541ae8667ad43","datavalue":{"value":{"entity-type":"item","numeric-id":2773613,"id":"Q2773613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a619fcf8788d4e471ffd445c6a469315296e1be","datavalue":{"value":{"amount":"+0.8970028","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":"Q879965$BD691ED4-9DDB-4399-9AB2-F00A13E51ECA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e83babbf9a16221c01b43d3a6954083e08098949","datavalue":{"value":{"entity-type":"item","numeric-id":5162023,"id":"Q5162023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00721dd025a45da2c199391c08d0461f239bcb56","datavalue":{"value":{"amount":"+0.8957413","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":"Q879965$7BC17653-BF61-4999-BA68-3559AE9CA419","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0900bae123b6340979e1745f3e7ce1d700d6ba21","datavalue":{"value":{"entity-type":"item","numeric-id":2339828,"id":"Q2339828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d50e7a0035e3e315a345f6df9f59aaf8e36dea5c","datavalue":{"value":{"amount":"+0.89571375","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":"Q879965$16A481BB-6D79-4938-87BE-EDF9F67C6652","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fab7d163f1bbe740771d550e295ee45a67a8c63e","datavalue":{"value":{"entity-type":"item","numeric-id":2434979,"id":"Q2434979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40a0a84e99cd7323e91296273ccf22e569ef4046","datavalue":{"value":{"amount":"+0.8946895","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":"Q879965$EE7535E4-17E8-4213-88C8-AE6588AC4EB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f76753000fa43d3d66b551162032d1aa9810c6d9","datavalue":{"value":{"entity-type":"item","numeric-id":4019567,"id":"Q4019567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6351b149d81a350557830d1fb3b5b0bc749b678a","datavalue":{"value":{"amount":"+0.89312375","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":"Q879965$FB6F50A0-0353-446A-B00B-7B16E3667D63","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Polyhedral properties of the \\(K\\)-median problem on a tree","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Polyhedral_properties_of_the_%5C(K%5C)-median_problem_on_a_tree"}}}}}