19 votes
Accepted

Splitting the integers from $1$ to $2n$ into two sets with products as close as possible

Original question Is this sequence strictly increasing? No. ...
user avatar
  • 4,627
14 votes

Splitting the integers from $1$ to $2n$ into two sets with products as close as possible

Here are optimal solutions for $n \le 10$, and the two sets happen to be equicardinal even if you don't enforce that: \begin{matrix} n & a_n & \text{solution} \\ \hline 1 & 1 & \{2\},\{...
user avatar
  • 3,820
11 votes
Accepted

Stable marriage with contracts: is it known?

There is a humongous literature on "matching with contracts", starting with: Hatfield, John William, and Paul R. Milgrom. "Matching with contracts." The American Economic Review 95.4 (2005): 913-...
user avatar
11 votes
Accepted

Spreading $n$ points in $\{0,1\}^n$ as far as possible

If I understood the question correctly, what you're asking is related to the maximum distance of binary codes with large minimum distance $d\geq s$. In coding theory, $A_q(n,d)$ is defined as the ...
user avatar
  • 8,721
11 votes

Optimization algorithm sought

It is equivalent to look for the largest positive value $x$ such that, for some $M$-subset, $\sum (a_i-x b_i)\ge 0$. Plot the $n$ lines $y = a_i - x b_i$ in the plane. The $M$-subset that maximizes $\...
user avatar
9 votes

Optimal Talmudic Zigzag

This is a special case of finding the longest path in a directed acyclic graph. Namely, the vertices of our graph are $1$, $2$, ..., $n$, there is an edge $i \to j$ for each $i<j$ and the length of ...
user avatar
9 votes

n sets, each is large, the intersection of every three is small, what is the size of the union?

It can be $O(n^{\frac32})$ for $a\ge 1$ if the sets $A_i$ correspond to the $p^2$ points of a smooth surface in an appropriate surface in a 3-dimensional space over $\mathbb F_p$ and your points are ...
user avatar
  • 17.3k
9 votes

Splitting the integers from $1$ to $2n$ into two sets with products as close as possible

