Multiobjective integer (linear) programs (MOIPs), as the name suggests, simultaneously optimize multiple objective functions over a set of linear constraints and integer variables. Relaxations of MOIPs provide bounds on their solutions and play an important role in solution algorithms. In this talk, we present a Lagrangian relaxation of an MOIP and discuss its properties. Specifically, we show that there exist sparse Lagrangian multipliers that satisfy a complementary slackness property and generate tight relaxations at supported solutions. At unsupported solutions, where the convex hull relaxation is not tight either, we show that a Lagrangian relaxation improves upon the convex hull bounds. We use the Lagrangian relaxation to define a Lagrangian dual of an MOIP and establish weak duality. The dual is strong at supported solutions under certain conditions on the primal feasible region which are identical to the single-objective case.

The simplex algorithm is one the most popular algorithms to solve linear programs (LP). 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 extreme point along an improving edge-direction of the underlying polyhedron. A key issue in the simplex algorithm's performance is degeneracy, which may lead to a (potentially long) sequence of basis exchanges which do not change the current extreme point solution. In this paper, we prove that it is always possible to limit the number of consecutive degenerate pivots that the simplex algorithm performs to n-m-1, where n is the number of variables and m is the number of equality constraints of a given LP in standard equality form.

The weighted k-Set Packing problem is defined as follows: As input, we are given a collection S of sets, each of cardinality at most k, and a positive weight for each set in S. The task is to compute a subcollection A of S such that the sets in A are pairwise disjoint, and the total weight of A is maximum. The case k=2 is equivalent to the Maximum Weight Matching problem. For k >= 3, already the special case of unit weights, the unweighted k-Set Packing problem, is NP-hard.

The technique that has proven most successful in designing approximation algorithms for both the unweighted and the weighted k-Set Packing problem is local search. For the unweighted problem, the state-of-the-art is a polynomial-time (k+1)/3+epsilon-approximation by Fürer and Yu that takes into account certain local improvements of up to logarithmic size. For general weights, we recently showed that by considering a special class of local improvements of logarithmically bounded size, we can obtain a polynomial-time (k+epsilonk)/2-approximation, where epsilonk converges to 0 as k approaches infinity. We further proved that this result is asymptotically best possible: For general weights, one cannot achieve a better guarantee than k/2 by only considering local improvements of logarithmically bounded size.

At a first glance, this seems to conclude the story of local improvement algorithms for the weighted k-Set Packing problem. However, in this talk we show how to employ a black box algorithm for the unweighted k-Set Packing problem to generate local improvements of super-logarithmic size and obtain a polynomial-time 0.4986*k+0.5194-approximation algorithm for weighted k-Set Packing. Our techniques further allow us to establish a general connection between the approximation guarantees achievable for unit and general weights.

This result has been published in the proceedings of SODA 2023.