3,654 research outputs found
Fast Convolutions for Near-Convex Sequences
Full text linkWe develop algorithms for (min,+)-Convolution and related convolution problems such as Super Additivity Testing, Convolution 3-Sum and Minimum Consecutive Subsums which use the degree of convexity of the instance as a parameter. Assuming the min-plus conjecture (Künnemann-Paturi-Schneider, ICALP'17 and Cygan et al., ICALP'17), our results interpolate in an optimal manner between fully convex instances, which can be solved in near-linear time using Legendre transformations, and general non-convex sequences, where the trivial quadratic-time algorithm is conjectured to be best possible, up to subpolynomial factors
Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs
Full text linkWe solve the Bin Packing problem in time, where is the number
of items less or equal to one third of the bin capacity. This parameter
measures the distance from the polynomially solvable case of only large (i.e.,
greater than one third) items. Our algorithm is actually designed to work for a
more general Vector Bin Packing problem, in which items are multidimensional
vectors. We improve over the previous fastest time
algorithm.
Our algorithm works by reducing the problem to finding an exact weight
perfect matching in a (multi-)graph with edges, whose weights are
integers of the order of . To solve the matching problem in the
desired time, we give a variant of the classic Mulmuley-Vazirani-Vazirani
algorithm with only a linear dependence on the edge weights and the number of
edges, which may be of independent interest.
Moreover, we give a tight lower bound, under the Strong Exponential Time
Hypothesis (SETH), showing that the constant in the base of the exponent
cannot be further improved for Vector Bin Packing.
Our techniques also lead to improved algorithms for Vector Multiple Knapsack,
Vector Bin Covering, and Perfect Matching with Hitting Constraints.Comment: ICALP 202
Parameterized algorithms for block-structured integer programs with large entries
Full text linkWe study two classic variants of block-structured integer programming.
Two-stage stochastic programs are integer programs with constraints of the form
A_i x + D_i y_i = b_i for all i = 1, ..., n,
where A_i and D_i are bounded-size matrices. Intuitively, after choosing a small set of global variables x, the problem decomposes into many bounded-size subproblems.
n-fold programs are integer programs with constraints of the form
(∑_i C_i y_i = a) and (D_i y_i = b_i for all i = 1, ..., n),
again with bounded-size matrices C_i and D_i. This captures knapsack-like settings where variables are partitioned into small groups that obey local constraints, while a few global constraints link all variables.
Recent work shows that optimization for both two-stage stochastic programs and n-fold programs is fixed-parameter tractable (FPT) when parameterized by the dimensions of the relevant matrices A_i, C_i, D_i and by the maximum absolute entry in the constraint matrix. A key tool is the Graver basis, which assumes all constraint entries are bounded.
We prove that these FPT results persist even when large entries are allowed in the global part of the program:
Two-stage stochastic programs (feasibility): FPT when parameterized by the dimensions of A_i and D_i and by the maximum absolute entry of D_i. In particular, A_i may have arbitrarily large entries.
Uniform n-fold integer programs (linear optimization): FPT when parameterized by the dimensions of C_i and D_i and by the maximum absolute entry of D_i, provided all C_i are equal to a common matrix C; C may have arbitrarily large entries.
The uniformity requirement in the second result is necessary: without it, the problem is NP-hard even for constant parameter values. Both algorithms are weakly polynomial, with running time measured in the total bit size of the input.
Methodologically, we move beyond a purely Graver-basis approach. For two-stage stochastic programs, we reduce to an integer program with a bounded number of variables using new insights about the combinatorics of integer cones. For n-fold programs, we reduce the given instance to an exponential-size program with bounded right-hand sides, and then solve it via a reduction to mixed-integer programming with a bounded number of integral variables
Parameterized Algorithms for Matching Integer Programs with Additional Rows and Columns
Full text linkWe study integer linear programs (ILP) of the form min{c^⊤ x | Ax = b,l ≤ x ≤ u,x ∈ ℤⁿ} and analyze their parameterized complexity with respect to their distance to the generalized matching problem, following the well-established approach of capturing the hardness of a problem by the distance to triviality. The generalized matching problem is an ILP where each column of the constraint matrix has 1-norm of at most 2. It captures several well-known polynomial time solvable problems such as matching and flow problems. We parameterize by the size of variable and constraint backdoors, which measure the least number of columns or rows that must be deleted to obtain a generalized matching ILP. This extends generalized matching problems by allowing a parameterized number of additional arbitrary variables or constraints, yielding a novel parameter.
We present the following results: (i) a fixed-parameter tractable (FPT) algorithm for ILPs parameterized by the size p of a minimum variable backdoor to generalized matching; (ii) a randomized slice-wise polynomial (XP) time algorithm for ILPs parameterized by the size h of a minimum constraint backdoor to generalized matching as long as c and A are encoded in unary; (iii) we complement (ii) by proving that solving an ILP is W[1]-hard when parameterized by h even when c,A,l,u have coefficients of constant size. To obtain (i), we prove a variant of lattice-convexity of the degree sequences of weighted b-matchings, which we study in the light of SBO jump M-convex functions. This allows us to model the matching part as a polyhedral constraint on the integer backdoor variables. The resulting ILP is solved in FPT time using an integer programming algorithm. For (ii), the randomized XP time algorithm is obtained by pseudo-polynomially reducing the problem to the exact matching problem. To prevent an exponential blowup in terms of the encoding length of b, we bound the Graver complexity of the constraint matrix and employ a Graver augmentation local search framework. The hardness result (iii) is obtained through a parameterized reduction from ILP with h constraints and coefficients encoded in unary
Near-Linear Time Algorithm for n-fold ILPs via Color Coding
Full text linkWe study an important case of ILPs max {c^Tx | Ax = b, l <= x <= u, x in Z^{n t}} with n * t variables and lower and upper bounds l, u in Z^{nt}. In n-fold ILPs non-zero entries only appear in the first r rows of the matrix A and in small blocks of size s x t along the diagonal underneath. Despite this restriction many optimization problems can be expressed in this form. It is known that n-fold ILPs can be solved in FPT time regarding the parameters s, r, and Delta, where Delta is the greatest absolute value of an entry in A. The state-of-the-art technique is a local search algorithm that subsequently moves in an improving direction. Both, the number of iterations and the search for such an improving direction take time Omega(n), leading to a quadratic running time in n. We introduce a technique based on Color Coding, which allows us to compute these improving directions in logarithmic time after a single initialization step. This leads to the first algorithm for n-fold ILPs with a running time that is near-linear in the number nt of variables, namely (rs Delta)^{O(r^2s + s^2)} L^2 * nt log^{O(1)}(nt), where L is the encoding length of the largest integer in the input. In contrast to the algorithms in recent literature, we do not need to solve the LP relaxation in order to handle unbounded variables. Instead, we give a structural lemma to introduce appropriate bounds. If, on the other hand, we are given such an LP solution, the running time can be decreased by a factor of L
Separable Convex Mixed-Integer Optimization: Improved Algorithms and Lower Bounds
Full text linkWe provide several novel algorithms and lower bounds in central settings of mixed-integer (non-)linear
optimization, shedding new light on classic results in the field. This includes an improvement on
record running time bounds obtained from a slight extension of Lenstra’s 1983 algorithm [Math.
Oper. Res. ’83] to optimizing under few constraints with small coefficients. This is important for ubiquitous tasks like knapsack–, subset sum– or scheduling problems [Eisenbrand and Weismantel,
SODA’18, Jansen and Rohwedder, ITCS’19].
Further, we extend our algorithm to an intermediate linear optimization problem when the
matrix has many rows that exhibit 2-stage stochastic structure, which adds to a prominent line
of recent results on this and similarly restricted cases [Jansen et al. ICALP’19, Cslovjecsek et al.
SODA’21, Brand et al. AAAI’21, Klein, Reuter SODA’22, Cslovjecsek et al. SODA’24]. We also
show that the generalization of two fundamental classes of structured constraints from these works
(n-fold and 2-stage stochastic programs) to separable-convex mixed-integer optimization are harder
than their mixed-integer, linear counterparts. This counters a widespread belief popularized initially
by an influential paper of Hochbaum and Shanthikumar, namely that “convex separable optimization
is not much harder than linear optimization” [J. ACM ’90].
To obtain our algorithms, we employ the mixed Graver basis introduced by Hemmecke [Math. Prog. ’03], and our work is the first to give bounds on the norm of its elements. Importantly, we use these bounds differently from how purely-integer Graver bounds are exploited in related approaches, and prove that, surprisingly, this cannot be avoided
Parameterized algorithms for block-structured integer programs with large entries
Full text linkWe study two classic variants of block-structured integer programming. Two-stage stochastic programs are integer programs of the form {Aix + Diyi = bi for all i = 1, ..., n}, where Ai and Di are bounded-size matrices. Intuitively, this form corresponds to the setting when after setting a small set of global variables x, the program can be decomposed into a possibly large number of bounded-size subprograms. On the other hand, n-fold programs are integer programs of the form (Equation presented) Ciyi = a and Diyi = bi for all i = 1, ..., n}, where again Ci and Di are bounded-size matrices. This form is natural for knapsack-like problems, where we have a large number of variables partitioned into small-size groups, each group needs to obey some set of local constraints, and there are only a few global constraints that link together all the variables. A line of recent work established that the optimization problem for both two-stage stochastic programs and n-fold programs is fixed-parameter tractable when parameterized by the dimensions of relevant matrices Ai, Ci, Di and by the maximum absolute value of any entry appearing in the constraint matrix. A fundamental tool used in these advances is the notion of the Graver basis of a matrix, and this tool heavily relies on the assumption that all the entries of the constraint matrix are bounded. In this work, we prove that the parameterized tractability results for two-stage stochastic and n-fold programs persist even when one allows large entries in the global part of the program. More precisely, we prove the following: In this work, we prove that the parameterized tractability results for two-stage stochastic and n-fold programs persist even when one allows large entries in the global part of the program. More precisely, we prove the following: • The feasibility problem for two-stage stochastic programs is fixed-parameter tractable when parameterized by the dimensions of matrices Ai, Di and by the maximum absolute value of the entries of matrices Di. That is, we allow matrices Ai to have arbitrarily large entries. • The linear optimization problem for n-fold integer programs that are uniform - all matrices Ci are equal - is fixed-parameter tractable when parameterized by the dimensions of matrices Ci and Di and by the maximum absolute value of the entries of matrices Di. That is, we require that Ci = C for all i = 1, ..., n, but we allow C to have arbitrarily large entries. In the second result, the uniformity assumption is necessary; otherwise the problem is NP-hard already when the parameters take constant values. Both our algorithms are weakly polynomial: the running time is measured in the total bitsize of the input. In both results, we depart from the approach that relies purely on Graver bases. Instead, for two-stage stochastic programs, we devise a reduction to integer programming with a bounded number of variables using new insights about the combinatorics of integer cones. For n-fold programs, we reduce a given n-fold program to an exponential-size program with bounded right-hand sides, which we consequently solve using a reduction to mixed integer programming with a bounded number of integral variables.</p
Cardinality Constrained Scheduling in Online Models
Full text linkMakespan minimization on parallel identical machines is a classical and intensively studied problem in scheduling, and a classic example for online algorithm analysis with Graham’s famous list scheduling algorithm dating back to the 1960s. In this problem, jobs arrive over a list and upon an arrival, the algorithm needs to assign the job to a machine. The goal is to minimize the makespan, that is, the maximum machine load. In this paper, we consider the variant with an additional cardinality constraint: The algorithm may assign at most k jobs to each machine where k is part of the input. While the offline (strongly NP-hard) variant of cardinality constrained scheduling is well understood and an EPTAS exists here, no non-trivial results are known for the online variant. We fill this gap by making a comprehensive study of various different online models. First, we show that there is a constant competitive algorithm for the problem and further, present a lower bound of 2 on the competitive ratio of any online algorithm. Motivated by the lower bound, we consider a semi-online variant where upon arrival of a job of size p, we are allowed to migrate jobs of total size at most a constant times p. This constant is called the migration factor of the algorithm. Algorithms with small migration factors are a common approach to bridge the performance of online algorithms and offline algorithms. One can obtain algorithms with a constant migration factor by rounding the size of each incoming job and then applying an ordinal algorithm to the resulting rounded instance. With this in mind, we also consider the framework of ordinal algorithms and characterize the competitive ratio that can be achieved using the aforementioned approaches. More specifically, we show that in both cases, one can get a competitive ratio that is strictly lower than 2, which is the bound from the standard online setting. On the other hand, we prove that no PTAS is possible
Author, Philosopher Alexandra Stoddard to Speak March 2 at Williams Library
No full textOXFORD, Miss. – Contemporary philosopher, author, interior designer and speaker Alexandra Stoddard gives an inspirational lecture and reading March 2 at the University of Mississippi
Solving packing problems with few small items using rainbow matchings
Full text linkAn important area of combinatorial optimization is the study of packing and covering problems, such as Bin Packing, Multiple Knapsack, and Bin Covering. Those problems have been studied extensively from the viewpoint of approximation algorithms, but their parameterized complexity has only been investigated barely. For problem instances containing no “small” items, classical matching algorithms yield optimal solutions in polynomial time. In this paper we approach them by their distance from triviality, measuring the problem complexity by the number k of small items.
Our main results are fixed-parameter algorithms for vector versions of Bin Packing, Multiple Knapsack, and Bin Covering parameterized by k. The algorithms are randomized with one-sided error and run in time 4k · k! · nO(1). To achieve this, we introduce a colored matching problem to which we reduce all these packing problems. The colored matching problem is natural in itself and we expect it to be useful for other applications. We also present a deterministic fixed-parameter algorithm for Bin Packing with run time O((k!)2 · k · 2k · n log(n))
- …
