| viXra.org > Combinatorics and Graph Theory > 2102 |
 |
 |
| viXra.org > Combinatorics and Graph Theory > 2102 |
|
|
[3] viXra:2102.0142 [pdf] replaced on 2025-07-02 09:07:36
Authors: Keshava Prasad Halemane
Comments: 25 Pages.
The Symmetric Primal-Dual Symplex Pivot Decision Strategy (spdspds) is a novel iterative algorithm to solve linear programming problems. A symplex pivoting operation is considered simply as an exchange between a basic (dependent) variable and a non-basic (independent) variable, in the Goldman-Tucker Compact-Symmetric-Tableau (CST) which is a unique symmetric representation common to both the primal as well as the dual of a linear programming problem in its standard canonical form. From this viewpoint, the classical simplex pivoting operation of Dantzig may be considered as a restricted special case. The infeasibility index associated with a symplex tableau is defined as the sum of the number of primal variables and the number of dual variables that are infeasible. A measure of goodness as a global effectiveness measure of a pivot selection is defined/determined as/by the decrease in the infeasibility index associated with such a pivot selection. The selection of the symplex pivot element is made by seeking the best possible anticipated decrease in the infeasibility index from among a wide range of candidate choices with non-zero values - limited only by considerations of potential numerical instability. After passing through a non-repeating sequence of CST tableaus, the algorithm terminates when further reduction in the infeasibility index is not possible; then the tableau is checked for the terminal tableau type to facilitate the problem classification - a termination with an infeasibility index of zero indicates optimum solution. Even in the absence of an optimum solution, the versatility of the spdspds algorithm allows one to explore/determine the most suitable alternative solutions, including possibly a comprehensive parametric analysis, etc. The worst-case computational complexity of the spdspds algorithm is shown to be O(L^1.5) where L refers to the problem-size expressed in terms of the size(length) of the input data.
Category: Combinatorics and Graph Theory
[2] viXra:2102.0078 [pdf] replaced on 2021-03-11 07:12:19
Authors: Theophilus Agama
Comments: 6 Pages.
In this paper we introduce the notion of universe, induced communities and cells with their corresponding spots. Using this language we formulate and prove the union close set conjecture by showing that for any finite universe $\mathbb{U}$ and any induced community $\mathcal{M}_{\mathbb{U}}$ there exist some spot $a\in \mathbb{U}$ such that the density
\begin{align}
\mathcal{D}_{\mathcal{M}_{\mathbb{U}}}(a)\geq \frac{1}{2}.\nonumber
\end{align}
Category: Combinatorics and Graph Theory
[1] viXra:2102.0006 [pdf] submitted on 2021-02-01 09:23:26
Authors: Majid Zohrehbandian
Comments: 7 Pages.
Maximum cut problem is a famous combinatorial problem, which its complexity has been heavily studied over the years. Among them is the efficient algorithm of Goemans and Williamson with an approximation factor roughly 1.13823≅1/0.878 (It is most often expressed as 0.878). Their algorithm combines semidefinite programming and a rounding procedure to produce an approximate solution to the maximum cut problem. In this paper, after introducing a new semidefinite programming formulation we present an improved randomized approximation with an approximation factor roughly 1.01241≅1/0.98775 .
Category: Combinatorics and Graph Theory
| Third-Party Links: |
|