Titlebook: Integer Programming and Combinatorial Optimization; 25th International C Jens Vygen,Jarosław Byrka Conference proceedings 2024 The Editor(s

支形吊灯

,A First Order Method for Linear Programming Parameterized by Circuit Imbalance,nt solvers for large-scale LPs. From a theoretical perspective, linear convergence rates have been established for first order LP algorithms, despite the fact that the underlying formulations are not strongly convex. However, the convergence rate typically depends on the Hoffman constant of a large

IRK

,Approximately Packing Dijoins via Nowhere-Zero Flows, in 1976 that in every digraph, the minimum size of a dicut equals to the maximum number of disjoint dijoins. However, prior to our work, it was not even known whether at least 3 disjoint dijoins exist in an arbitrary digraph whose minimum dicut size is sufficiently large. By building connections wi

淘气

,Capacitated Facility Location with Outliers and Uniform Facility Costs,oximation for this problem. We give a local search algorithm that requires only 2 operations and is a 6.372+ . approximation. In developing this result we also improve the approximation guarantee of the capacitated facility location problem with uniform facility costs. Our local search algorithm is

output

landmark

,Assortment Optimization with Visibility Constraints,o as .. We are given a universe of substitutable products and a stream of . customers. The objective is to determine the optimal assortment of products to offer to each customer in order to maximize the total expected revenue, subject to the constraint that each product is required to be shown to a

abreast

轻率的你

储备

,Von Neumann-Morgenstern Stability and Internal Closedness in Matching Theory,opular, the approach by Gale and Shapley cannot encompass all the different features that arise in applications, motivating the search for alternative solution concepts. We investigate alternatives that rely on the concept of internal stability, a notion introduced for abstract games by von Neumann

deforestation

Fully-Dynamic Load Balancing,of machines and can be reassigned at any time step. The goal is to maintain a near-optimal maximum load at all time steps with a small total number of reassignments. We consider the setting where the degree of the jobs (number of machines they can be assigned to) is bounded. This is motivated from n

enumaerate

Pairwise-Independent Contention Resolution,pled according to a . (PI) distribution, we show a .-selectable OCRS for uniform matroids of rank ., and .-selectable OCRSs for laminar, graphic, cographic, transversal, and regular matroids. These imply prophet inequalities with the same ratios when the set of values is drawn according to a PI dist