PaperlayerView exact revision on arXiv

Source-linked AI summary

A Constructive FPT Algorithm for Integer Cone Optimization with Convex Costs

Klaus Jansen, Felix Ohnesorge

arXiv:2609.31328v4cs.DS

TL;DR

The paper addresses the lack of an FPT algorithm for Cone and Polytope Intersection parameterized by dimension. It gives a deterministic constructive algorithm for multiple generator types and convex costs, with sparse optimal representations and applications including bin packing and scheduling.

  • Problem

    Earlier Cone and Polytope Intersection algorithms left open FPT tractability in dimension because their refined running time depends on the integer hull’s vertex count.

    Source: §1 · p. 2

  • Method

    The paper extends the residue-decomposition approach to multiple generator polytopes with convex costs and combines it with a support bound to construct sparse certificates.

    Source: §1 · p. 4

  • Results

    The algorithm returns an optimal vector or reports infeasibility or unboundedness, and its applications include constructive FPT algorithms for packing and scheduling problems.

    Source: §1 · p. 4, §3.6 · p. 16

  • Takeaways & Limitations

    The applications establish FPT parameterizations for point-in-cone, bin packing, vector bin packing, and scheduling, with the dependence on d ETH-tight for point-in-cone and bin-packing applications.

    Source: §1 · p. 4

    For scheduling, the uniform and unrelated models are parameterized with τ machine types.

    Source: §1 · p. 4

Abstract

from arXiv · show

We give a deterministic fixed-parameter algorithm for integer cone optimization with convex costs. Given $\tau$ rational polytopes in $\mathbb{R}^d$, each with a convex cost function, we minimize the total cost of nonnegative integer combinations of their lattice points subject to arbitrary rational linear constraints on the typewise aggregates and generator counts. Our algorithm runs in time \[ 2^{\tau\log(\tau+1)\,2^{O(d)}}\cdot |I|^{O(1)}, \] where $|I|$ is the total binary input length. It constructs an optimal representation using at most $2^{2d+1}$ distinct generators per type. For a single generator type, the running time becomes $2^{2^{O(d)}}\cdot |I|^{O(1)}$. This yields constructive FPT algorithms for Cone and Polytope Intersection and high-multiplicity bin packing, improving the $2^{2^{O(d\log d)}}\cdot |I|^{O(1)}$ bound of Koana and Kumabe (2026) for bin-packing decision. The dependence on $d$ is ETH-tight for point-in-cone, high-multiplicity bin packing, and vector bin packing. For vector bin packing, this establishes fixed-parameter tractability in the number of item types. We also obtain new FPT parameterizations for high-multiplicity scheduling on uniform and unrelated machines: makespan minimization and $\ell_q$-load minimization are FPT in the number of job and machine types.

1 Introduction

The introduction frames Cone and Polytope Intersection as combining integer generators under aggregate constraints, then presents a constructive extension to multiple types and convex costs. It addresses the gap between XP and FPT algorithms in dimension and connects the framework to packing and scheduling applications.

