Source author record

Antoine Deza

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.OC Computational Geometry math.MG Discrete Mathematics Computational Engineering, Finance, and Science math.NT

Catalog footprint

Research overview

11works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Flat simplices and kissing polytopes

We consider how flat a lattice simplex contained in the hypercube $[0,k]^d$ can be. This question is related to the notion of kissing polytopes: two lattice polytopes contained in the hypercube $[0,k]^d$ are kissing when they are disjoint but their distance is as small as possible. We show that the smallest possible distance of a lattice point $P$ contained in the cube $[0,k]^3$ to a lattice triangle in the same cube that does not contain $P$ is $\frac{1}{\sqrt{3k^4-4k^3+4k^2-2k+1}}$ when $k$ is at least $2$ . We also improve the known lower bounds on the distance of kissing polytopes for $d$ at least $4$ and $k$ at least $2$ .

preprint2021arXiv

Polytopal balls arising in optimization

We study a family of polytopes and their duals, that appear in various optimization problems as the unit balls for certain norms. These two families interpolate between the hypercube, the unit ball for the $\infty$ -norm, and its dual cross-polytope, the unit ball for the $1$ -norm. We give combinatorial and geometric properties of both families of polytopes such as their $f$ -vector, their volume, and the volume of their boundary.

preprint2020arXiv

Primitive point packing

A point in the $d$ -dimensional integer lattice $\mathbb{Z}^d$ is primitive when its coordinates are relatively prime. Two primitive points are multiples of one another when they are opposite, and for this reason, we consider half of the primitive points within the lattice, the ones whose first non-zero coordinate is positive. We solve the packing problem that asks for the largest possible number of such points whose absolute values of any given coordinate sum to at most a fixed integer $k$ . We present several consequences of this result at the intersection of geometry, number theory, and combinatorics. In particular, we obtain an explicit expression for the largest possible diameter of a lattice zonotope contained in the hypercube $[0,k]^d$ and, conjecturally of any lattice polytope in that hypercube.

preprint2019arXiv

The diameter of lattice zonotopes

We establish sharp asymptotic estimates for the diameter of primitive zonotopes when their dimension is fixed. We also prove that, for infinitely many integers $k$ , the largest possible diameter of a lattice zonotope contained in the hypercube $[0,k]^d$ is uniquely achieved by a primitive zonotope. As a consequence, we obtain that this largest diameter grows like $k^{d/(d+1)}$ up to an explicit multiplicative constant, when $d$ is fixed and $k$ goes to infinity, providing a new lower bound on the largest possible diameter of a lattice polytope contained in $[0,k]^d$ .

preprint2015arXiv

Imperfect demand estimation for new product production planning

We are interested in the effect of consumer demand estimation error for new products in the context of production planning. An inventory model is proposed, whereby demand is influenced by price and advertising. The effect of parameter misspecification of the demand model is empirically examined in relation to profit and service level feasibility. Faced with an uncertain consumer reaction to price and advertising, we find that it is safer to overestimate rather than underestimate the effect of price on demand. Moreover, under a service level constraint it is safer to overestimate the effect of advertising, whereas for strict profit maximization, underestimating the effect of advertising is the conservative approach.

preprint2014arXiv

A further generalization of the colourful Carathéodory theorem

Given $d+1$ sets, or colours, $S_1, S_2,...,S_{d+1}$ of points in $\mathbb{R}^d$ , a {\em colourful} set is a set $S\subseteq\bigcup_i S_i$ such that $|S\cap S_i|\leq 1$ for $i=1,...,d+1$ . The convex hull of a colourful set $S$ is called a {\em colourful simplex}. Bárány's colourful Carathéodory theorem asserts that if the origin 0 is contained in the convex hull of $S_i$ for $i=1,...,d+1$ , then there exists a colourful simplex containing 0. The sufficient condition for the existence of a colourful simplex containing 0 was generalized to 0 being contained in the convex hull of $S_i\cup S_j$ for $1\leq i< j \leq d+1$ by Arocha et al. and by Holmsen et al. We further generalize the sufficient condition and obtain new colourful Carathéodory theorems. We also give an algorithm to find a colourful simplex containing 0 under the generalized condition. In the plane an alternative, and more general, proof using graphs is given. In addition, we observe that any condition implying the existence of a colourful simplex containing 0 actually implies the existence of $\min_i|S_i|$ such simplices.

