11 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…
Bach, Eleon, Black, Alexander E. + 4 more
Narrowing the gap between theory and practice is a longstanding goal of the algorithm analysis community. To further progress our understanding of how algorithms work in practice, we propose a new algorithm analysis framework that we call by the book analysis. In contrast to earlier frameworks, by the book analysis not…
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…
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…
Federico Pavesi, Antonio Candelieri, Noémie Jaquier
Bayesian optimization is a data-efficient technique that has been shown to be extremely powerful to optimize expensive, black-box, and possibly noisy objective functions. Many applications involve optimizing probabilities and mixtures which naturally belong to the probability simplex, a constrained non-Euclidean domain…
Kiyoji Huang Fujiwara, Yujia Shi, Thomas G. Wong
The simplex of complete graphs, also known as the first-order truncated simplex lattice, is a network of $M+1$ identical complete graphs, each with $M$ vertices, such that each clique contains an edge or bridge to every other clique. It contains $N = M(M+1)$ vertices, and previous asymptotic results using a…
Sanyou Mei, Chunlin Sun, Yinyu Ye
We study Turn-Based Deterministic Forward Games (TBDFGs), the subclass of turn-based deterministic zero-sum games in which no directed cycle contains actions controlled by both players. This forward condition is strictly weaker than acyclicity: recurrent behavior may be arbitrarily rich within one player's states…
Daniel Stilck França, Ngoc Hoang Anh Mai
We study quantum algorithms for approximating Lasserre's hierarchy values for polynomial optimization. Let f, g1, . . . , g m be real polynomials in n variables and f ⋆ the infimum of f over the semialgebraic set S(g) = {x : gi(x) ≥ 0}. Let λ k be the value of the order-k Lasserre relaxation. Assume either (i) f ⋆ = λ…
Zamina Guliyeva, Yagub Aliyev
The cevians passing through a point in a simplex create a cevian simplex, which is divided by these cevians into smaller simplices. We consider the problem about the maximum of the ratio of the sum of the volumes of some of these smaller simplices by the volume of the reference simplex. The special case of tetrahedron…
Levin Nemesch, Stefan Ruzika, Clemens Thielen, Alina Wittmann
Linear-multi-parametric optimization problems are a widely studied class of optimization problems. The objective function in such a problem is affine linear dependent on a parameter vector, and the goal is to compute a set of solutions that contains an optimal solution for every fixed parameter vector. However, this is…