1 Introduction

  • The earlier Cone and Polytope Intersection algorithms left open whether an FPT algorithm parameterized by dimension exists, since the refined running time depends on the integer hull’s vertex count.The problem includes point-in-cone and high-multiplicity bin packing as special cases.Source: §1 · p. 2
  • Koana and Kumabe [26] give an FPT decision algorithm for high-multiplicity bin packing, but do not provide an explicit certificate.Their method partitions generators into residue classes modulo d and uses the Integer Decomposition Property of each class’s convex hull.Source: §1 · p. 2
  • Appendix C extends the results to efficiently approximable convex costs when sparse objective values have a certified gap.The extension includes costs f(t)(x) = ℓt(x)3/2 for rational affine functions ℓt nonnegative on P(t).Source: §1 · p. 3
  • The paper extends the approach in [26] to multiple generator polytopes with convex costs and explicitly constructs a sparse certificate.The formulation permits rational linear constraints on typewise aggregates and generator counts.Source: §1 · pp. 2–4
  • For each type, the algorithm uses at most 2d active residue classes, enumerates their tuples, and solves convex integer feasibility instances in at most D = τ(d + 1)2d variables.Small integer solution bounds reduce the general problem to bounded multiplicity; a second call with homogeneous constraints detects improving recession directions.Source: §1 · p. 4
  • The applications include point-in-cone, high-multiplicity and vector bin packing, bin covering, scheduling, and cutting stock, with constructive FPT algorithms parameterized by d + τ where stated.The dependence on d is ETH-tight for point-in-cone and the bin-packing applications; scheduling on uniform or unrelated machine types is covered for fixed-power convex load costs.Source: §1 · p. 4
  • For scheduling, the uniform and unrelated machine models are parameterized using τ machine types.The stated input parameters also include the total number of machines m and the largest integral processing requirement pmax before speed scaling in the uniform model.Source: §1 · p. 4

2 Preliminaries

The preliminaries state the assumptions on convex costs and oracle access used by the algorithm, alongside structural facts about integer cones and separation oracles.

2 Preliminaries

  • The algorithm accesses polynomial cost functions at integer generators through three stated properties, and explicitly given polynomials satisfy them.The stated properties include discrete Jensen behavior, exact evaluation with an encoding bound, and a common lattice denominator for objective values.Source: §2 · pp. 4–5
  • Because the polytopes are bounded, integer generators have polynomial encoding length and their polynomial costs can be evaluated exactly in polynomial time.The cost values also have polynomially bounded binary encoding length, and a common denominator makes objective-value binary search well-defined.Source: §2 · p. 5
  • A strong separation oracle either certifies that a query point belongs to a convex set or returns a separating rational vector with polynomially bounded encoding length.Source: §2 · p. 5
  • Eisenbrand and Shmonin’s integer-cone bound gives a representation using at most 2d generators, and the paper notes that this support bound is asymptotically tight.The lemma applies to finite X ⊆ Z^d with conv(X) ∩ Z^d = X.Source: §2 · p. 5

3 The Algorithm

The algorithm develops a restricted formulation for optimizing fractional costs over residue classes and reconstructing sparse integer representations, while limiting the residue classes used in its search. It solves the resulting integer-feasibility tests with separation oracles and exact budget search, using a uniform multiplicity bound to establish infeasibility, unboundedness, and optimality outcomes.

3 The Algorithm

  • A deterministic computation takes 2^{O(d^2 log(d+1))}·(|I|+enc(a))^{O(1)} time; an optimal primal representation in (3.1a), supported on at most d + 1 generators, takes 2^{O(d^2 log(d+1))}·(|I|+enc(z,n))^{O(1)} time.Source: §3 · p. 7

3.1 Explicit Solution Reconstruction

  • An integer aggregate and count admit a cost-nonincreasing decomposition using at most 2d + 1 distinct integer generators, constructible within the stated parameterized time.The generators lie in the residue hull and have binary-encoded positive integer multiplicities.Source: §3.1 · pp. 7–9

3.2 Sparse Support for Convex Objectives

  • Convex-cost sparsification preserves aggregates, counts, and constraints while limiting support to 2d generators per type, yielding at most τ2d total support.This support bound also limits each type to at most 2d active residue classes; the candidate active-residue tuples are bounded by 2^(τ·2^O(d)).Source: §3.2 · p. 10

3.3 Restricted Polyhedral Convex Formulation

  • For a fixed active-residue tuple, the restricted polyhedral formulation uses aggregate-and-count variables, and for one type feasibility at cost at most γ is equivalent to an integer point for some R with |R| ≤ 2d.The relaxation encodes aggregate, typewise, count, and cost constraints across active residue classes.Source: §3.3 · pp. 11–12
  • A feasible solution of cost at most γ exists exactly when some candidate tuple yields an integer point in K_R(γ), preserving the typewise aggregates and counts.The correspondence preserves the constraints on aggregates, counts, and costs.Source: §3.3 · pp. 12–13

