9 papers · ranked by Valyu relevance
Daniel Gibor
In this paper, we present a randomized polynomial-time simplex algorithm with higher probability and tighter bounds for linear programming by applying improved quasi-convex properties, a logarithmic rounding on a given polytope and its logarithmic perturbation. We base our work on the first randomized polynomial-time…
Yann Disser, Georg Loho, Matthew Maat, Nils Mosis
The existence of a polynomial pivot rule for the simplex method for linear programming, policy iteration for Markov decision processes, and strategy improvement for parity games each are prominent open problems in their respective fields. While numerous natural candidates for efficient rules have been eliminated, all…
Chengtao Du, Jinzhong Zhang, Jie Fang, Heming Jia
The black-winged kite algorithm (BKA) integrates the Cauchy mutation strategy and the leader selection strategy to simulate high-altitude circling exploration, fixed-point diving attack, and group cooperative migration of the black-winged kites to approximate the global optimal solution. The BKA exhibits deficiencies…
Kirill Kukharenko, Laura Sanità
The simplex algorithm is one of the most popular algorithms to solve linear programs (LPs). Starting at an extreme point solution of an LP, it performs a sequence of basis exchanges (called pivots) that allows one to move to a better extreme point along an improving edge-direction of the underlying polyhedron. A key…
Anna Pietrenko-Dabrowska, Slawomir Koziel
Formal optimization is nowadays ubiquitous in microwave design. It is frequently conducted using electromagnetic (EM) simulations, which guarantee dependability. Yet, it is computationally expensive. Local tuning may involve hundreds of system analyses, whereas global EM-driven optimization typically generates…
Uri Zwick
We give a concise description and an improved analysis of the Random-Action-Removal algorithm for solving 2-player, 0-sum, turn-based, possibly infinite duration, stochastic or non-stochastic games played on graphs, or on finite sets of states. More generally, the algorithm can be used to find the sink of an Acyclic…
Sanjay Mishra
This paper develops a complete foundational treatment of simplicial complexes from Euclidean spaces through geometric realizations, emphasizing concrete computations, examples, and practical verification methods. Beginning with finite point sets in finite and infinite-dimensional Euclidean spaces, geometric…
Zhaoyang Wang, Xianghui Fu, Bo Deng, Yang Chen + 1 more
In algebraic topology, a k-dimensional simplex is defined as a convex polytope consisting of k + 1 vertices. If spatial dimensionality is not considered, it corresponds to the complete graph with k + 1 vertices in graph theory. The alternating sum of the number of simplices across dimensions yields a topological…
Joakim da Silva, Daniel Hernández Escobar, Tor Kjellsson Lindblom, Håkan Nordström + 1 more
As opposed to the ADMM method, the reference simplex method solves each problem corresponding to a weight vector sequentially, and the simplex times are thus expected to be linear in the number of weight vectors, as can be verified in Figure [mp70454-fig-0005]. This allows us to estimate the simplex run times for a…