Kirill Kukharenko,Laura Sanità
Kirill Kukharenko
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 extrem...
Jannis Blauth,Nathan Klein,Martin Nägele
Jannis Blauth
Prize-Collecting TSP is a variant of the traveling salesperson problem where one may drop vertices from the tour at the cost of vertex-dependent penalties. The quality of a solution is then measured by adding the length of the tour and the ...
A [Formula: see text] -approximation for the maximum leaf spanning arborescence problem in DAGs [0.03%]
有向图中最大叶生成树问题的近似算法研究
Meike Neuwohner
Meike Neuwohner
The Maximum Leaf Spanning Arborescence problem (MLSA) in directed acyclic graphs (dags) is defined as follows: Given a directed acyclic graph G and a vertex r ∈ V ( G ) from which every other vertex is reachable, find a spanning arbo...
Chien-Chung Huang,Nidia Obscura Acosta,Sorrachai Yingchareonthawornchai
Chien-Chung Huang
In the connectivity interdiction problem, we are asked to find a global graph cut and remove a subset of edges under a budget constraint, so that the total weight of the remaining edges in this cut is minimized. This problem easily includes...
A first order method for linear programming parameterized by circuit imbalance [0.03%]
由电路不平衡参数化的线性规划一阶方法
Richard Cole,Christoph Hertrich,Yixin Tao et al.
Richard Cole et al.
Various first order approaches have been proposed in the literature to solve Linear Programming (LP) problems, recently leading to practically efficient solvers for large-scale LPs. From a theoretical perspective, linear convergence rates h...
Christoph Hunkenschröder,Kim-Manuel Klein,Martin Koutecký et al.
Christoph Hunkenschröder et al.
We study fundamental block-structured integer programs called tree-fold and multi-stage IPs. Tree-fold IPs have a constraint matrix with independent blocks linked together by few constraints in a recursive pattern. Transposing this constrai...
Michael Muehlebach,Michael I Jordan
Michael Muehlebach
We exploit analogies between first-order algorithms for constrained optimization and non-smooth dynamical systems to design a new class of accelerated first-order algorithms for constrained optimization. Unlike Frank-Wolfe or projected grad...
Fast convergence of trust-regions for non-isolated minima via analysis of CG on indefinite matrices [0.03%]
基于不定矩阵的共轭梯度分析的信赖域算法求非孤立极小点的快速收敛性研究
Quentin Rebjock,Nicolas Boumal
Quentin Rebjock
Trust-region methods (TR) can converge quadratically to minima where the Hessian is positive definite. However, if the minima are not isolated, then the Hessian there cannot be positive definite. The weaker Polyak-Łojasiewicz (PŁ) conditi...
Ahmad Abdi,Gérard Cornuéjols,Bertrand Guenin et al.
Ahmad Abdi et al.
A rational number is dyadic if it has a finite binary representation p / 2 k , where p is an integer and k is a nonnegative integer. Dyadic rationals are important for numerical computations because they have an exact representation in fl...
Benny Sudakov,István Tomon
Benny Sudakov
Given an m × n binary matrix M with | M | = p · m n (where |M| denotes the number of 1 entries), define the discrepancy of M as disc ( M ) = max X ⊂ [ m ] , Y ⊂ [ n ] | | M [ X × Y ] | - p | X | · | Y ...