×

On the closest point to the origin in transportation polytopes. (English) Zbl 1351.90120

Summary: We consider the problem of finding the point in the transportation polytope which is closest to the origin. Recursive formulas to solve it are provided, explaining how they arise from geometric considerations, via projections, and we derive solution algorithms with linear computational complexity in the number of variables.

MSC:

90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90C20 Quadratic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bachem, A.; Korte, B., Minimum norm problems over transportation polytopes, Linear Algebra Appl., 31, 103-118 (1980) · Zbl 0435.90036
[2] Balinski, M. L.; Rispoli, F. J., Signature classes of transportation polytopes, Math. Program., 60, 127-144 (1993) · Zbl 0783.90078
[3] Barbinok, A., Asymptotic estimates for the number of contingency tables, integer flows, and volumes of transportation polytopes, Int. Math. Res. Not., 2009, 2, 348-385 (2009) · Zbl 1163.15015
[4] Brightwell, G.; Van den Heuvel, J.; Stougie, L., A linear bound on the diameter of the transportation polytope, Combinatorica, 26, 2, 133-139 (2006) · Zbl 1150.90008
[5] De Loera, J. A.; Kim, E. D., Combinatorics and geometry on transportation polytopes: An update, Contemp. Math., 625, 37-76 (2014) · Zbl 1360.90169
[6] De Loera, J. A.; Kim, E. D.; Onn, S.; Santos, F., Graphs of transportation polytopes, J. Combin. Theory Ser. A, 116, 8, 1306-1325 (2009) · Zbl 1229.05190
[8] He, B.; Stoer, J., Solution of projection problems over polytopes, Numer. Math., 61, 73-90 (1992) · Zbl 0758.65046
[9] Kozlov, M. K.; Tarasov, S. P.; Khachiyan, L. G., The polinomial solvability of convex quadratic programming, USSR Comput. Math. Matht. Phys., 20, 5, 223-228 (1980) · Zbl 0486.90068
[12] Monteiro, R. D.C.; Adler, I., Interior path following primal-dual algorithms. Part II, convex quadratic programming, Math. Program., 44, 43-46 (1989) · Zbl 0676.90039
[14] Onn, S.; Vallejo, E., Permutohedra and minimal matrices, Linear Algebra Appl., 412, 471-489 (2006) · Zbl 1077.05019
[15] Pak, I., On the number of faces of certain transportation polytopes, European J. Combin., 21, 689-694 (2000) · Zbl 0963.90042
[16] Romero, D., Easy transportation-like problems on \(L\)-dimensional arrays, J. Optim. Theory Appl., 66, 1, 137-147 (1990) · Zbl 0679.90037
[17] Schneider, M. H.; Zenios, S. A., A comparative study of algorithms for matrix balancing, Oper. Res., 38, 3, 439-455 (1990) · Zbl 0703.90094
[18] Verbeek, A.; Kroonenberg, P., A survey of algorithms for exact distributions of test studies in \(r \times c\) contingency tables with fixed margins, Comput. Stat. Data Anal., 3, 159-185 (1985) · Zbl 0586.62083
[19] Wolfe, P., Algorithm for a least-distance programming problem, Math. Programming Study, I, 190-205 (1974) · Zbl 0359.90062
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.