11

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-935.
The existence result of that paper is actually a special case of the earlier, even up to the basic proof approach (via Tarski's fixed point theorem).
...

answered Apr 19 '17 at 21:14

Michael Greinecker

10.5k33 gold badges4747 silver badges7070 bronze badges

11

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 maximum cardinality of a $q-$ary code with length $n$ and minimum distance $d.$
You can never have more than 2 codewords at full distance by binary geometry. In ...

11

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 $\sum (a_i-x b_i)$ for a given $x$ is the one defined by the $M$ lines from this arrangement that have the highest crossings with a vertical line through $x$. (...

answered Jan 17 '20 at 2:22

David Eppstein

17.9k22 gold badges4949 silver badges117117 bronze badges

9

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 that edge is $\log \tfrac{p_i + p_j}{2 \sqrt{p_i p_j}}$. We want the longest path from $1$ to $n$.
There are a number of standard efficient algorithms for ...

answered Apr 3 '18 at 13:39

David E Speyer

130k1111 gold badges339339 silver badges644644 bronze badges

9

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 the $p^3$ general position planes, with $p^2$ planes through each point. There are no 3 collinear points if the surface is chosen appropriately, so for any 3 ...

co.combinatorics oc.optimization-and-control combinatorial-optimization infinite-combinatorics hypergraph

8

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,b)\in\{(0,0),(1,1),(1,0),(0,1)\}$.
Our first task will be to eliminate any $(1,0)$ or $(0,1)$ options. For that,
use the Hadamard matrix without the ...

8

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 up to the eigenvalues of $B=J+xA_G$.
Note that the spectrum of $J$ is $\{0^{n-1}, n^1\}$, and that the eigenvalue $n$ corresponds to the eigenvector $(1,...,1)$. ...

7

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,A_2,…,A_m$ corresponds to a $m$-coloring of $G$.
The graph $G$ has degree no more than $6{n\choose 2}$, so $G$ can be colored in no more than $6{n\choose 2}+1$ ...

7

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 your graph is bipartite, the problem is infeasible when the number of nodes is odd. For $n\in\{2,4,6,8\}$, the optimal objective values are $0, 4, 8, 8$, so your ...

7

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
\begin{eqnarray*}
\|x\|_{a,b} & = & \|x_1a+x_2b\|_1 \\
& \ge & \|x_1a+x_2b\|_2=\sqrt{x_1^2+x_2^2}=\|x\|_2 \\
& \ge & \frac{1}{\sqrt{2}}\|x\|...

fa.functional-analysis linear-algebra inequalities nonlinear-optimization combinatorial-optimization

7

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 = (V, E)$ be a simple graph. For $B$ a subset of the vertex set $V$ , we define the spread of $B$ as
$$\mathrm{sp}(B) = \Big\{\max[\mathrm{deg}(u)]−
\min[\mathrm{...

7

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 Karpinski showed that it is NP-hard to approximate TSP within a factor of $\frac{741}{740} - \epsilon$, for any $\epsilon > 0$.

graph-theory mg.metric-geometry computational-complexity combinatorial-optimization approximation-algorithms

6

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 distributed on a set of $k$ elements where $k \equiv 2^n \mod p$ and $k \lt p$. At each step, we flip the coin and produce a random element in a set of size $2k \equiv ...

6

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 of first collecting the boxes, try the following zig-zag algorithm: start from the origin and poll the up and right nearest lattice points. One of them is closer ...

nt.number-theory diophantine-approximation global-optimization cryptography combinatorial-optimization

6

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:
$\bullet$ every member of that family $\mathcal{A}$ has 3 elements;
$\bullet$ all sets in $\mathcal{A}$ are pairwise disjunct.
Let $|\mathcal{A}| =a$ and let $A= \...

6

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 the 5-cycle gave the worst approximation ratio).
Graphs for which the Max-Cut value and the SDP relaxation coincided were called 'exact'. As Dima says, there ...

6

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(1 + 2\sqrt{2} + \sqrt{3}) = 88.9676+$ while changing
the $z=+1$ vertices to $(\pm\sqrt2, 0, 1)$ and $(0,\pm\sqrt2,1)$ gives
$16\bigl(\!\sqrt{8+\sqrt{8}} + \...

mg.metric-geometry inequalities convex-optimization combinatorial-optimization real-algebraic-geometry

answered Nov 22 '20 at 5:02

Noam D. Elkies

68.9k1212 gold badges245245 silver badges330330 bronze badges

6

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 distinct elements from $\{1,\dots,m\}$, and a fixed triple $(i,j,k)$, the probability that $\{x_1, \dots, x_a\} \subseteq A_i \cap A_j \cap A_k$ is at most $\left(\...

co.combinatorics oc.optimization-and-control combinatorial-optimization infinite-combinatorics hypergraph

5

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 some complicated polytope like the traveling salesman polytope, one wants to know if it is the projection of a much simpler polytope in slightly higher dimension. ...

5

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$, and that it is never higher than $94^n$. See:
On the Number of Crossing‐Free Matchings, Cycles, and Partitions.
Micha Sharir and Emo Welzl.
SIAM J. Comput. 36(...

answered Aug 20 '17 at 19:12

David Eppstein

17.9k22 gold badges4949 silver badges117117 bronze badges

5

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 polygon $P$ on $1 + n + 2t$ vertices $C_0$, $C_1$, $\ldots$, $C_n$, $D_1$, $\ldots$, $D_t$, $E_1$, $\ldots$, $E_t$. Choose vertices $V_1$, $\ldots$, $V_n$ on sides $...

5

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 0$ for all $0\leqslant i\leqslant i+2s\leqslant N-1$, then there exist non-negative numbers $p_0,\dots,p_{N}$ such that $q_i=p_i+p_{i+1}$ for $i=0,\dots,N-1$.
...

answered Nov 17 '17 at 23:40

Fedor Petrov

80.9k77 gold badges187187 silver badges340340 bronze badges

5

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 is what Fekete calls $\text{Min-Area}$.
He also proves $\text{Max-Area}$ is NP-complete, and addresses
higher-dimensional variations.
&...

answered Apr 16 '19 at 23:37

Joseph O'Rourke

140k2626 gold badges295295 silver badges834834 bronze badges

5

It is convenient to consider the vertex set of $B_h$ as a partially ordered set with its natural genealogic order, with minimum element its root. Any subtree $T'$ as described in your procedure (also including the empty tree) is then exactly an initial segment. (For the notation: $B_1$ is the one-vertex tree, and so on)
Removing $T'$ from $B_h$ leaves a ...

5

For $n\in\mathbb N$ and $s,t\in\mathbb R$ with $0\lt t\le s\le n$, let $F(n,s,t)$ be the greatest integer $m$ such that any family of $n$ numbers $a_1,\dots,a_n\in[0,1]$ with $a_1+\cdots+a_n=s$ can be partitioned into $m$ subfamilies, each with sum $\ge t$.
Lemma 1. If $k\in\mathbb N$ and $s\le k\le n$, then $F(n,s,t)\le\left\lfloor\frac k{\lceil kt/s\rceil}...

5

I will guess that the optimum occurs for $k$ isolated vertices and a complete graph on the other $n-k$ where $k=\lfloor\frac{n+1}5\rfloor.$ The same count occurs for $k$ vertices of degree $n-1$ and no other edges so the other $n-k$ have degree $k.$
Past that I have these observations:
A graph $G$ and the complement $\bar G$ give the same value to the sum.
...

4

Note: The question can be rephrased as follows: Two players $A$ and $B$ play a game on a graph. $A$ cuts the graph into two connected components, and $B$ chooses one component of the resulting graph. $A$ wants to maximize and $B$ wants to minimize the edge connectivity of the result. The bounds are the question: What would $A$ or $B$ say if they were to pick ...

4

General references on polytopes are:
Ziegler: Lecture on Polytopes (already mentioned by Joseph O'Rourke in a comment)
Grünbaum: Convex Polytopes
Thomas: Lectures in Geometric Combinatorics
Bronsted: An introduction to convex polytopes
Matousek: Lectures on Discrete Geometry, Chapter 5
Barvinok: A Course in Convexity, Chapter VI
A interesting survey about ...

4

Short answer: with negative $b_i$'s, it's NP-hard, but otherwise it's polynomial time.
If you allow negative $b_i$ then it is hard (set all the $a_i=1$, so the goal is to get the chosen subset of $b_i$'s to sum to a number close to but greater than $-1$ in order to make the denominator as small as possible — this is a subset sum problem.
If the $a_i$'s and ...

answered Dec 16 '15 at 8:44

David Eppstein

17.9k22 gold badges4949 silver badges117117 bronze badges

4

According to graphclasses 3-Colourability of 4-regular ∩ planar is NP-hard. Check "+details" for reference.

co.combinatorics graph-theory computational-complexity discrete-mathematics combinatorial-optimization

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

#### Related Tags

combinatorial-optimization × 333co.combinatorics × 131

graph-theory × 94

oc.optimization-and-control × 48

algorithms × 44

computational-complexity × 33

linear-programming × 27

reference-request × 23

mg.metric-geometry × 23

linear-algebra × 21

discrete-geometry × 21

nonlinear-optimization × 19

integer-programming × 19

convex-optimization × 18

pr.probability × 17

inequalities × 15

matrices × 14

approximation-algorithms × 11

heuristics × 11

traveling-salesman-problem × 11

global-optimization × 10

graph-colorings × 9

real-analysis × 8

extremal-graph-theory × 8

probability-distributions × 7