On January 14, 2025, Tony Huynh from the Sapienza Università di Roma gave a talk on the peaceable queens problem on the toroidal board at the Discrete Math Seminar. The title of his talk was “The Peaceable Queens Problem“.
The peaceable queens problem asks to determine the maximum number $a(n)$ such that there is a placement of $a(n)$ white queens and $a(n)$ black queens on an $n \times n$ chessboard so that no queen can capture any queen of the opposite color.
We consider the peaceable queens problem and its variant on the toroidal board. For the regular board, we show that $a(n) \leq 0.1716n^2$, for all sufficiently large $n$. This improves on the bound $a(n) \leq 0.25n^2$ of van Bommel and MacEachern.
For the toroidal board, we provide new upper and lower bounds. Somewhat surprisingly, our bounds show that there is a sharp contrast in behaviour between the odd torus and the even torus. Our lower bounds are given by explicit constructions. For the upper bounds, we formulate the problem as a non-linear optimization problem with at most 100 variables, regardless of the size of the board. We solve our non-linear program exactly using modern optimization software.
We also provide a local search algorithm and a software implementation which converges very rapidly to solutions which appear optimal. Our algorithm is sufficiently robust that it works on both the regular and toroidal boards. For example, for the regular board, the algorithm quickly finds the so-called Ainley construction.
This is joint work with Katie Clinch, Matthew Drescher, and Abdallah Saffidine.
In 2017, Aharoni proposed the following generalization of the Caccetta-Häggkvist conjecture for digraphs. If G is a simple n-vertex edge-colored graph with n color classes of size at least r, then G contains a rainbow cycle of length at most ⌈n/r⌉.
In this talk, we prove that Aharoni’s conjecture holds up to an additive constant. Specifically, we show that for each fixed r, there exists a constant c such that if G is a simple n-vertex edge-colored graph with n color classes of size at least r, then G contains a rainbow cycle of length at most n/r+c.
Combinatorial and Discrete Optimization I: November 8, 2019 Friday, 14:20 – 15:40.
Kangbok Lee
Kedong Yan
Dabeen Lee
Se-young Yun
Combinatorial and Discrete Optimization II: November 9, 2019 Saturday, 10:00 – 11:20.
Hyung Chan An
Dong Yeap Kang
Tony Huynh
Sang-il Oum
Abstracts
Kangbok Lee (이강복), Bi-criteria scheduling
The bi-criteria scheduling problems that minimize the two most popular scheduling objectives, namely the makespan and the total completion time, are considered. Given a schedule, makespan, denoted as $C_\max$, is the latest completion time of the jobs and the total completion time, denoted as $\sum C_j$, is the sum of the completion times of the jobs. These two objectives have received a lot of attention in the literature because of their practical implications. Scheduling problems are somehow difficult to solve even for single criterion. On the other hand, when it comes to a bi-criteria problem, a balanced solution coordinating both objectives is indeed essential. In this paper, we consider bi-criteria scheduling problems on $m$ identical parallel machines where $m$ is 2, 3 and an arbitrary number, denoted as $P2 || (C_\max,\sum C_j)$, $P3 || (C_\max,\sum C_j)$ and $P || (C_\max,C_j)$, respectively. For each problem, we explore its inapproximability and develop an approximation algorithm with analysis of its worst performance.
Kedong Yan, Cliques for multi-term linearization of 0-1 multilinear program for boolean logical pattern generation
Logical Analysis of Data (LAD) is a combinatorial optimization-based machine learning method. A key stage of LAD is pattern generation, where useful knowledge in a training dataset of two types of, say, + and − data under analysis is discovered. LAD pattern generation can be cast as a 0-1 multilinear program (MP) with a single 0-1 multilinear constraint: $$(PG): \max\limits_{x\in\{0,1\}^{2n}}f(x):=\sum_{i\in S^+}\Pi_{j\in J_i}(1-x_j)~~\text{subject to}~~g(x):=\sum_{i\in S^-}\Pi_{j\in J_i}(1-x_j)=0$$
The unconstrained maximization of $f$ (without $g$) is straightforward, thus the main difficulty of globally maximizing $(PG)$ arises primarily from the presence of g and the interaction between $f$ and $g$. We dealt with the task of linearizing $g$. Namely, we employed a graph theoretic analysis of data to discover sufficient conditions among neighboring data and also neighboring groups of data for ‘compactly linearizing’ $g$ in terms of a small number of stronger valid inequalities, as compared to those that can be obtained via 0-1 linearization techniques from the literature. In an earlier work, we analyzed + and − data (that is, terms of $f$ and $g$ together) on a graph to develop a polyhedral overestimation scheme for $f$. Extending this line of research, this paper proposes a new graph representation of monomials in f in conjunction with terms in $g$ to more aggressively aggregate a set of terms/data through each maximal clique in the graph into yielding a stronger valid inequality. This is achieved by means of a new notion of ‘neighbors’ that allows us to join two data that are more than 1-Hamming distance away from each other by an edge in the graph. We show that new inequalities generalize and subsume those from the earlier paper. Furthermore, with using six benchmark data mining datasets, we demonstrate that new inequalities are superior to their predecessors in terms of a more efficient global maximization of $(PG)$; that is, for a more efficient analysis and classification of real-life datasets.
Dabeen Lee (이다빈), Joint Chance-constrained programs and the intersection of mixing sets through a submodularity lens
The intersection of mixing sets with common binary variables arise when modeling joint linear chance-constrained programs with random right-hand sides and finite sample space. In this talk, we first establish a strong and previously unrecognized connection of mixing sets to submodularity. This viewpoint enables us to unify and extend existing results on polyhedral structures of mixing sets. Then we study the intersection of mixing sets with common binary variables and also linking constraint lower bounding a linear function of the continuous variables. We propose a new class of valid inequalities and characterize when this new class along with the mixing inequalities are sufficient to describe the convex hull.
Se-Young Yun (윤세영), Optimal sampling and clustering algorithms in the stochastic block model
This paper investigates the design of joint adaptive sampling and clustering algorithms in the Stochastic Block Model (SBM). To extract hidden clusters from the data, such algorithms sample edges sequentially in an adaptive manner, and after gathering edge samples, return cluster estimates. We derive information-theoretical upper bounds on the cluster recovery rate. These bounds reveal the optimal sequential edge sampling strategy, and interestingly, the latter does not depend on the sampling budget, but only the parameters of the SBM. We devise a joint sampling and clustering algorithm matching the recovery rate upper bounds. The algorithm initially uses a fraction of the sampling budget to estimate the SBM parameters, and to learn the optimal sampling strategy. This strategy then guides the remaining sampling process, which confers the optimality of the algorithm.
Hyung-Chan An (안형찬), Constant-factor approximation algorithms for parity-constrained facility location problems
Facility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest, little is known on how the problem behaves in conjunction with parity constraints. This shortfall of understanding was rather disturbing when we consider the central role of parity in the field of combinatorics. In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of facilities and clients, the opening cost of each facility, and the parity requirement—$\mathsf{odd}$, $\mathsf{even}$, or $\mathsf{unconstrained}$—of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement. Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a $T$-join on an auxiliary graph constructed by the algorithm. This graph does not satisfy the triangle inequality, but we show that a carefully chosen set of shortcutting operations leads to a cheap and sparse $T$-join. Finally, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound. At the end of this paper, we also present the first constant-factor approximation algorithm for the parity-constrained $k$-center problem, the bottleneck optimization variant.
Dong Yeap Kang (강동엽), On minimal highly connected spanning subgraphs in dense digraphs
In 1985, Mader showed that every $n(\geq4k+3)$-vertex strongly $k$-connected digraph contains a spanning strongly $k$-connected subgraph with at most $2kn-2k^2$ edges, and the only extremal digraph is a complete bipartite digraph $DK_{k,n−k}$. Nevertheless, since the extremal graph is sparse, Bang-Jensen asked whether there exists g(k) such that every strongly $k$-connected $n$-vertex tournament contains a spanning strongly $k$-connected subgraph with $kn + g(k)$ edges, which is an “almost $k$-regular” subgraph.
Recently, the question of Bang-Jensen was answered in the affirmative with $g(k) = O(k^2\log k)$, which is best possible up to logarithmic factor. In this talk, we discuss how to find minimal highly connected spanning subgraphs in dense digraphs as well as tournaments. In particular, we show that every highly connected dense digraph contains a spanning highly connected subgraph that is almost $k$-regular, which yields $g(k) = O(k^2)$ that is best possible for tournaments.
Tony Huynh, Stable sets in graphs with bounded odd cycle packing number
It is a classic result that the maximum weight stable set problem is efficiently solvable for bipartite graphs. The recent bimodular algorithm of Artmann, Weismantel and Zenklusen shows that it is also efficiently solvable for graphs without two disjoint odd cycles. The complexity of the stable set problem for graphs without $k$ disjoint odd cycles is a long-standing open problem for all other values of $k$. We prove that under the additional assumption that the input graph is embedded in a surface of bounded genus, there is a polynomial-time algorithm for each fixed $k$. Moreover, we obtain polynomial-size extended formulations for the respective stable set polytopes. To this end, we show that 2-sided odd cycles satisfy the Erdos-Posa property in graphs embedded in a fixed surface. This result may be of independent interest and extends a theorem of Kawarabayashi and Nakamoto asserting that odd cycles satisfy the Erdos-Posa property in graphs embedded in a fixed orientable surface Eventually, our findings allow us to reduce the original problem to the problem of finding a minimum-cost non-negative integer circulation of a certain homology class, which we prove to be efficiently solvable in our case.
Sang-il Oum, Rank-width: Algorithmic and structural results
Rank-width is a width parameter of graphs describing whether it is possible to decompose a graph into a tree-like structure by ‘simple’ cuts. This talk aims to survey known algorithmic and structural results on rank-width of graphs. This talk is based on a survey paper with further remarks on the recent developments.
It is a classic result that the maximum weight stable set problem is efficiently solvable for bipartite graphs. The recent bimodular algorithm of Artmann, Weismantel and Zenklusen shows that it is also efficiently solvable for graphs without two disjoint odd cycles. The complexity of the stable set problem for graphs without $k$ disjoint odd cycles is a long-standing open problem for all other values of $k$. We prove that under the additional assumption that the input graph is embedded in a surface of bounded genus, there is a polynomial-time algorithm for each fixed $k$. Moreover, we obtain polynomial-size extended formulations for the respective stable set polytopes.
To this end, we show that 2-sided odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed surface. This result may be of independent interest and extends a theorem of Kawarabayashi and Nakamoto asserting that odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed orientable surface.
Eventually, our findings allow us to reduce the original problem to the problem of finding a minimum-cost non-negative integer circulation of a certain homology class, which we prove to be efficiently solvable in our case.
This is joint work with Michele Conforti, Samuel Fiorini, Gwenaël Joret, and Stefan Weltge.
Tony Huynh from Université libre de Bruxelles became the first person to give a talk at discrete math seminar at DIMAG on December 10, 2018. He talked about his recent work “A tight Erdős-Pósa function for planar minors” (SODA’19).
Let H be a planar graph. By a classical result of Robertson and Seymour, there is a function f(k) such that for all k and all graphs G, either G contains k vertex-disjoint subgraphs each containing H as a minor, or there is a subset X of at most f(k) vertices such that G−X has no H-minor. We prove that this remains true with f(k)=ck log k for some constant c depending on H. This bound is best possible, up to the value of c, and improves upon a recent bound of Chekuri and Chuzhoy. The proof is constructive and yields the first polynomial-time O(log 𝖮𝖯𝖳)-approximation algorithm for packing subgraphs containing an H-minor.
This is joint work with Wouter Cames van Batenburg, Gwenaël Joret, and Jean-Florent Raymond.
