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.
...

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\},\{...

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-...

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 ...

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 $\...

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 ...

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 ...

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,
...

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,...

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 ...

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 ...

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,...

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 ...

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
\...

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 = ...

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 ...

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 ...

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 ...

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 ...

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:
$\...

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 ...

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(...

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 ...

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 $...

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 ...

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 ...

Community wiki

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$, ...

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 ...

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 ...

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 ...

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

#### Related Tags

combinatorial-optimization × 374co.combinatorics × 144

graph-theory × 102

algorithms × 53

oc.optimization-and-control × 48

computational-complexity × 35

linear-programming × 30

mg.metric-geometry × 28

reference-request × 26

integer-programming × 26

discrete-geometry × 25

linear-algebra × 24

pr.probability × 18

convex-optimization × 18

nonlinear-optimization × 18

approximation-algorithms × 17

matrices × 15

inequalities × 14

traveling-salesman-problem × 12

global-optimization × 11

extremal-graph-theory × 11

graph-colorings × 9

np × 9

heuristics × 9

probability-distributions × 8