$\newcommand{\sub}[1]{_{\substack{m\in[1,2n] \\ #1}}}$ $\newcommand{\td}{{\widetilde d}}$ $\renewcommand{\cP}{{\mathcal P}}$ For the growth rate, we have the upper bound $a_n\le 2^nn!$ and, ...
user avatar
  • 21.8k
8 votes
Accepted

NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix

Here is a simple embedding of 3-SAT into the current setup (the question is just if we can get all vectors good). Call the first column special with $1$'s. Split the other variables into pairs $(a,...
user avatar
  • 53k
8 votes
Accepted

Eigenvalues of adjacency matrix of a k-regular graph

If $G$ is regular, then $J$ and $A_G$ are simultaneously diagonalizable (i.e. they have a common set of eigenvectors). That is, the eigenvalues of $xA_G$ and $J$ (to the same eigenvectors) just add ...
user avatar
  • 10k
8 votes
Accepted

Smallest relation in complement of partial order that prohibits its extension

I claim that the relation $R$ is in fact unique. The uniqueness follows from the one pair extension property of finite partially ordered sets. Proposition: Suppose that $X$ is a finite set with ...
user avatar
7 votes
Accepted

What is the best way to partition the $4$-subsets of $\{1,2,3,\dots,n\}$?

This problem can be reformulated in terms of graph coloring: Let the graph $G=(V,E)$, $V=\mathcal A$, $(x,y)\in E \leftrightarrow x \cap y \geq 2$ Then a partition of $\mathcal{A}$ into groups $A_1,...
user avatar
  • 8,284
7 votes

Snake algorithm that minimizes straight lines

This problem is a special case of the quadratic traveling salesman problem in which the cost for traversing three consecutive nodes that have no turn is $1$ and the cost is $0$ otherwise. Because ...
user avatar
  • 3,820
7 votes
Accepted

On a certain norm of the identity operator on $\mathbb R^2$

Simply observe that $$\|x\|_{a,b}=\|x_1a+x_2b\|_1\,.$$ Thus, by orthogonality of $a,b$ and the easily-derived inequality $\|y\|_2\le\|y\|_1\le\sqrt{n}\|y\|_2$ for any $y\in\mathbb{R}^n$, we have \...
user avatar
  • 1,360
7 votes
Accepted

Pairs of vertices with high degree difference

I have just found out a very similar theorem to the one in the question. Some work still must be done, but it seems clear that it is very closely related. https://arxiv.org/pdf/1806.08303.pdf Let $G = ...
user avatar
7 votes

Metric TSP with integer edge cost

No polynomial-time algorithm exists, unless P=NP. Indeed, even for TSP instances where all distances are $1$ or $2$ (note that these automatically satisfy the triangle inequality), Engebretsen and ...
user avatar
  • 28.7k
7 votes
Accepted

Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment

You can solve this as a minimum-weight perfect matching problem in a graph with a node for each point and an edge for each pair of points. Because the distances satisfy the triangle inequality, an ...
user avatar
  • 3,820
6 votes
Accepted

"Most Similar Vector Problem" on an Integer Lattice?

Writing up the comment: You just need to "pixelate" the line by finding all lattice boxes that it crosses: Then the answer vector $v$ must connect to one of the corners of the shaded boxes. Instead ...
user avatar
  • 4,822
6 votes
Accepted

How to roll a $p$

Here is an optimal method that I think is equivalent to your greedy method. We start with a constant random variable, say $0$. Inductively, after $n$ steps we have a random element uniformly ...
user avatar
  • 27.5k
6 votes

Domination problem with sets

Clearly we can assume that each element in $M$ appears in exactly $4$ subsets. Let $|M| =n$. Stage 1. Take maximal subfamily $\mathcal{A} \subseteq \{S_1,....,S_k\} =:\mathcal{S} $ such that: $\...
user avatar
  • 237
6 votes

Exactness of the semidefinite programming (SDP) relaxation of maximum cut (Max-Cut)

This question was studied somewhat in the early '90s (before Goemans--Williamson, in fact; note that it was Delorme and Poljak who first gave a poly-time SDP algorithm for Max-Cut, conjecturing that ...
user avatar
6 votes
Accepted

Subsets of a ball/sphere with the largest sum of distances

Negative answers to some of those questions: Q1 Not always; for $n=8$ a square antiprism is better than a cube. For example, in radius $\sqrt 3$, the cube with vertices $(\pm 1, \pm1, \pm1)$ gives $16(...
user avatar
6 votes
Accepted

n sets, each is large, the intersection of every three is small, what is the size of the union?

Let $m$ be chosen later, and let $A_1, A_2, \dots, A_n$ be independently chosen random subsets of $\{1,2,\dots m\}$, each having size $n$. For a fixed $a+1$-tuple $(x_1, x_2, \dots, x_{a+1})$ of ...
user avatar
6 votes
Accepted

Graph combinatorial optimization problem

The answer is $k=n-2$. To see this, first note that $k \geq n-2$, since the complete graph on $n$ vertices minus an edge has the desired property for $k=n-3$. For the other inequality suppose that $...
user avatar
  • 28.7k
6 votes

What is the smallest size of a shape in which all fixed $n$-polyominos can fit?

It seems $S_n$ is $\geq\displaystyle\Theta\left(\frac{n^2}{\log(n)}\right)$. In the following, I will consider polyominos as subsets of $\mathbb{Z}^2$ (so, a polyomino is represented by the set of ...
user avatar
  • 3,442
5 votes

Can anyone suggest a text on polyhedral theory?

Reading between the lines of your comment about increasing the number of faces under projections, I'm guessing that you're interested in the subject known as "extension complexity." Starting with ...
5 votes
Accepted

Number Associated with Straight-line Drawings of Hamiltonian Graphs

It is known that the number of non-crossing spanning cycles (called "simple polygonalizations") of $n$ points in the plane can be as low as $1$ (for points in convex position) and as high as $4.64^n$, ...
user avatar
5 votes
Accepted

Is this problem of selecting points NP-hard?

This problem is reducible from VERTEX-COVER. A rough description: let the input graph to VERTEX-COVER be $G = (V, E)$ with $|V| = n$. Choose integer $n << t = O(n^c)$, and create a convex ...
user avatar
5 votes
Accepted

Diameter of a weighted Hamming cube

It looks like even the sharp upper estimate 1 may be obtained. We use the following Lemma. If $q_0,\dots,q_{N-1}$ are non-negative real numbers such that $q_i-q_{i+1}+q_{i+2}-\dots+q_{i+2s}\geqslant ...
user avatar
  • 89.5k
5 votes
Accepted

What is known about this TSP variant?

Indeed the problem is NP-complete: Fekete, Sándor P. "On simple polygonalizations with optimal area." Discrete & Computational Geometry 23, no. 1 (2000): 73-110. (Journal link.) Your problem ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible