{"entities":{"Q1396212":{"pageid":1406952,"ns":120,"title":"Item:Q1396212","lastrevid":68615442,"modified":"2026-04-13T00:56:36Z","type":"item","id":"Q1396212","labels":{"en":{"language":"en","value":"Combinatorial interior point methods for generalized network flow problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1942738"}},"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":"Q1396212$3C8A3121-79D5-4DDD-8F13-E4E96CBC0482","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a5c2a59e993d9783a52c016549b7ebb0dd6a8d6c","datavalue":{"value":{"text":"Combinatorial interior point methods for generalized network flow problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1396212$A3131FCE-43D9-4E97-A080-BEE31E09B6A4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"16ddaa06956e2f85cb8ca8446ce80cea4baca22f","datavalue":{"value":"1053.90135","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1396212$49B2E6D9-874F-4EA0-8606-2A317BCEB4EF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"389c681e6859e96625810538dab4d8964ec9e5f5","datavalue":{"value":{"entity-type":"item","numeric-id":233995,"id":"Q233995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1396212$2BEA2B22-AFD3-4A9E-92D0-956D9CB09ACA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"32f9987a7941a9b881daf94c50d323c37b17f9c3","datavalue":{"value":{"entity-type":"item","numeric-id":477469,"id":"Q477469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1396212$1F2BF4DF-35F5-48C5-BDFC-9F3DCF961233","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":"Q1396212$191056FF-45C0-413E-9FB2-066D1E7D7773","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c6427ff9a626f686c7f1def93b416dba0b5871b3","datavalue":{"value":{"time":"+2002-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":"Q1396212$F5888646-C596-476B-925D-EFE8983E1F5B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7fc7ed7734a8435f336595c13dff0b4d0cf5947e","datavalue":{"value":"The paper is concerned with generalized minimum cost flow problems. Compared with a pure network flow problem, in generalized network flow problems each arc has a gain/loss factor associated with it. Since the pure and generalized problems are linear programs, any linear programming algorithms, in particular, interior point methods can be used to solve these problems. However if interior point methods are applied directly, they are not combinatorial. The authors present combinatorial interior point methods for the generalized minimum cost flow problems and the generalized circulation problems. The algorithms run in \\(O(m^2 n^2 (\\log m+\\log^2 n)L)\\) time, where \\(m\\) and \\(n\\) are the number of arcs and nodes in the graph, and \\(L\\) is the length of the input data.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1396212$E7D0C62D-695A-4FAE-8E8E-9A8D97BBD0B4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4ac3edbc9a781214f87fc7c9c04c2c17e13b7ca7","datavalue":{"value":"90C51","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1396212$DB219032-D008-463B-8280-E3F022C78D63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1396212$C9D6A876-359D-4C77-AF91-076E1953B3F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1396212$DB8FCF49-EF43-4102-BF06-07E316FFBBDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1396212$066DD8F5-6394-451C-AA7B-C18E6FEAE4BE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e8419d007f517d8f010422cf8dcda69e86b65ed2","datavalue":{"value":"1942738","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1396212$5D8E4BCD-E45E-4EFD-B4FB-0027F51C8367","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"afd7d7d43ad189257d922b054fa627eba556607c","datavalue":{"value":"minimum cost flow problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1396212$F5CF1857-E24B-4C97-94E2-DB86E1999932","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"143c948fa08252dd305c52de3072d5de5b766a94","datavalue":{"value":"circulation problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1396212$113CC12E-7E4B-4D76-BEDE-8B046DCB5C89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5463f8cb67c335ff66aa835d1eefbd219fa938e5","datavalue":{"value":"interior point methods","type":"string"},"datatype":"string"},"type":"statement","id":"Q1396212$42A3AA86-F89D-473D-B6F8-756D69B69DA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b51d2ccfef1b445850ba4a303a58769a1009b280","datavalue":{"value":"combinatorial methods","type":"string"},"datatype":"string"},"type":"statement","id":"Q1396212$3CAFDC6A-458E-462D-A45D-94D82388B159","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1247900d8ca90463aba7653b58abc2ec2e0008eb","datavalue":{"value":"polynomial methods","type":"string"},"datatype":"string"},"type":"statement","id":"Q1396212$2DDAD213-5E7A-4FD1-9420-114557712934","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cf4c707a2d5b2edbf0d3da0287d7b23f0d6cc140","datavalue":{"value":{"entity-type":"item","numeric-id":591175,"id":"Q591175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1396212$3D2A0A1F-E425-451E-831D-C765169B4E2A","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":"Q1396212$1C4852A9-F1D4-4D3E-B087-5D3C91129716","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"873760bd8bf64b3dd8e4f47e0d3a5110f09a80d0","datavalue":{"value":"https://doi.org/10.1007/s10107-002-0333-y","type":"string"},"datatype":"url"},"type":"statement","id":"Q1396212$B5F5E353-B641-4364-8AEF-B4B95DA9AFDA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ca381017c3b9c6562c8ab9cd965549f86ab004c6","datavalue":{"value":"W2050789657","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1396212$44CEF49A-9C10-4992-A656-A488BADE5267","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"382577de21a22a16428a1db40a63c6a4a679f83b","datavalue":{"value":"10.1007/S10107-002-0333-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1396212$F30560FD-1F2F-42FA-8BD1-393B5CF3D120","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"453196422b2c6a40810b30c7add1e642bf157428","datavalue":{"value":{"entity-type":"item","numeric-id":1196185,"id":"Q1196185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b80fc100ff4bfc522a22aa9890806eee5a7ed4e","datavalue":{"value":{"amount":"+0.8911996483802795","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":"Q1396212$A20E8E51-CF5F-45DD-B967-37F87D187E2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5858b317e30a34d97758096f2cb11c97be3a32e6","datavalue":{"value":{"entity-type":"item","numeric-id":2819530,"id":"Q2819530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f9bdb6bff74319c4009af847371b64661996258","datavalue":{"value":{"amount":"+0.8901351094245911","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":"Q1396212$BA4F7164-2056-4A77-9477-7CB6E5798696","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"574b5a67714e6964c28b1784095645fc201fdf7f","datavalue":{"value":{"entity-type":"item","numeric-id":3202103,"id":"Q3202103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26a0dde39e96174dc2563e30d2d80e873f333c47","datavalue":{"value":{"amount":"+0.8436393141746521","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":"Q1396212$8EDA54A4-E11A-43F4-8639-DDCB33C005C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a3d1032ecf995219e689b1671388bb3761330f6","datavalue":{"value":{"entity-type":"item","numeric-id":2757524,"id":"Q2757524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b20d4cbe4c8454a4244a6b8ec0eaa240f9aca4f","datavalue":{"value":{"amount":"+0.8244333863258362","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":"Q1396212$F4A5F878-9A96-4D37-BA6F-1DEEAAB54037","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0d095d1fc00c5b7cf82943504a0d629373b08ac","datavalue":{"value":{"entity-type":"item","numeric-id":5704090,"id":"Q5704090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b488c54f141971769e23d748200128051635d6a9","datavalue":{"value":{"amount":"+0.822192907333374","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":"Q1396212$F3A0704B-7D40-4294-996F-AE27F653E839","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Combinatorial interior point methods for generalized network flow problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Combinatorial_interior_point_methods_for_generalized_network_flow_problems"}}}}}