3.4 Solving the Formulation via Separation Oracles

  • For each candidate tuple, deterministic integer feasibility over K_R(γ) uses a polynomial-encoding bounding box and a strong separation oracle combining residue-hull and fractional-cost oracles.The randomized algorithm of Reis and Rothvoss [32] gives a faster variant without changing the stated double-exponential dependence on d.Source: §3.4 · pp. 13–14

3.5 Exact Optimization from Budget Feasibility

  • For a supplied multiplicity bound, exact budget search yields an optimum or reports infeasibility, with at most 2^{2d+1} generators per type.Attainable objective values lie on a computable rational grid, so binary search over scaled integer budgets finds the minimum feasible budget.Source: §3.5 · p. 15

3.6 Proof of the Main Theorem

  • The deterministic algorithm reports infeasibility or unboundedness below, or returns an optimal representation supported on at most 2^{2d+1} generators per type.A uniform multiplicity bound reduces the problem to the bounded-multiplicity algorithm; a negative-cost solution to the zero-right-hand-side instance certifies unboundedness below.Source: §3.5 · p. 15, §3.6 · p. 16

4 Declaration of Generative AI Use

The authors describe generative AI use in theorem formulation, proof work, editing, notation review, and literature search, and state that they independently verified the proofs. The applications encode multiplicities in binary and return configurations with multiplicities rather than listing every item or machine.

4 Declaration of Generative AI Use

  • The authors used generative AI for theorem and proof formulation, language editing, notation review, and literature search, while independently verifying the proofs.They state that they take full responsibility for the paper's content.Source: §4 · p. 16

A Applications

  • Application multiplicities are binary-encoded, and returned configurations with multiplicities avoid listing every item or machine individually.The applications use explicitly given convex polynomials with rational coefficients.Source: A Applications · p. 19

A.1 Machine Scheduling

The scheduling applications give constructive fixed-parameter algorithms for convex load costs and makespan on uniform and unrelated machines. Their parameterization uses the number of job types and machine types, and the algorithm returns sparse configuration representations.

A.1 Machine Scheduling

  • The objective (A.1) is equivalent to minimizing the ℓ_q norm of the load vector, with q = 2 giving the sum of squared loads.The reduction records how many machines of each type use each configuration, including idle machines, and its additive generator cost equals (A.1).Source: §A.1 · pp. 19–20
  • For uniform and unrelated machines, earlier cited algorithms parameterized by processing requirements or total machines, whereas this result parameterizes by d + τ.The paper notes that extending an earlier framework to convex objectives beyond small processing requirements was an open direction.Source: §A.1 · p. 19
  • Scheduling with fixed integer q ≥1 and d job types on τ distinct machine speeds has a deterministic algorithm returning at most 2^(2d+1) configurations per speed.The stated parameterization is d + τ, with polynomial dependence on the binary encodings of processing times and speeds.Source: §A.1 · p. 19
  • The scheduling reduction also covers unrelated machines with type-specific processing-time vectors and the same d + τ parameterization.For type t, the load cost is (⟨p(t), x⟩)^q.Source: §A.1 · p. 20
  • Makespan feasibility is tested by replacing each machine's configuration domain with configurations whose load is at most the prescribed makespan T.Zero costs decide feasibility; binary search after scaling finite processing times to integers yields exact makespan minimization in polynomially many calls.Source: §A.1 · p. 20

A.2 Point in Cone and High-Multiplicity Bin Packing

The paper obtains constructive fixed-parameter algorithms for point-in-cone and high-multiplicity bin packing, returning sparse generator representations. For bin packing, the dependence on the number of item types improves on the cited prior bound and is ETH-tight.

