CS Paper Radar

A Characterization of Functions on the Integer Lattice That Are L-Extendable through Local Convex Extensions

Ken Yokoyama, Yuni Iwamasa, Kei Kimura

cs.DM math.CO ·submitted 2026-10-28 05:12 UTC · v1

Abstract

L-extendable functions on the integer lattice are functions that admit a $\frac12$UJ-convex relaxation; that is, values can be assigned to the additional half-integral points, while keeping the original values at integer points, so that the resulting function is $\frac12$UJ-convex. Various examples of L-extendable functions and their applications are known. A general characterization of L-extendability for functions on the integer lattice, however, remains open. In this paper, we study the L-extendability of functions on the integer lattice. We first obtain a necessary condition: L-extendable functions are integrally convex. We then consider a special subclass of L-extendable functions, namely, those whose local convex extensions give L-convex relaxations. This subclass has a useful optimization property: the optimal value of the original function coincides with that of the $\frac12$UJ-convex relaxation given by its local convex extension, a property not guaranteed for general $\frac12$UJ-convex relaxations. We characterize this subclass by showing that a function is L-extendable through its local convex extension if and only if it is integrally convex and its restriction to every unit hypercube is D-convex, where D-convexity is a discrete convexity associated with reflected Freudenthal simplicial divisions. This subclass strictly contains the class of D-convex functions. We also give a combinatorial characterization of D-convex subsets of the vertices of a unit hypercube: a set $X\subseteq\{0,1\}^n$ is D-convex if and only if it is majority-closed and contains a relative opposite pair.

Comment
17 pages, 3 figures

Closest papers

Nearest neighbours by meaning across the whole index.

UTVPI-representable integer point sets: discrete convexity, polymorphisms, and pairwise closure

cs.DM ·2026-08-25 ·Kei Kimura, Kazuhisa Makino, Shota Yamada, Ryo Yoshizumi
theory similarity 0.64
Abstract · 48 pages, v2: acknowledgments updated, references added

We study subsets of the integer lattice represented by single-variable-per-inequality (SVPI), difference-constraint (DC), unit two-variable-per-inequality (UTVPI), and two-variable-per-inequality (TVPI) systems. We relate five viewpoints: inequality representation, discrete convexity, polymorphisms, reconstruction from two-coordinate projections, and fixed points of closure operators. Our central result completely characterizes UTVPI-representability. For every set $S\subseteq\mathbb Z^n$ with $n>1$, \[ \begin{aligned} &S\text{ is UTVPI-representable}\\ &\;\Longleftrightarrow\; S\text{ is closed under the directed midpoint and median operations}\\ &\;\Longleftrightarrow\; S\text{ is integrally convex and $2$-decomposable}. \end{aligned} \] The median condition may instead be replaced by closedness under some majority operation, and the same class is the fixed-point class of a pairwise directed-midpoint closure operator. Thus, all five viewpoints yield equivalent characterizations of UTVPI-representability. In particular, $2$-decomposability is exactly the global condition needed to lift the known two-dimensional equivalence between integral convexity and UTVPI-representability to arbitrary dimension. This theorem is embedded in a broader pairwise-closure theory. For a family $F$ of operations, we define a closure operator by closing every two-coordinate projection under $F$ and joining the resulting sets. Its fixed points are precisely the sets that are both $2$-decomposable and $F$-closed, and we establish a local-to-global criterion for such characterizations. A closed-convex-hull analogue characterizes TVPI-representability. We also characterize SVPI-representability by natural multioperations, prove limitations of operation-based characterizations for several related classes, and determine the complete inclusion hierarchies in the general, Boolean, and two-dimensional settings.

0.26

Towards discrete convex analysis over classical root systems

cs.DM math.COmath.OC ·2026-08-17 ·Yuni Iwamasa
similarity 0.63
Abstract · 97 pages, 6 tables

Discrete Convex Analysis (DCA) is a discrete analog of continuous convex analysis, originally proposed as a unified theoretical framework for efficiently solvable combinatorial optimization problems. Recently, DCA has proven to be a powerful tool across diverse fields, ranging from operations research to economics and pure mathematics. Motivated by the broad applicability of DCA, this paper establishes a unified theory of discrete convex analysis over discrete structures arising from classical root systems, extending the usual setting of the integer lattice, which essentially corresponds to type A. We adopt the vertex set of the Euclidean Coxeter complex as the primal discrete domain for L-convexity, and the root lattice as the dual discrete domain for M-convexity. Using the associated polyhedral structures, we formulate L- and M-convex functions together with notions of integrality determined by the root system. We show that local optimality guarantees global optimality for these functions. Furthermore, we establish that integral L-convex functions and integral M-convex functions correspond one-to-one via the discrete Fenchel--Legendre conjugate, thereby extending the conjugacy in the original DCA from type A to all classical root systems.

