Frank Vega

Mr. Frank Vega

Member, Information Physics Institute, Gosport, Hampshire, UK
orcid

Research Focus & Metrics

Academic Career Length

13Years (2014-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
3 May 2022 in The Ramanujan Journal
Verified
Journal Article
Closed access
PDF file
Frank VegaFrank Vega
Frank Vega

1 January 2026
Verified
Journal Article
Closed access
Frank VegaFrank Vega
Frank Vega
We present \textbf{Hvala}, a linear-time ensemble approximation algorithm for Minimum Vertex Cover that combines a maximal-matching 2-approximation, a bucket-queue maximum-degree greedy, and the degree-$1$ weighted-reduction Hallelujah heuristic of a companion work, applies redundant-vertex pruning to each, and returns the smallest of the four resulting covers. We prove unconditionally that Hvala runs in $\mathcal{O}(n+m)$ time and space and attains worst-case approximation ratio $\rho\le 2$ on every finite simple graph; conditional on the strict pointwise inequality of the Hallelujah heuristic, the bound improves to $|S|<2\cdot\mathrm{OPT}(G)$ on every graph. Empirically we evaluate Hvala on three independent studies totalling $252$ instances --- the $109$-instance NPBench collection, $130$ real-world graphs from the Network Data Repository (up to $\approx 2.5$M vertices and $\approx 15$M edges), and $13$ hand-crafted adversarial graphs (crown graphs, odd cycles, high-girth cubic and bipartite-expander graphs) --- separating certified ratios from ratios-to-best-known. On the $173$ instances with a published reference value, the mean approximation ratio is $1.015$ and the maximum is $1.192$ (a single Sanchis instance); every reported ratio falls below $1.414$. The natural open question this benchmark raises --- not a theorem proved here --- is whether Hvala admits a uniform $\sqrt{2}-\epsilon$ bound on broad restricted graph classes (bounded degree, treewidth, clique number, expander-like, or power-law families), since an all-graphs sub-$\sqrt{2}$ bound would, by Khot--Minzer--Safra, contradict $\mathrm{P}\neq\mathrm{NP}$. The algorithm is publicly available via PyPI as the \texttt{hvala} package.

7 June 2024 in IPI Letters
Verified
Journal Article
Open access
PDF file
Frank VegaFrank Vega
Frank Vega
P versus NP is considered as one of the most fundamental open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? It was essentially mentioned in 1955 from a letter written by John Nash to the United States National Security Agency. However, a precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. Another major complexity class is NP-complete. It is well-known that P is equal to NP under the assumption of the existence of a polynomial time algorithm for some NP-complete. We show that the Monotone Weighted Xor 2-satisfiability problem (MWX2SAT) is NP-complete and P at the same time. Certainly, we make a polynomial time reduction from every directed graph and positive integer k in the K-CLOSURE problem to an instance of MWX2SAT. In this way, we show that MWX2SAT is also an NP-complete problem. Moreover, we create and implement a polynomial time algorithm which decides the instances of MWX2SAT. Consequently, we prove that P = NP.

10 March 2026 in Preprints.org
Verified
Preprint
Open access
PDF file
Frank VegaFrank Vega
Frank Vega
We present a polynomial-time algorithm for Minimum Vertex Cover achieving an approximation ratio strictly less than 2 for any finite undirected graph with at least one edge, thereby disproving the Unique Games Conjecture. The algorithm reduces the problem to a minimum weighted vertex cover on a degree-1 auxiliary graph using weights \( 1/d_v \), solves it optimally via Cauchy-Schwarz-balanced selection, and projects the solution back to a valid cover. Correctness and the strict sub-2 ratio are rigorously proved. Runtime is \( O(|V|+|E|) \), confirming practical scalability and opening avenues for revisiting UGC-dependent hardness results across combinatorial optimization.

23 July 2018 in EMC Review - Časopis za Ekonomiju - APEIRON
Verified
Journal Article
Open access
PDF file
KDKatarina Držajić
Katarina Držajić
Frank VegaFrank Vega
Frank Vega
The theoretical framework by Diamond, Mortensen and Pissarides (Nobel Award in Economic Sciences, 2010) shows us how generous wages can determine the success in filling job vacancies. The empirical evidence is convincing: larger and more profitable enterprises pay higher wages. Nowadays, large leader companies are investing not only in paying efficient wages to prevent shirking, but also in the improvement of working conditions and even taking a rigorous analytical approach to etiquette. It is a common fact that small and medium-sized enterprises (SMEs) cannot compete in the same way with these high standards. However, recent examples have shown that a suitable work environment, techniques for reducing the stress factors, strategies to create workplaces with a more ethnical diversity and profound benefits for women, as well as the efforts in making the workers feel more liable to their jobs are possible in SMEs and have real benefits for their growth and productivity. At the same time, these approaches could be beneficial for developing countries in a large scale since SMEs play a major role in most of these economies. In this paper, we will conduct a study from the most popular current standards that the best companies promote and suggest some alternatives for SMEs in order to improve these factors.

12 July 2023
Verified
Preprint
Open access
PDF file
Frank VegaFrank Vega
Frank Vega
The (2.4. Theorem) does not exist in the cited reference. In fact, Guy Robin proves a similar Proposition 1 instead on page 192, but only when A and B are "consecutive" colossally abundant numbers. Note that, he used the French word "successifs" in y...