A.2 Point in Cone and High-Multiplicity Bin Packing

  • Point-in-cone membership has a constructive FPT algorithm that returns a certificate supported on at most 2^(2d+1) generators.The paper states that this matches the cited lower bound.Source: §A.2 · p. 21
  • High-multiplicity bin packing runs in 2^(2O(d)) · |I|^O(1) time and returns a packing with at most 2^(2d+1) distinct generators.This improves the cited 2^(2O(d log d)) dependence and is ETH-tight in d.Source: §A.2 · p. 21
  • The same theorem directly minimizes the number of bins by setting each generator's cost to 1, retaining the running time and support bound.It returns a minimum-bin packing or reports infeasibility.Source: §A.2 · p. 22

A.3 Vector Bin Packing

High-multiplicity vector bin packing is fixed-parameter tractable in the number of item types, even when the number of resource dimensions is part of the input. The algorithm returns a minimum-bin packing with a sparse configuration representation.

A.3 Vector Bin Packing

  • With d item types, vector bin packing runs deterministically in 2^(2O(d)) · |I|^O(1) time and returns a minimum-bin packing using at most 2^(2d+1) configurations.The number r of resource dimensions is part of the input and is not a parameter.Source: §A.3 · p. 22
  • A prescribed bin bound is handled by adding N(1) ≤ b and setting the objective cost to zero.Ordinary bin packing is the case r = 1, making the double-exponential dependence on d ETH-tight.Source: §A.3 · p. 22

A.4 Several Bin Types and Cutting Stock

The framework handles multiple bin types with different capacity vectors and nonnegative costs, and yields minimum-cost packing with a bounded number of configurations per type. In one resource dimension, it applies to cutting stock, where the number of item types alone does not give FPT tractability when stock types are unrestricted.

A.4 Several Bin Types and Cutting Stock

  • Theorem 1 yields a minimum-cost packing with at most 2^{2d+1} configurations per bin type.Each bin type has capacity vector B(t) and nonnegative rational cost; finite supplies can be imposed by N(t) ≤ m(t).Source: §A.4 · pp. 22–23
  • In one resource dimension, the formulation is cutting stock with d requested piece lengths and τ stock lengths and prices.The configuration formulation goes back to Gilmore and Gomory [9].Source: §A.4 · p. 23
  • Cutting stock is NP-hard with eight item types when the number of stock types is unrestricted, so item types alone do not yield FPT unless P = NP.Goemans and Rothvoss [10, Section 6.1] give an XP algorithm parameterized by d + τ.Source: §A.4 · p. 23

A.5 Bin Covering

Bin covering maximizes the number of disjoint item groups whose total size reaches a threshold, allowing unused items. The paper applies its single-generator-type theorem directly to binary multiplicities, giving an FPT algorithm parameterized by item types.

A.5 Bin Covering

  • Bin covering maximizes the number of disjoint groups of items with total size at least B, while allowing unused items.The input gives positive rational item sizes and multiplicities.Source: §A.5 · p. 23
  • The algorithm applies directly to binary multiplicities and is parameterized by the number of item types.Prior randomized FPT algorithms for explicitly listed items parameterize by the number of small items, which may be large even with few item types.Source: §A.5 · p. 23
  • An XP algorithm parameterized by d follows from the cone theorem by appending a coordinate equal to one and testing whether at least k bins can be covered.Binary search over k finds the optimum.Source: §A.5 · p. 23
  • Theorem 1 computes an optimum in time 2^{2^{O(d)}}|I|^{O(1)}, represented by at most 2^{2d+1} distinct covered-bin configurations.Each generator describes a covered bin; item-availability constraints enforce that the total use does not exceed the multiplicities.Source: §A.5 · p. 23

B.1 Separation and Cost Oracles

This section gives deterministic oracles for residue hulls and integer pricing. The pricing method transforms the feasible-region objective into a discrete-convex comparison function, then minimizes it over a bounded lattice set.