0.44

On the Complexity of Locally Dense Lattices

cs.CC ·2026-08-15 ·Shuichi Hirahara, Kazuki Ogitsuka
published similarity 0.58
Abstract · Full version of MFCS 2026

\emph{Locally dense lattices} are central gadgets used to prove the hardness of the Shortest Vector Problem and related lattice problems. Informally, a locally dense lattice is a lattice $\mathcal{L}$ that contains exponentially many lattice vectors inside some $\ell_p$ ball centered at $\vec{s}$ with radius at most an $α< 1$ fraction of the length of its shortest nonzero lattice vector. In this paper, taking a ``meta'' viewpoint on locally dense lattices, we introduce the \emph{Locally Dense Lattice Problem} (LDLP), the decision problem of determining whether a given input specifies a locally dense lattice. Our main result is that LDLP in $\ell_p$ norms for all finite $p \geq \log_2 3$ and for the infinity norm is complete for the second level of the polynomial hierarchy. We also compare two standard definitions of local density that appear in prior work. Micciancio's original definition (FOCS 1998 and SICOMP 2001) uses integer coefficient vectors, while later work by Micciancio (ToC 2012) and by Bennett and Peikert (RANDOM 2023) uses short vectors in a shifted coset. We show that the corresponding promise problems are mutually reducible in deterministic polynomial time, which shows that the two formulations are robust.

0.52

On the Triangle Inequality for the Jaccard Distance in Arbitrary Lattices

cs.AI cs.DMmath.CO ·2026-08-18 ·Costin Bădică, Amelia Bădică
theory similarity 0.55
Abstract

This paper presents new theoretical results on generalizing the Jaccard distance for lattices and real valuations. We demonstrate that when the valuation is strictly positive, monotone, and modular, the Jaccard distance satisfies the triangle inequality on arbitrary lattices, effectively generalizing earlier results that depended heavily on distributivity. Moving to relatively complemented distributive lattices (which safely drop the requirement for the global bounds found in Boolean algebras), we prove the triangle inequality holds as long as the valuation is positive, monotone, supermodular, and $\log$-submodular. Additionally, we adapt the symmetric-difference Jaccard formulation for submodular valuations to sectionally complemented distributive lattices. Shifting to necessary conditions, we prove that supermodularity is a strict requirement for the standard generalized Jaccard distance to operate as a valid metric. Finally, we map the practical value of relaxing these structural constraints to computational fields like quantum information theory, formal concept analysis, and machine learning, closing with a brief look at open mathematical problems.

0.24

A Constructive FPT Algorithm for Integer Cone Optimization with Convex Costs

cs.DS ·2026-09-25 ·Klaus Jansen, Felix Ohnesorge, Björn Schumacher
similarity 0.54
Abstract

