Loading article...
Loading article...
Stream/Area:
-
Subject:
-
Paper ID:
IJSREM65725
Volume:
10 |
6 |
Jun 2026
Pages:
1-8
Publication Frequency:
Monthly (12 issues per year)
License:International Journal of Scientific Research in Engineering and Management follows the Creative Commons Attribution 4.0 (CC BY 4.0) License, allowing free use and distribution with proper attribution.
Department of Mathematics
Veer Kunwar Singh University, Ara
Department of Mathematics
Veer Kunwar Singh University, Ara
Our study area belongs to Linear Programming hence we have decided to study to find the approximately optimal rescaling in this paper. The paper first describes the standard primal and dual form of a constraint matrix. This paper also studies shortest path and interior-points method. By reviewing the earlier studies and research done in the field of linear programming, optimization, constraint matrix, optimal rescaling we are going to present our findings in this paper. Related theorems, propositions and corollaries seem to be part of our study and hence they are described in this paper. A result has been provided in this paper for a scaling-invariant Interior-Point Method that works out LP in time that is dimensionally a polynomial, answering an unlocked question by Monteiro-Tsuchiya in the assenting. This locks a long line of research by Vavasis-Ye and Monteiro-Tsuchiya;
KEYWORDS
𝐴 Moneteiro and Tsuchiya, noting that under the rescalings of the columns of A and c, noted that the central path is invariant and presented a question before the researchers whether there exists and LP algorithm depending as an alternative on the measure 𝜒̅∗ , described as the minimum 𝜒̅𝑨𝑫 value feasible by a column rescaling AD of A. Near-optimal rescaling of the constraint matrix is provided in this paper to answer the question.
1. I. Dikin, “Iterative solution of problems of linear and quadratic programming”, Doklady Akademii Nauk, 174:4, 1967, pp. 747-748, 2. G. Stewart, “On scaled projections and pseudoinverses”, Linear Algebra and its Applications, 112, 1989, pp. 189-193 3. M. J. Todd, “A Dantzig-Wolfe-Like Variant of Karmarker‟s Interior-Point Linear Programming Algorithm”, Operations Research, 38:6, 1990, pp 106-1018, url: https://doi-org/10.1287/opre-38.6.1006 4. S. A. Vavasis and Y. Ye., “A primal-dual interior point method whose running time depends only on the constraint matrix, Mathematical Programming, 74:1, 1996, pp. 79-120. 5. L. Tuncel, “Approximating the complexity measure of Vavasis-Ye algorithm in NP-hard”, Mathematical Programming, 86:1, 1999, pp. 219-223 6. R. D. C. Monteiro and T. Tsuchiya, “A modified layered-step interior-point algorithm for linear programming”, SIAM Journal on Optimization, 13:4, 2003, pp. 1054-1079. 7. R. D. C. Monteiro and T. Tsuchiya, “A New Iteration-Complexity Bound for the MTY Predictor-Corrector Algorithm”, SIAM Journal on Optimization, 15:2, 2005, pp. 319-347 8. R. D. C. Monteiro and T. Tsuchiya, “A strong bound on the integral of the central path curvature and its relationships with the iteration-complexity of primal-dual path- following LP algorithms”, Mathematical Programming, 115:1, 2008, pp. 105-149. 9. S. Bordwardt, T. Stephen and T. Yusun, “On the circuit diameter conjecture”, Discrete & Computation Geometry, 60:3, 2018, pp. 558-587 10. J. van den Brand, “A Deterministic Linear Program Solver in Current Matrix Multiplication Time”, In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020 11. J. van den Brand, Y. P. Liu, Y. –T. Saranurak, A. Sidford, Z. Song and D. Wang., “Minimum Cost Flows, MDPs, and L1-Regression in Nearly Linear Time for Dense Instances”, In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2021, pp. 859 - 869
Publication Date
6/30/2026
Peer Review Type
Double-Blind Peer Review
Review Rounds: 2
Documents
Article Views
0
Total views since publication
PDF Downloads
31
Total downloads since publication
Geographic Reach
5
Digital Preservation: This article is permanently archived on Zenodo and complies with all data preservation standards across major indexing platforms.
Plagiarism Screening
This manuscript has been checked for plagiarism using TurnitinPlagiarismChecker software.
Conflict of Interest
The authors declare no conflict of interest related to this research work.
Funding Information
No funding information available for this research.
Related research in the same subject area
Loading similar articles...