B.1 Separation and Cost Oracles

  • A strong separation oracle for each residue hull runs in 2^{O(d log d)}(enc(P)+enc(v))^{O(1)} time per query.It either certifies membership or returns a strictly separating normal and offset; an empty residue class can also be detected.Source: §B.1 · pp. 23–24
  • Integer pricing either detects an empty residue class or returns a minimizer, using deterministic time 2^{O(d^2 log(d+1))}(|I|+enc(a))^{O(1)}.The algorithm minimizes a comparison function over a bounded lattice set and returns a feasible point minimizing the pricing objective when one exists.Source: §B.1 · pp. 24–25
  • The pricing construction shifts the feasible region and objective, then assigns infeasible points a positive violation-based penalty so every feasible point ranks first.Among feasible points, the comparison function preserves the ordering by the transformed objective; comparisons use rational arithmetic and at most two evaluations of f.Source: §B.1 · p. 24
  • The comparison function is discrete convic: its lattice-cone condition ensures its value cannot decrease at the point z in the defining relation.The proof uses convexity of the violation function for infeasible points and discrete Jensen on feasible points.Source: §B.1 · pp. 24–25

B.2 Uniform Multiplicity Bound

The uniform multiplicity bound limits feasible representations and, when the objective is bounded below, optimal representations. The proof bounds an optimal integer solution using an LP vertex bound and a proximity theorem, and also bounds negative-cost representations satisfying the homogeneous aggregate constraints.

B.2 Uniform Multiplicity Bound

  • Every feasible instance has a feasible representation of total multiplicity at most N⋆; if its objective is bounded below, an optimal representation has the same bound.The bound also applies to a negative-cost integer generator representation whenever Wv ≤ 0 admits one.Source: §B.2 · p. 25
  • For an optimal support of at most s generators, the proof forms an integer program from the aggregate constraints and bounds its LP vertex coordinates by k!U^k.A proximity theorem then gives an integer optimum whose total multiplicity is at most k(k+1)k!U^k ≤ N⋆.Source: §B.2 · pp. 25–26
  • If Wv ≤ 0 has a negative-cost vertex, Cramer’s rule gives an integer representation of negative cost with total multiplicity at most N⋆.The common denominator q is at most k!U^k.Source: §B.2 · pp. 25–26

C More General Convex Costs

The results extend to convex costs accessed through approximation oracles, provided their approximation and objective-gap conditions are met. A computable gap bound preserves the original guarantees, including for costs such as rational affine loads raised to the 3/2 power.

C More General Convex Costs

  • Rational evaluation oracles satisfying Assumption 2 apply directly, while the extension covers convex costs that can only be approximated.The cost functions need only be accessed at integer generators.Source: C More General Convex Costs · p. 26
  • Convex costs with deterministic dyadic approximation and a supplied computable objective-gap bound retain Theorem 1’s guarantees.The oracle approximates each integer-generator cost within 2^-p in time polynomial in |I|+p, and the gap applies to sparse representations including zero.Source: C More General Convex Costs · p. 26
  • A bound B ≤ 2^{O(K)}|I|^{O(1)} preserves the original running-time bound if it can be computed within that time.Here K = τ2^{2d+1}.Source: C More General Convex Costs · pp. 26, 28
  • Surrogate rational costs preserve exact optimality and unboundedness for the original costs while retaining the algorithm’s support guarantee.The proof selects precision using the gap bound and multiplicity limit; the optimal representation for the original costs has total multiplicity at most N⋆.Source: C More General Convex Costs · pp. 27–28
  • For costs f^(t)(x)=ℓ_t(x)^{3/2} with rational affine ℓ_t≥0, rational square-root approximation supplies the required oracle and preserves the original guarantees.A computable gap bound is derived using an algebraic-integer norm argument.Source: C More General Convex Costs · p. 28
Loading 2609.31328v4…