We give a deterministic fixed-parameter algorithm for integer cone optimization with convex costs. Given $τ$ rational polytopes in $\R^{d+k}$, we combine generators whose first $d$ coordinates are integral and whose remaining $k$ coordinates may be fractional. Each generator has a convex cost depending only on its integer coordinates. We minimize the total cost of nonnegative integer combinations subject to arbitrary rational linear constraints on the full typewise aggregates and generator counts. Our algorithm runs in time \[ 2^{τ\log(τ+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. The number $k$ of continuous coordinates contributes only to the polynomial input factor. For a single generator type, the running time becomes $2^{2^{O(d)}}\cdot |I|^{O(1)}$. Applications include constructive FPT algorithms for Cone and Polytope Intersection, high-multiplicity bin packing, vector bin packing, and makespan minimization on uniform and unrelated machines. The double-exponential dependence on $d$ is tight for Point-in-Cone and both bin-packing problems assuming $\mathrm{NP}\nsubseteq\mathrm{SUBEXP}$. The mixed-integer formulation also yields additive EPTASs for makespan minimization, machine covering, and envy minimization on identical machines, and additive schemes fixed-parameter tractable in $1/\varepsilon+τ$ on uniform machines.

0.24

Geometry-Dependent Approximation for Non-Monotone $k$-Submodular Maximization

cs.DS cs.LGmath.OC ·2026-10-02 ·Vaneet Aggarwal
highly cited similarity 0.54
Abstract

We study the maximization of a nonnegative $k$-submodular function, not assumed monotone, in which each of $n$ elements receives one of $k\ge2$ labels or stays unselected and the selected elements must satisfy a constraint. For a compact convex down-closed region $P\subseteq[0,1]^n$ of fractional selection vectors, the diagonal level $ζ(P)=\max\{t\in[0,1]:t(1,\ldots,1)\in P\}$ is the largest selection probability that can be given to all elements at once; it equals $r/n$ for a uniform matroid of rank $r$, and $ζ(P)=1$ means that the constraint is vacuous. We give approximation coefficients that increase continuously with $ζ$. They come from one inequality for the multilinear extension of the objective: the algorithm computes an action without querying the objective, and objective feedback gives a comparator-independent update direction. For $k\ge3$, feasibility of the action reduces to three polynomial inequalities in one variable; for $k=2$ the profile is closed form. At $ζ=0$ the coefficients are $0.4456\ldots$ for $k=2$ and $0.4541\ldots$ for every $k\ge3$. For every finite $k\ge3$ they reach $1/2$ above an explicit level, which is $0.4026\ldots$ for $k=3,4,5$, and at $ζ=1$ they reach $1/2$ for $k=2$, $(\sqrt{17}-3)/2$ for $k=3,4$, and $k/(2k-1)$ for $k\ge5$. Online linear optimization gives $O(\sqrt T)$ approximate regret, with gradient feedback or with value queries made after each action. The coefficients carry over to matroids, with expected and high-probability guarantees, and to any fixed number of knapsacks: the zero-level coefficients hold on every instance, and the larger ones when items are small or when prefix enumeration keeps the diagonal level on one branch. For one budget the enumeration exponent is $O(1/\varepsilon)$.

0.38

Universal optimality on finite Lee tori

cs.IT math.CO ·2026-11-12 ·Tao Zhang
theory similarity 0.53
Abstract · 30 pages

We study subsets of finite Lee tori that minimize pair energy among sets of the same cardinality for every discretely completely monotone potential. At half occupancy on a product of even cycles, the two checkerboards minimize both total pair energy and maximum individual energy. They are the only minimizers for every nonconstant classical completely monotone potential on $(0,\infty)$, proving the checkerboard conjecture of Bouman, Draisma, and van Leeuwaarden for this class. At the independence number of the distance one graph on $\Z_q^n$, universally optimal sets exist exactly when $q$ is even, $q=3$, $n=1$, or $(q,n)=(5,2)$. In these cases they are precisely the maximum independent sets and form a single Lee isometry class. At density $1/5$ in $\Z_5^n$, $n\ge2$, universal optimality is characterized by a weighted count of pairs at distances one and two. We prove these results using integer box occupancy bounds that strengthen Fourier linear programming and, in the quinary case, Fourier certificates with a common zero set.

0.38

The Complexity of Recognizing SDP Exactness for the Maximum Cut Problem

cs.CC math.OC ·2026-09-03 ·Avinash Bhardwaj
similarity 0.53
Abstract

The standard semidefinite programming (SDP) relaxation of Max-Cut is exact when its optimum equals the maximum cut value. Delorme and Poljak resolved NP-completeness of recognizing exactness for weighted graphs and left the unweighted case open. We show that recognition is NP-complete even for connected simple unweighted graphs, and hence strongly NP-complete for nonnegative integer edge weights. The reduction provides an explicit SDP optimum and makes the additive integrality gap equal to the minimum number of unsatisfied clauses in the source formula. Recognition remains NP-complete even when an exact rational optimal primal--dual pair is supplied. We also establish strong NP-hardness of recognizing exactness of the Frieze--Jerrum Max-$k$-Cut relaxation for every fixed $k\ge3$, even for connected graphs with nonnegative integer edge weights. An independent bounded-weight construction gives a second proof for Max-Cut. Finally, reductions preserving the additive gap up to explicit factors establish strong NP-completeness of exactness recognition for a basic Max-DiCut SDP and NP-hardness for a Max-Bisection SDP.

0.33