Arrow Research search

Author name cluster

Jean Cardinal

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

14 papers
2 author rows

Possible papers

14

MFCS Conference 2025 Conference Paper

Hitting and Covering Affine Families of Convex Polyhedra, with Applications to Robust Optimization

  • Jean Cardinal
  • Xavier Goaoc
  • Sarah Wajsbrot

Geometric hitting set problems, in which we seek a smallest set of points that collectively hit a given set of ranges, are ubiquitous in computational geometry. Most often, the set is discrete and is given explicitly. We propose new variants of these problems, dealing with continuous families of convex polyhedra, and show that they capture decision versions of the two-level finite adaptability problem in robust optimization. We show that these problems can be solved in strongly polynomial time when the size of the hitting/covering set and the dimension of the polyhedra and the parameter space are constant. We also show that the hitting set problem can be solved in strongly quadratic time for one-parameter families of convex polyhedra in constant dimension. This leads to new tractability results for finite adaptability that are the first ones with so-called left-hand-side uncertainty, where the underlying problem is non-linear.

Details

SODA Conference 2023 Conference Paper

Zigzagging through acyclic orientations of chordal graphs and hypergraphs

  • Jean Cardinal
  • Hung Phuc Hoang
  • Arturo Merino
  • Torsten Mütze

In 1993, Savage, Squire, and West described an inductive construction for generating every acyclic orientation of a chordal graph exactly once, flipping one arc at a time. We provide two generalizations of this result. Firstly, we describe Gray codes for acyclic orientations of hypergraphs that satisfy a simple ordering condition, which generalizes the notion of perfect elimination order of graphs. This unifies the Savage-Squire-West construction with a recent algorithm for generating elimination trees of chordal graphs (SODA 2022). Secondly, we consider quotients of lattices of acyclic orientations of chordal graphs, and we provide a Gray code for them, addressing a question raised by Pilaud (FPSAC 2022). This also generalizes a recent algorithm for generating lattice congruences of the weak order on the symmetric group (SODA 2020). Our algorithms are derived from the Hartung-Hoang-Mutze-Williams combinatorial generation framework, and they yield simple algorithms for computing Hamilton paths and cycles on large classes of polytopes, including chordal nestohedra and quotientopes. In particular, we derive an efficient implementation of the Savage-Squire-West construction. Along the way, we give an overview of old and recent results about the polyhedral and order-theoretic aspects of acyclic orientations of graphs and hypergraphs. * Arturo Merino was supported by ANID Becas Chile 2019-72200522. Torsten Mütze was supported by Czech Science Foundation grant GA 22-15272S. Arturo Merino and Torsten Mütze were also supported by German Science Foundation grant 413902284.

Details

SODA Conference 2022 Conference Paper

Efficient generation of elimination trees and graph associahedra

  • Jean Cardinal
  • Arturo Merino
  • Torsten Mütze

An elimination tree for a connected graph G is a rooted tree on the vertices of G obtained by choosing a root x and recursing on the connected components of G – x to produce the subtrees of x. Elimination trees appear in many guises in computer science and discrete mathematics, and they encode many interesting combinatorial objects, such as bitstrings, permutations and binary trees. We apply the recent Hartung-Hoang-Mütze-Williams combinatorial generation framework to elimination trees, and prove that all elimination trees for a chordal graph G can be generated by tree rotations using a simple greedy algorithm. This yields a short proof for the existence of Hamilton paths on graph associahedra of chordal graphs. Graph associahedra are a general class of high-dimensional polytopes introduced by Carr, Devadoss, and Postnikov, whose vertices correspond to elimination trees and whose edges correspond to tree rotations. As special cases of our results, we recover several classical Gray codes for bitstrings, permutations and binary trees, and we obtain a new Gray code for partial permutations. Our algorithm for generating all elimination trees for a chordal graph G can be implemented in time (m + n ) per generated elimination tree, where m and n are the number of edges and vertices of G, respectively. If G is a tree, we improve this to a loopless algorithm running in time (1) per generated elimination tree. We also prove that our algorithm produces a Hamilton cycle on the graph associahedron of G, rather than just Hamilton path, if the graph G is chordal and 2-connected. Moreover, our algorithm characterizes chordality, i. e. , it computes a Hamilton path on the graph associahedron of G if and only if G is chordal.

Details

SODA Conference 2020 Conference Paper

Competitive Online Search Trees on Trees

  • Prosenjit Bose
  • Jean Cardinal
  • John Iacono
  • Grigorios Koumoutsos
  • Stefan Langerman

We consider the design of adaptive data structures for searching elements of a tree-structured space. We use a natural generalization of the rotation-based online binary search tree model in which the underlying search space is the set of vertices of a tree. This model is based on a simple structure for decomposing graphs, previously known under several names including elimination trees, vertex rankings, and tubings. The model is equivalent to the classical binary search tree model exactly when the underlying tree is a path. We describe an online O (log log n )-competitive search tree data structure in this model, matching the best known competitive ratio of binary search trees. Our method is inspired by Tango trees, an online binary search tree algorithm, but critically needs several new notions including one which we call Steiner-closed search trees, which may be of independent interest. Moreover our technique is based on a novel use of two levels of decomposition, first from search space to a set of Steiner-closed trees, and secondly from these trees into paths.

Details

SODA Conference 2009 Conference Paper

Decomposition of multiple coverings into more parts

  • Greg Aloupis
  • Jean Cardinal
  • Sébastien Collette
  • Stefan Langerman
  • David Orden
  • Pedro Ramos 0001

We prove that for every centrally symmetric convex polygon Q, there exists a constant α such that any αk -fold covering of the plane by translates of Q can be decomposed into k coverings. This improves on a quadratic upper bound proved by Pach and Tóth (SoCG'07). The question is motivated by a sensor network problem, in which a region has to be monitored by sensors with limited battery life.

Details