Articles of discrete optimization

Why these two problems lead to same answers?

Suppose these two problems: Problem 1: $$\min_{X,P} \quad\max_{1\leq l\leq L-1} \quad {|\sum_{1\leq i\leq N_p}^{N_p}x_ie^{\frac{2\pi l}{N}p_i}| \over {\sum_{i=1}^{N_p} x_i^2}} \quad \equiv \quad \min_{X,P} \quad\max_{1\leq l\leq L-1} \quad {\sum_{1\leq i,j\leq N_p}^{N_p}x_ix_je^{\frac{2\pi l}{N}(p_i-p_j)} \over {(\sum_{i=1}^{N_p} x_i^2})^2} $$ Problem 2: $$\min_{P} \quad\max_{1\leq l\leq L-1} \quad |\sum_{1\leq i\leq N_p}^{N_p}e^{\frac{2\pi l}{N}p_i}| \quad \equiv \quad \min_{P} \quad\max_{1\leq l\leq L-1} \quad \sum_{1\leq i,j\leq […]

minimum lines, maximum points

There are $P$ points in the 2-dimensional plane. Through each point, we draw two orthogonal lines: one horizontal (parallel to x axis), one vertical (parallel to y axis). Obviously, some of these lines conicide. How can we arrange the points such as the total number of lines is minimized? I started with solving the dual […]

Discrete log for prime powers

I was fiddling around and found that a function of the form $$L_b (x)=\left(\frac{b^{\phi (p^k)}-1}{p^k}\right)^{-1}\left(\frac{x^{\phi (p^k)}-1}{p^k}\right) \mod p^k$$ seems to behave similarly to a discrete logarithm modulo $p^k$ (explained below), assuming $p \nmid x$, $p \nmid b$, and $p^{k+1} \nmid b^{\phi(p^k)}-1$. For example, if $p^k=9$ and $b=2$, then $L_2(2)=1, L_2(4)=2, L_2(8)=3$. However, there seems to […]

Is there an effective algorithm to solve this binary integer linear programming?

I am an applied math undergraduate student. On my project, I come across an integer linear programming question as follow: Given $x_0,x_1,…,x_n$: $\forall$ i $\in$ [0,n], $x_i$ = 0 or 1 min Z = $\sum_{i=0}^n x_i $ with m numbers of constraints in the format $\sum x_j \ge 1$: j $\in$ [0,n]. I know this […]

square cake with raisins

Alice bakes a square cake, with $n$ raisins (= points). Bob cuts $p$ square pieces. They are axis-aligned, interior-disjoint, and each piece must contain at least $2$ raisins. Note that a single raisin can be shared by two pieces (if it is on their boundary), or even four pieces (if it is on their corner). […]

Relations between the maximum matching, minimum vertex cover, maximum independent set, and maximum vertex biclique for a bipartite graph

From Wikipedia: König’s theorem states that, in bipartite graphs, the maximum matching is equal in size to the minimum vertex cover. Via this result, the minimum vertex cover, maximum independent set, and maximum vertex biclique problems may be solved in polynomial time for bipartite graphs. König’s theorem states about the relation between sizes of the […]

Combining kindergardeners in 'fair' cookie-baking groups. Kirkman's schoolgirl problem extended version

I am coordinating cookie-baking events with kindergarten kids. This turns out to be a challenging problem, and I could use a little help: We would like a general way of creating ‘fair’ cookie-baking teams for kindergarten pupils. By ‘fair’ I mean the following: A class consisting of N children (usually in the range 18 to […]