preprint2014arXiv

A primal-simplex based Tardos' algorithm

In the mid-eighties Tardos proposed a strongly polynomial algorithm for solving linear programming problems for which the size of the coefficient matrix is polynomially bounded by the dimension. Combining Orlin's primal-based modification and Mizuno's use of the simplex method, we introduce a modification of Tardos' algorithm considering only the primal problem and using simplex method to solve the auxiliary problems. The proposed algorithm is strongly polynomial if the coefficient matrix is totally unimodular and the auxiliary problems are non-degenerate.

preprint2014arXiv

Chance Constrained Optimization for Targeted Internet Advertising

We introduce a chance constrained optimization model for the fulfillment of guaranteed display Internet advertising campaigns. The proposed formulation for the allocation of display inventory takes into account the uncertainty of the supply of Internet viewers. We discuss and present theoretical and computational features of the model via Monte Carlo sampling and convex approximations. Theoretical upper and lower bounds are presented along with a numerical substantiation.

preprint2014arXiv

How many double squares can a string contain?

Counting the types of squares rather than their occurrences, we consider the problem of bounding the number of distinct squares in a string. Fraenkel and Simpson showed in 1998 that a string of length n contains at most 2n distinct squares. Ilie presented in 2007 an asymptotic upper bound of 2n - Theta(log n). We show that a string of length n contains at most 5n/3 distinct squares. This new upper bound is obtained by investigating the combinatorial structure of double squares and showing that a string of length n contains at most 2n/3 double squares. In addition, the established structural properties provide a novel proof of Fraenkel and Simpson's result.

preprint2013arXiv

A combinatorial approach to colourful simplicial depth

The colourful simplicial depth conjecture states that any point in the convex hull of each of d+1 sets, or colours, of d+1 points in general position in R^d is contained in at least d^2+1 simplices with one vertex from each set. We verify the conjecture in dimension 4 and strengthen the known lower bounds in higher dimensions. These results are obtained using a combinatorial generalization of colourful point configurations called octahedral systems. We present properties of octahedral systems generalizing earlier results on colourful point configurations and exhibit an octahedral system which can not arise from a colourful point configuration. The number of octahedral systems is also given.

preprint2012arXiv

Computational Lower Bounds for Colourful Simplicial Depth

The colourful simplicial depth problem in dimension d is to find a configuration of (d+1) sets of (d+1) points such that the origin is contained in the convex hull of each set (colour) but contained in a minimal number of colourful simplices generated by taking one point from each set. A construction attaining d^2+1 simplices is known, and is conjectured to be minimal. This has been confirmed up to d=3, however the best known lower bound for d at least 4 is ((d+1)^2)/2. A promising method to improve this lower bound is to look at combinatorial octahedral systems generated by such configurations. The difficulty to employing this approach is handling the many symmetric configurations that arise. We propose a table of invariants which exclude many of partial configurations, and use this to improve the lower bound in dimension 4.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Antoine Deza

Research overview

Is this your work?

11 publications

Flat simplices and kissing polytopes

Polytopal balls arising in optimization

Primitive point packing

The diameter of lattice zonotopes

Imperfect demand estimation for new product production planning

A further generalization of the colourful Carathéodory theorem

A primal-simplex based Tardos' algorithm

Chance Constrained Optimization for Targeted Internet Advertising

How many double squares can a string contain?

A combinatorial approach to colourful simplicial depth

Computational Lower Bounds for Colourful Simplicial Depth

See the researcher in context

Building this map preview