Karmarkar's algorithm with improved steps (Q910334): Difference between revisions

The paper studies Karmarkar's canonical linear program: \(v=Min\{c^ tx:\) \(x\in \Omega \}\) where \(\Omega =\{x\in R^ n|\) \(Ax=0\), \(e^ tx=1\), \(x>0\}\) and \(\Omega^ 0=\{x\in \Omega |\) \(x>0\}\neq \emptyset\). It is assumed that \(c^ tx>0\) for all \(x\in \Omega^ 0\). The author defines a function \(\beta\) on \(\Omega^ 0\) such that \(\sup_{d\in \Omega^ 0}\beta (d)\leq 1\) if and only if \(v=0\). It is shown that for a given \(d\in \Omega^ 0\), there exists \(x_ d\in \Omega\) such that \(f(x_ d)\leq f(d)r_ d\) where the constant \(\gamma_ d\) increases monotonically and improves \textit{M. Padberg}'s constant [Oper. Res. Lett. 4, 253-257 (1986; Zbl 0617.90059)] if \(\beta (d)<1\). This compares also with \textit{N. Karmarkar}'s result [Combinatorica 4, No.4, 373-395 (1984; Zbl 0557.90065)] which states that for \(d\in \Omega^ 0\) there exists \(x_ d\in \Omega^ 0\) satisfying the inequality \(f(x_ d)\leq f(d)\gamma\) where \(0<\gamma <1\) depends on n.