Mathematical Programming

Journal: Mathematical Programming

Abbreviation

Math. Program.

Publisher

Springer

ISSN

0025-5610
1436-4646

Show all metadata

Search Results

Publications 1 - 10 of 51

A colorful Steinitz Lemma with application to block-structured integer programs
Oertel, Timm; Paat, Joseph; Weismantel, Robert (2024)
Mathematical Programming
The Steinitz constant in dimension d is the smallest value c(d) such that for any norm on Rd and for any finite zero-sum sequence in the unit ball, the sequence can be permuted such that the norm of each partial sum is bounded by c(d). Grinberg and Sevastyanov prove that c(d)≤d and that the bound of d is best possible for arbitrary norms; we refer to their result as the Steinitz Lemma. We present a variation of the Steinitz Lemma that permutes multiple sequences at one time. Our result, which we term a colorful Steinitz Lemma, demonstrates upper bounds that are independent of the number of sequences. Many results in the theory of integer programming are proved by permuting vectors of bounded norm; this includes proximity results, Graver basis algorithms, and dynamic programs. Due to a recent paper of Eisenbrand and Weismantel, there has been a surge of research on how the Steinitz Lemma can be used to improve integer programming results. As an application we prove a proximity result for block-structured integer programs.
Sum-of-squares hierarchy lower bounds for symmetric formulations
Kurpisz, Adam; Leppänen, Samuli; Mastrolilli, Monaldo (2020)
Mathematical Programming
A fast (2+27)-approximation algorithm for capacitated cycle covering
Traub, Vera; Tröbst, Thorben (2022)
Mathematical Programming
We consider the capacitated cycle covering problem: given an undirected, complete graph G with metric edge lengths and demands on the vertices, we want to cover the vertices with vertex-disjoint cycles, each serving a demand of at most one. The objective is to minimize a linear combination of the total length and the number of cycles. This problem is closely related to the capacitated vehicle routing problem (CVRP) and other cycle cover problems such as min-max cycle cover and bounded cycle cover. We show that a greedy algorithm followed by a post-processing step yields a (2 + 2/7)-approximation for this problem by comparing the solution to a polymatroid relaxation. We also show that the analysis of our algorithm is tight and provide a 2+ epsilon lower bound for the relaxation.
Matrix discrepancy and the log-rank conjecture
Sudakov, Benny; Tomon, István (2025)
Mathematical Programming
A technique for obtaining true approximations for k-center with covering constraints
Anegg, Georg; Angelidakis, Haris; Kurpisz, Adam; et al. (2022)
Mathematical Programming
There has been a recent surge of interest in incorporating fairness aspects into classical clustering problems. Two recently introduced variants of the k-Center problem in this spirit are Colorful k-Center, introduced by Bandyapadhyay, Inamdar, Pai, and Varadarajan, and lottery models, such as the Fair Robust k-Center problem introduced by Harris, Pensyl, Srinivasan, and Trinh. To address fairness aspects, these models, compared to traditional k-Center, include additional covering constraints. Prior approximation results for these models require to relax some of the normally hard constraints, like the number of centers to be opened or the involved covering constraints, and therefore, only obtain constant-factor pseudo-approximations. In this paper, we introduce a new approach to deal with such covering constraints that leads to (true) approximations, including a 4-approximation for Colorful k-Center with constantly many colors—settling an open question raised by Bandyapadhyay, Inamdar, Pai, and Varadarajan—and a 4-approximation for Fair Robust k-Center, for which the existence of a (true) constant-factor approximation was also open. We complement our results by showing that if one allows an unbounded number of colors, then Colorful k-Center admits no approximation algorithm with finite approximation guarantee, assuming that P≠NP. Moreover, under the Exponential Time Hypothesis, the problem is inapproximable if the number of colors grows faster than logarithmic in the size of the ground set.
k-Trails: recognition, complexity, and approximations
Singh, Mohit; Zenklusen, Rico (2018)
Mathematical Programming
The notion of degree-constrained spanning hierarchies, also called k-trails, was recently introduced in the context of network routing problems. They describe graphs that are homomorphic images of connected graphs of degree at most k. First results highlight several interesting advantages of k-trails compared to previous routing approaches. However, so far, only little is known regarding computational aspects of k-trails. In this work we aim to fill this gap by presenting how k-trails can be analyzed using techniques from algorithmic matroid theory. Exploiting this connection, we resolve several open questions about k-trails. In particular, we show that one can recognize efficiently whether a graph is a k-trail, and every graph containing a k-trail is a (k +1)-trail. Moreover, further leveraging the connection to matroids, we consider the problem of finding a minimum weight k-trail contained in a graph G. We show that one can efficiently find a (2k − 1)-trail contained in G whose weight is no more than the cheapest k-trail contained in G, even when allowing negative weights. The above results settle several open questions raised by Molnár, Newman, and Sebő.
Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation
Chudak, Fabián A.; Roughgarden, Tim; Williamson, David P. (2004)
Mathematical Programming
New approaches to multi-objective optimization
Grandoni, Fabrizio; Ravi, Ramamoorthi; Singh, Mohit; et al. (2014)
Mathematical Programming
A natural way to deal with multiple, partially conflicting objectives is turning all the objectives but one into budget constraints. Many classical optimization problems, such as maximum spanning tree and forest, shortest path, maximum weight (perfect) matching, maximum weight independent set (basis) in a matroid or in the intersection of two matroids, become NP-hard even with one budget constraint. Still, for most of these problems efficient deterministic and randomized approximation schemes are known. Not much is known however about the case of two or more budgets: filling this gap, at least partially, is the main goal of this paper. In more detail, we obtain the following main results: Using iterative rounding for the first time in multi-objective optimization, we obtain multi-criteria PTASs (which slightly violate the budget constraints) for spanning tree, matroid basis, and bipartite matching with k=O(1) budget constraints. We present a simple mechanism to transform multi-criteria approximation schemes into pure approximation schemes for problems whose feasible solutions define an independence system. This gives improved algorithms for several problems. In particular, this mechanism can be applied to the above bipartite matching algorithm, hence obtaining a pure PTAS. We show that points in low-dimensional faces of any matroid polytope are almost integral, an interesting result on its own. This gives a deterministic approximation scheme for k-budgeted matroid independent set. We present a deterministic approximation scheme for k-budgeted matching (in general graphs), where k=O(1). Interestingly, to show that our procedure works, we rely on a non-constructive result by Stromquist and Woodall, which is based on the Ham Sandwich Theorem.
A polynomial oracle-time algorithm for convex integer minimization
Hemmecke, Raymond; Onn, Shmuel; Weismantel, Robert (2011)
Mathematical Programming
Hyperbolic set covering problems with competing ground-set elements
Amaldi, Edoardo; Bosio, Sandro; Malucelli, Federico (2012)
Mathematical Programming

Publications 1 - 10 of 51

Journal: Mathematical Programming

Abbreviation

Publisher

Journal Volumes

ISSN

Description

Filters

Search Results