{"entities":{"Q1186549":{"pageid":1197298,"ns":120,"title":"Item:Q1186549","lastrevid":66445563,"modified":"2026-04-12T10:08:18Z","type":"item","id":"Q1186549","labels":{"en":{"language":"en","value":"Expressing combinatorial optimization problems by linear programs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 36798"}},"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":"Q1186549$1DC2F244-E94E-4EFC-92A0-157BBFDBC32B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ff4873cd321aa8a7b7b23075585ea7953358466f","datavalue":{"value":{"text":"Expressing combinatorial optimization problems by linear programs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1186549$8D24FAD4-4DC5-40D3-86A6-9C834945B635","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5198528ddad645cdf9fc9c8d4c60b344860c613d","datavalue":{"value":"0748.90074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186549$3F0C1166-05DF-4D24-88C1-5EA30617CF7B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5e7821a3ef568ca827e8aaca5db53b5d4ddd3f09","datavalue":{"value":"10.1016/0022-0000(91)90024-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186549$815E012B-7842-4E0F-89C5-0F5D5887D446","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"64789e48fd3ab0a44b5ae0aa6d85c1c024312026","datavalue":{"value":{"entity-type":"item","numeric-id":458479,"id":"Q458479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186549$B54648FD-D0EF-41F7-ACAE-3A1443D79CD1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186549$992A8905-280A-404D-8376-590DE4A16C8B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1186549$A06D3E02-F9DD-4F6D-A99B-70E384102C2B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a3bd879eacf310ca99cefe3c23d1b42aec22ab44","datavalue":{"value":"The \\({\\mathcal P}={\\mathcal NP}\\) problem is investigated. The known \\(\\mathcal NP\\)- complete problems can be formulated as an optimization of a linear function over a convex hull of feasible solutions of the problem. Such a representation does not provide an advantage because of the exponential size of the obtained linear program (LP). The paper aims at analysing the possibility to reduce the size of the LP. Adding new variables the author proposes to transform a polytope of the LP to a specific form, named symmetric. Roughly, it is a polytope that remains ``invariant'' under any permutation of the initial variables. The main result is that the travelling salesman problem and the matching problem cannot be expressed by any symmetric LP with a size less than exponential.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186549$211B1E0D-2ACE-4D3C-A591-7E14A15128D7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186549$6AA9BE65-9A2F-44CD-9926-0D5F2213A74B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8ede024a2e42be41193baf32f90dd58f10db2ea3","datavalue":{"value":"52B12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186549$407B73BD-246A-438F-9E9C-37B663CF7E96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186549$B92AC226-6D37-47F4-9FDB-4F7DEA757865","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186549$3EF66343-B97D-46A2-AE5E-DA23E03A20C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186549$9BBE50CE-1A45-449C-8ECC-CF4A28E4D981","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"480088915df1f62946b6ccda15b4de0565a39ac7","datavalue":{"value":"36798","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186549$3F5CFB7E-B3CF-4387-8C43-826CC878E5B0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"40ec6fa91177ac519cc2405fc20f4279f719b776","datavalue":{"value":"symmetric linear program","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186549$6FDB49C1-C466-4D31-8DBE-49A56862E38A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3434597b5e97212b870ea6c9c881e7db3d38a546","datavalue":{"value":"transformation of polytopes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186549$7C3433EB-D603-45B5-9804-889B9BAB7D1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b76c57478e7480f586895f73fe9158887c3cad6c","datavalue":{"value":"travelling salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186549$FA80CFA2-0C53-4C3B-8D08-7D0BFF8CF237","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"56922b44f4b77c888d5a91237cc4964d535123f5","datavalue":{"value":"matching problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186549$063A0225-6D56-49BB-8CCF-ADFBDF668D68","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"1032137749ff345ae88df7b48231415b5ba374c8","datavalue":{"value":"Q56084006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186549$708D3928-27E5-458B-9F8E-F1EDB3352BA1","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":"Q1186549$38DE4637-07F8-4DC7-8C44-171901037DCE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186549$CA7F6FF8-76F3-4E74-9080-2A787F2F9A9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8a74f042ba1f29a12a670ab9d659cf777707121","datavalue":{"value":{"entity-type":"item","numeric-id":798301,"id":"Q798301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186549$8176E169-F81A-42E8-902D-0F98BC9AC628","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86f1036f52c9d084642933ae13a25638be140f18","datavalue":{"value":{"entity-type":"item","numeric-id":3039039,"id":"Q3039039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186549$23FA9329-C367-49B8-838B-2C9ADF7D9F99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18bf67666549968e21bcfc545117ac605c5708ff","datavalue":{"value":{"entity-type":"item","numeric-id":1255780,"id":"Q1255780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186549$75563207-B54B-4866-9E40-915CAEE31468","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bd8b848f40aaa3f56b8b15df38fbe662aeb1afa","datavalue":{"value":{"entity-type":"item","numeric-id":5516087,"id":"Q5516087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186549$7327DFD1-9873-426E-958D-74CAB7C17C82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186549$BEAEBD0B-5373-4B48-83C8-D3A6BEAA66B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ca8e2226bc49403f5d34bedd57297744e386790","datavalue":{"value":{"entity-type":"item","numeric-id":1168215,"id":"Q1168215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186549$997E110B-2D2D-46AF-A7D8-3519C66FF2D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5df2408c5166f2c5365f8bd9e6f2305fde6f0b9","datavalue":{"value":{"entity-type":"item","numeric-id":1214165,"id":"Q1214165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186549$A0B83F0D-2390-44A4-AFA3-42BE09B1531D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0b86da6901907b4b60c4d755cbdefb3d87af7f5","datavalue":{"value":{"entity-type":"item","numeric-id":761967,"id":"Q761967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186549$21F26C7A-0EE2-40A8-853F-4422529D9735","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97236fbeb6b6b2bba840114a8ba2f0448b9619f9","datavalue":{"value":{"entity-type":"item","numeric-id":4197641,"id":"Q4197641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186549$64AED505-AF64-4D19-8F41-794C63F52542","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"513dcedacea841939b838d72464763f37c9be4c6","datavalue":{"value":{"entity-type":"item","numeric-id":3741078,"id":"Q3741078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186549$75FAD59F-33DE-403E-9853-7C13E60A7F1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4dfff9233f6b4b6b3993452d7700b95ebd96d4f","datavalue":{"value":{"entity-type":"item","numeric-id":3496158,"id":"Q3496158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186549$B7B6F316-A644-4AB6-8E73-AD55C94CBD02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4fa5c0efe0c39997534bb44636c6730a4e42c655","datavalue":{"value":{"entity-type":"item","numeric-id":3965907,"id":"Q3965907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186549$A5DFC444-E405-4775-A444-D0415A6EE9AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c5769e6e6a35ae57b366b486d7b893a8167041d","datavalue":{"value":{"entity-type":"item","numeric-id":1089267,"id":"Q1089267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186549$C35FC78F-4D91-4229-AFC8-13506F586C60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"800321fe9f6efe205a2eb283e0da5841a2b5eaad","datavalue":{"value":{"entity-type":"item","numeric-id":1061485,"id":"Q1061485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186549$FEEA960E-8B11-4AC5-8A36-FA48A4330B33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14e822d0f6871d5df9de9fd97a15be05d850e629","datavalue":{"value":{"entity-type":"item","numeric-id":1071001,"id":"Q1071001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186549$84FC8701-90E2-417E-9823-8EE152F7865A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56c6c299e15ddeb001671e573dc9a5439e5a86a0","datavalue":{"value":{"entity-type":"item","numeric-id":3818127,"id":"Q3818127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186549$10B0023A-DEFF-4C4A-B33A-20921EF7C6A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d38757c8fcedd15751dfe68258cf952a44ea5c53","datavalue":{"value":{"entity-type":"item","numeric-id":1168734,"id":"Q1168734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186549$837585AD-A480-4EF4-8289-62DE49441CC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed5cab814cd603492c1673559e52eda9669c1aa7","datavalue":{"value":{"entity-type":"item","numeric-id":5512231,"id":"Q5512231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186549$C0C4FC03-4062-4368-A00B-9E07CB08B507","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"511896c340d2eb7ea1af2390f73bb18ea0722523","datavalue":{"value":"journals/jcss/Yannakakis91","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186549$D03E220B-3074-4CDB-A0AE-771FE4EF3610","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cd3ea8480e5c8b4ada6502bdca6fbf89b373b51","datavalue":{"value":{"entity-type":"item","numeric-id":5056416,"id":"Q5056416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf8dedd0b8b151ea7b45a1e6eba5478978845475","datavalue":{"value":{"amount":"+0.8368239998817444","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":"Q1186549$05B5745D-D278-4CE1-B7A0-FA397860CA41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e4bae74ae89ababd23d4b58b3e7ec9206217cea","datavalue":{"value":{"entity-type":"item","numeric-id":2796404,"id":"Q2796404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8737922a4ea84157eda6b15d9e501777c6de4d8","datavalue":{"value":{"amount":"+0.8236487507820129","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":"Q1186549$151C8496-043C-429E-8AE4-7465F76DE3F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0b794d6cba39a9af7e1730fa4da7d8cbb7461f0","datavalue":{"value":{"entity-type":"item","numeric-id":3520785,"id":"Q3520785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7730ac5558867cf2c03dc5acb61a0354547329be","datavalue":{"value":{"amount":"+0.8055667281150818","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":"Q1186549$E2D4C22C-D38E-4A91-8AF3-B3B51E54E635","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a924f13649f32272cac5101e30692c0795af976a","datavalue":{"value":{"entity-type":"item","numeric-id":4575655,"id":"Q4575655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aca17d2b8518fb2dbfa0ebaaaf84429a92358f1b","datavalue":{"value":{"amount":"+0.8013788461685181","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":"Q1186549$6AD1E1AE-C0E7-40E7-BC2C-BD0271E6BFAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c0863e04709378d74bfe75e5d4cb11a3e37e3f4","datavalue":{"value":{"entity-type":"item","numeric-id":5415468,"id":"Q5415468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef11373dfa10ebd74bdfde7b6c90ad2307b89946","datavalue":{"value":{"amount":"+0.8012223839759827","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":"Q1186549$945539CD-09CB-4276-936B-089FEDC67BA5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Expressing combinatorial optimization problems by linear programs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Expressing_combinatorial_optimization_problems_by_linear_programs"}}}}}