Dirk Banholzer,Jörg Fliege,Ralf Werner
Dirk Banholzer
We present a novel response surface method for global optimisation of an expensive and noisy (black-box) objective function, where error bounds on the deviation of the observed noisy function values from their true counterparts are availabl...
Martin Nägele,Christian Nöbel,Richard Santiago et al.
Martin Nägele et al.
There has been significant work recently on integer programs (IPs) min { c ⊤ x : A x ≤ b , x ∈ Z n } with a constraint marix A with bounded subdeterminants. This is motivated by a well-known conjecture claiming that, for...
Constant-competitiveness for random assignment Matroid secretary without knowing the Matroid [0.03%]
不知道Matroid的随机分配恒定竞争力及.matroid秘书问题
Richard Santiago,Ivan Sergeev,Rico Zenklusen
Richard Santiago
The Matroid Secretary Conjecture is a notorious open problem in online optimization. It claims the existence of an O(1)-competitive algorithm for the Matroid Secretary Problem (MSP). Here, the elements of a weighted matroid appear one-by-on...
A linear time algorithm for linearizing quadratic and higher-order shortest path problems [0.03%]
线性时间算法用于线性化二次及更高阶的最短路径问题
Eranda Çela,Bettina Klinz,Stefan Lendl et al.
Eranda Çela et al.
An instance of the NP-hard Quadratic Shortest Path Problem (QSPP) is called linearizable iff it is equivalent to an instance of the classic Shortest Path Problem (SPP) on the same input digraph. The linearization problem for the QSPP (LinQS...
Daniel Dadush,Friedrich Eisenbrand,Thomas Rothvoss
Daniel Dadush
Approximate integer programming is the following: For a given convex body K ⊆ R n , either determine whether K ∩ Z n is empty, or find an integer point in the convex body 2 · ( K - c ) + c which is K, scaled by 2 from ...
Edin Husić,Zhuan Khye Koh,Georg Loho et al.
Edin Husić et al.
A set function can be extended to the unit cube in various ways; the correlation gap measures the ratio between two natural extensions. This quantity has been identified as the performance guarantee in a range of approximation algorithms an...
Franziska Eberle,Anupam Gupta,Nicole Megow et al.
Franziska Eberle et al.
The configuration balancing problem with stochastic requests generalizes well-studied resource allocation problems such as load balancing and virtual circuit routing. There are given m resources and n requests; each request has multiple pos...
Sander Borst,Daniel Dadush,Sophie Huiberts et al.
Sander Borst et al.
Explorable heap selection is the problem of selecting the nth smallest value in a binary heap. The key values can only be accessed by traversing through the underlying infinite binary tree, and the complexity of the algorithm is measured by...
Manu Upadhyaya,Sebastian Banert,Adrien B Taylor et al.
Manu Upadhyaya et al.
We present a methodology for establishing the existence of quadratic Lyapunov inequalities for a wide range of first-order methods used to solve convex optimization problems. In particular, we consider (i) classes of optimization problems o...
Matúš Benko,Patrick Mehlitz
Matúš Benko
As a starting point of our research, we show that, for a fixed order γ ≥ 1 , each local minimizer of a rather general nonsmooth optimization problem in Euclidean spaces is either M-stationary in the classical sense (correspondin...