{"entities":{"Q1925790":{"pageid":1936532,"ns":120,"title":"Item:Q1925790","lastrevid":57594966,"modified":"2026-03-31T13:23:39Z","type":"item","id":"Q1925790","labels":{"en":{"language":"en","value":"The quadratic Graver cone, quadratic integer minimization, and extensions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6116939"}},"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":"Q1925790$429B0796-E2A1-4027-9881-BF3DDBB3E67E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d6b1913566dd4854f19dec30859c89ad9d0640f3","datavalue":{"value":{"text":"The quadratic Graver cone, quadratic integer minimization, and extensions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1925790$A25FEC47-5BC1-444F-9C9C-BE037FCDEAF4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6307bade72b5d69f2c8ad26a0fd6dd2868a616e3","datavalue":{"value":"1280.90088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1925790$16C1F7D6-E963-49DD-8DCF-F740081C9079","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ae508c86f07cb97dfaea846bf22fad547f1c58eb","datavalue":{"value":{"entity-type":"item","numeric-id":170438,"id":"Q170438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1925790$C1DAC8C2-6A11-4592-8F62-06C208BE6ABE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"89ce9c0b4d738f8fe245f91d1d3566a3fef6869a","datavalue":{"value":{"entity-type":"item","numeric-id":314826,"id":"Q314826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1925790$DA5DA0ED-2326-4282-9EF0-E32DB9467414","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bd23bf92d175c5eb8d19ac1d69ef172f348bec1c","datavalue":{"value":{"entity-type":"item","numeric-id":1925789,"id":"Q1925789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1925790$FD70A3A9-E86D-4669-A3EE-FECF3E5B92F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dc0bd20b49fc5f8c46a35ef243535d5a3fb2bd74","datavalue":{"value":{"entity-type":"item","numeric-id":210498,"id":"Q210498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1925790$5FA1DCC3-7C27-4A99-92BE-D3507668864C","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":"Q1925790$B43B1AC0-6B06-4F3C-A878-FE276F11583D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"89237810e2607c40640d822ba13c3a4357a2a395","datavalue":{"value":{"time":"+2012-12-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1925790$F4A88CD8-EB78-4C36-A927-D46604882C78","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"93786b88f07882e860697d9de2a06d7cd798c8d3","datavalue":{"value":"https://arxiv.org/abs/1006.0773","type":"string"},"datatype":"url"},"type":"statement","id":"Q1925790$11EE374F-E47F-43DF-B323-706BB8263BDF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f17a370846d12f1d7edd394a33cbb25463400494","datavalue":{"value":"The paper addresses quadratic integer programming problems. The authors first observe that it is NP-hard to determine the optimal value of a quadratic integer programme  \\[ \\min \\{x^TVx + w^Tx + a: x \\in \\mathbb{Z}^n, ~Ax =b,~ l \\leq x \\leq u\\} \\]  even if the Graver basis of \\(A\\) is given and even if the objective function is convex and \\(V= vv^T\\).  They use this as a motivtaion to study special cases of quadratic functions for which this problem can be solved in polynomial time. Their main results show that this is the case for matrices \\(V\\) lying in the dual quadratic Graver cone (defined in the paper). As a special case, the result also holds for separable quadratic programming with the objective \\(\\sum_{i=1}^n (v_ix_i^2 + w_ix_i +a_i)\\), where \\(v\\) belongs to the dual diagonal Graver cone.  The results are extended later to show that for more general polynomials. It is shown that for every fixed \\(d\\) there is an algorithm that, given the Graver basis, solves  \\[ \\min\\{f(x): x \\in \\mathbb{Z}^n, ~Ax=b,~ x \\geq 0\\} \\]  in polynomial time for every degree \\(d\\) integer homogeneous polynomial \\(f\\) in a cone of certain tensors defined by \\(A\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1925790$8B939FB9-9F72-4F4F-8AF8-8EEED9AF0624","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":"Q1925790$16EAF7AF-7B66-44D3-B312-FB634662CD94","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1925790$A9F96F3F-BDD2-4D86-B4C1-97588E36DCF6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2e6892219b0ecdcff1efbfe066153e43421c1c99","datavalue":{"value":"6116939","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1925790$6886E3CA-DB31-42BF-BAEA-621C7674C99C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e0a438e9092bcf192a5c493b52b0717e88c2591","datavalue":{"value":"integer programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1925790$88D05A15-F60A-4F35-B525-594890DA4F49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a94043f34169830e7973c56cc9fe49d0f845066","datavalue":{"value":"Graver basis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1925790$31092DFE-9067-4BC4-A91D-4F2EB959EDD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c429e3ca3222ec2556792a4d502baf74255be451","datavalue":{"value":"quadartic optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1925790$FDE8E088-88F4-4A19-8785-1CFEAA4BFA4E","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":"Q1925790$75BFD702-DC4F-4119-AD97-6732AAF1A27E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e5a266fbbed1ce2daa216335d5c51686f2f844f4","datavalue":{"value":"W1770886307","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1925790$1D5A4870-207D-414D-A161-092D2D9ED151","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e15f182660bade51be1b76d62025b6b5ad24d393","datavalue":{"value":{"entity-type":"item","numeric-id":659795,"id":"Q659795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1925790$D95E916B-60BE-4BA1-938D-CC6A61313294","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c6a3b07179545307116abb178ab043db2cd44b9","datavalue":{"value":{"entity-type":"item","numeric-id":1017675,"id":"Q1017675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1925790$3397A618-4FA6-436D-8AB1-63CD8FC268EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c441850fd1ee5136afdefb19e0a15861cdf6543","datavalue":{"value":{"entity-type":"item","numeric-id":951095,"id":"Q951095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1925790$BC20A469-4F2E-4C47-BCA7-6AEB29F7A0A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f0ffad640823aca232d0514da887f178360be8f","datavalue":{"value":{"entity-type":"item","numeric-id":5757350,"id":"Q5757350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1925790$2F2C8C48-092E-49C3-821C-561333C3AD08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"666e36d82f5b2cbdbb1f9caccf659c29f574a451","datavalue":{"value":{"entity-type":"item","numeric-id":3601986,"id":"Q3601986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1925790$3B50BE63-4544-47FF-A596-ADD89DC1E1F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e5a002d92c6f7796c99b9e7c913e346335654d1","datavalue":{"value":{"entity-type":"item","numeric-id":4086967,"id":"Q4086967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1925790$7FB62AC0-A89A-42C7-9D4F-6317A3DD7F87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f5a77d9c8c972e7532e583a573d6e0d270f564f","datavalue":{"value":{"entity-type":"item","numeric-id":623465,"id":"Q623465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1925790$5766E5D7-F645-47A4-A7B9-C11AA5578AFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8bb7f52c81a94868ffd469efcf311221e89c53fc","datavalue":{"value":{"entity-type":"item","numeric-id":628649,"id":"Q628649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1925790$0855D2A7-02FA-463A-A90B-C7CE0B46972E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8628cfc19c8a5978fbad9b93278576c46fc56b0","datavalue":{"value":{"entity-type":"item","numeric-id":5813489,"id":"Q5813489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1925790$90BD3366-42B6-488C-9373-7E8BC4DB7E7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5fdc1ce394067058722b61c1d38be7745bd0312","datavalue":{"value":{"entity-type":"item","numeric-id":993280,"id":"Q993280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1925790$0B35B0CF-7E4B-478E-980D-7F3BBCC4B43E","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":"Q1925790$BD4E0293-1565-4568-9CF2-3579AE7FC414","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8726937e359569d5381d0d5f644a9495642d0feb","datavalue":{"value":{"entity-type":"item","numeric-id":1399915,"id":"Q1399915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1925790$9FA85AD1-C5B8-453E-AF3C-016A01E46470","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"854538bd89673f139e9d891c995f3de48d8205cf","datavalue":{"value":"10.1007/S10107-012-0605-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1925790$BB18C98F-0120-4F3C-8F2B-71C1C3F27049","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6782f0bd49a18e9b1fcf9d83bb6796c630301c00","datavalue":{"value":{"entity-type":"item","numeric-id":5384023,"id":"Q5384023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"575cb79573c8aef0e9e7fba39f6819ef94f6ed7f","datavalue":{"value":{"amount":"+0.7863389849662781","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":"Q1925790$55590B58-BFD5-47D2-941E-A2C2468217EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65724935885050338ec7a9593e53220df81cf60f","datavalue":{"value":{"entity-type":"item","numeric-id":2806816,"id":"Q2806816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1724890861a868ebf551d4bc39c694ef0d857b79","datavalue":{"value":{"amount":"+0.7760159373283386","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":"Q1925790$00414889-4A38-4B93-AF51-80B418E74C89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27aafc8280c00fbfbb3a48e365d6a9a031692693","datavalue":{"value":{"entity-type":"item","numeric-id":5206942,"id":"Q5206942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13cfc798ddddb8b76d5af32c0584cd7aeefbaa3f","datavalue":{"value":{"amount":"+0.7700247764587402","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":"Q1925790$0ED7E42D-CB93-4D1B-8E00-70ADB0A5773E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15508ceae315d1f184838282c98fe15268915b72","datavalue":{"value":{"entity-type":"item","numeric-id":3621050,"id":"Q3621050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11f5fe44ac29c33cbf61fc03478ffe76bc3e59d3","datavalue":{"value":{"amount":"+0.7689226269721985","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":"Q1925790$07DFFE1F-ED1C-47CE-95D5-78DF70E3124B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2fb89f7ffd3ed518bd745665dac364efd3259be0","datavalue":{"value":{"entity-type":"item","numeric-id":496616,"id":"Q496616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"502d31a3ac33e57f270e519845f6181b39fd734b","datavalue":{"value":{"amount":"+0.7564540505409241","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":"Q1925790$C3471EBB-E8BB-4C17-A8C9-20E34E5AC9ED","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1925790","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1925790"}}}}}