First Lightning Session (11:45 - 12:15)
- Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Work and Polylogarithmic Depth
Speaker: Zhuan Khye (Cedric) Koh (CWI)
Abstract: We present a nearly-linear work parallel algorithm for approximating the Held-Karp bound for Metric TSP. Given a graph with m edges and ε > 0, it returns a (1 + ε)-approximation to the Held-Karp bound with high probability, in O(m polylog(m)/ε4) work and O(polylog(m)/ε4) depth. Although a nearly-linear time sequential algorithm was given by Chekuri and Quanrud (FOCS 17), it was not known how to simultaneously achieve nearly-linear work and polylogarithmic depth. The key idea is the notion of a `core-sequence', which we introduce in the multiplicative weights update framework for solving packing/covering linear programs.
- Computational aspect of lifted cover inequalities for knapsack with few different weights
Speaker: Cédric Roy (TU/e)
Abstract: Cutting planes are frequently used for solving large integer programs. A common strategy is to derive cutting planes from building blocks or substructure of the integer program. In this presentation, we focus on knapsack constraints that arise from single row relaxations. Among the most popular classes derived from knapsack constraints are lifted minimal cover inequalities. Yet the separation problem for these inequalities is NP-hard, and one usually separates them heuristically, therefore not fully exploiting their potential.
In practice however, it turns out that many knapsack constraints only have few different coefficients. This motivates the concept of sparse knapsacks where the number of different coefficients is a small constant, independent of the number of variables present. For such knapsacks, we observe that there are only polynomially many different classes of structurally equivalent minimal covers. This opens the door to specialized techniques for using lifted minimal cover inequalities.
In this presentation we will present new separation routines that separate equivalence classes of inequalities rather than individual inequalities. We conclude the presentation by a numerical investigation for popular benchmarking instances.
- Residual subspace Active Set method for large-scale QP problems
Speaker: Wim Vanroose (University of Antwerpen)
Abstract: The active set and interior-point methods are both used to solve quadratic programming (QP) problems but differ in their handling of constraints. The active set method iteratively updates a set of active constraints, solving simpler QP subproblems that change by one constraint at a time. This allows for efficient solves by maintaining a factorization of the system, making each iteration computationally cheap. In contrast, the interior-point method moves through the interior of the feasible region, using barrier functions to handle all constraints simultaneously, though it requires a new factorization at each iteration. Active set methods perform well for smaller problems with few constraints, while interior-point methods scale better for large problems.
We present a new method for large-scale QP problems that combines the advantages of the active set method with the scalability of interior-point approaches. It works by projecting the problem onto a subspace, generating a series of increasingly larger subproblems. Each subproblem is solved using the active set method, warm-started with the working set and solution from the previous step. Asymptotically, the method coincides with Krylov subspace techniques like conjugate gradients (CG) or LSQR. This novel approach demonstrates similarities with Krylov methods, offering a powerful tool for solving large-scale optimization problems efficiently.
- Column Generation in Aviation
Speaker: Sebastian van Thienen (University of Antwerpen)
Abstract: Crew scheduling in aviation is a complex problem, resulting in linear programs with millions of decision variables. The movement of pilots can be modelled on a time-space graph, naturally giving rise to a Dantzig-Wolfe decomposition. Column generation can therefore be applied to calculate the optimal solution to the relaxed problem. On large instances, reaching optimality is often unrealistic due to degenerate steps, resulting in the tailing-off effect. Regularization can overcome this issue.
- Improved Guarantees for Fully Dynamic k-Center Clustering with Outliers
Speaker: Leyla Biabani
Abstract: The metric k-center clustering problem with z outliers involves clustering a given point set P in a metric space (M,d) using at most k balls, minimizing the maximum ball radius while excluding up to z points from the clustering. This problem holds fundamental significance in various domains, such as machine learning, data mining, and database systems. We address the fully dynamic version of the problem, where the point set undergoes continuous updates (insertions and deletions) over time. The objective is to maintain an approximate solution with efficient update times. We propose a novel fully dynamic algorithm that maintains a (4+ε)-approximate solution to the k-center problem with z outliers that covers all but at most (1+ε)z points at any time. Our dynamic algorithm presents a significant improvement over the recent dynamic (14+ε)-approximation algorithm by Chan, Lattanzi, Sozio, and Wang for this problem.
(back)