3
votes
2answers
169 views

Generalized Moore Graphs

A generalized Moore graph - as defined by Cerf, Cowan, Mullin and Stanton - is one for which the girth G and diameter D satisfy G ≥ 2D - 1. These graphs retain many of the optimal properties of Moore ...
1
vote
0answers
282 views

A detail in the proof of the Motzkin-Straus theorem

The Motzkin-Straus theorem says that the global optimum of the quadratic program $$\max f(x)=\frac{1}{2} x^{t}Ax,\qquad \mbox{ subject to }\sum x_{i}=1 \mbox{ and } x_{i}\geq 0,$$ where $A$ is the ...
2
votes
0answers
85 views

A Conjecture related to minimization of product of determinants over permutations

Hi I have the following problem (and a conjecture which holds in Matlab). Given an $N\times N$ matrix $H$, represent it by its $2N\times 2N$ real-valued representation (which I will also denote by ...
3
votes
0answers
100 views

Multiple Number Partitioning / “Multiprocessor Scheduling”

Consider the well-known Number Partitioning / "Multiprocessor Scheduling Problem": You want to partition a set $S$ of objects (jobs) $i$ with weights $w_i$ (process time) into subsets $S_k$ (e.g. ...
2
votes
1answer
197 views

An optimization problem, non complete bipartite graph and hungarian algorithm

I have two tables at my disposal, one work dataset and one reference dataset. Each dataset has got two columns, lets say these are fields A and B. I would like the rows in reference dataset with the ...
1
vote
3answers
1k views

How to get the largest subset of a set of sets of intervals with no overlapping intervals

Given: Set of Set of Intervals. Example {{(1,2), (3,4)}, {(1, 3)}, {(13,14)}} Wanted Result: Largest Subset, in which no Interval overlaps with another from every Set pairwise. Example: Input ...
4
votes
1answer
231 views

An optimization involving (random) graphs

Suppose we have a graph on $n$ nodes. We would like to assign to each node either a $+1$ or a $-1$. Call this a configuration $\sigma \in \{+1,-1\}^n$. The number of $+1$s that we have to assign is ...
8
votes
1answer
197 views

Algorithm for matching in the power set lattice

Suppose that we have two probability distributions, $f$ and $g$ on the subsets of a finite set $X$, i.e. $f, g: P(X) \to [0,1]$, with $$ \sum_{A \subseteq X} f(A) = \sum_{A \subseteq X} g(A) = 1. $$ ...
3
votes
1answer
185 views

Integral of a quadratic on a polygon (variations of discrete surfaces)

This question is pretty simple to state: given two linear functions on a polygon, I'm looking for a formula for the integral of their product which depends only on the values at the (unlabelled) edges ...
4
votes
1answer
442 views

An optimization problem involving sum of binomial coefficients upto some value

I would like to minimize $f(s, n, \epsilon)$ with respect to $s$ where $$f(s,n,\epsilon) = \left( 1 + \frac{n}{2^s} \right)\frac{1}{s} \sum_{k=0}^{\lfloor s\epsilon \rfloor} {s \choose k}~.$$ Note ...
1
vote
0answers
117 views

Minimizing an entropylike expression with a quadratic constraint

Let '$\{X_i\}$' be a set of n positive integers, and fix k to be a positive integer. I am interested in finding the set of solutions to the pair of inequalities: '$\displaystyle \sum_{i=1}^n X_i ...
0
votes
0answers
412 views

Decomposing max-convolution of sum of functions ?

Hello. $R, F_1, F_2, F_3$ are random (not-convex, not-concave) 2D matrices of size 100x100. $R$ is a linear combination of $F_1, F_2, F_3$. Explicitly, $R = w_1 F_1 + w_2 F_2 + w_3 F_3$ where ...
2
votes
1answer
251 views

Maximum-bend TSP

I've seen minimum-bend TSP studied, has anyone looked at max-bend TSP? As a special case, I'm interested in the maximum number of turns a hamiltonian path can take in an $n \times n$ square grid. I ...
3
votes
2answers
486 views

Cubic graphs which are “difficult to navigate”

Suppose I am inside a finite, weighted cubic graph without loops, with no information regarding its layout, including the number of vertices or distances to the adjacent vertices. I want to reach a ...
1
vote
2answers
1k views

Greedy approach to 0-1 Knapsack problem in specific instances

The 0-1 knapsack problem is known to be NP-complete, and the greedy approach by Dantzig (based on choosing on the basis of density or value/weight) can be shown to be suboptimal using counterexamples. ...
1
vote
1answer
483 views

Split sum into equal terms

Given a sum of $l$ integers $r_1+...+r_k+...+r_l$ and an integer $t$. Find indices $1 < p_1 <...< p_h <...< p_{t-1} < l$ such that in sum ...
4
votes
0answers
177 views

restricting “dances of minimal cost” (optimization on braids/permutations?)

Consider applying the permutation (1,3,0,5,2,7,4,6) to the integers (0,1,2,3,4,5,6,7) three times. I call this a "dance of minimal cost" because all unordered pairs in {0..7} meet each other, and the ...
3
votes
2answers
2k views

Maximum flow with negative capacities?

I'm trying to compute an (s-t) maximum flow through a network which includes a number of arc pairs ((u,v), (v,u)) that have equal, negative capacities (weights). I'm not aware of any efficient ...
2
votes
2answers
557 views

Mean curvature of polyhedral surfaces

Whilst working on this problem, I've come across the work of Konrad Polthier on generalizing the notion of curature to discrete surfaces; much of his work is covered in his thesis, "Polyhedral ...
8
votes
2answers
647 views

Covering a random graph with spanning trees.

Let $G=(V,E)$ be a connected graph, say $V=\{1,\ldots,n\}$. Let $F=(V,E')$ be a uniformly random forest in $G$. (In other words, $E'$ is a subset of edges $E$ not containing a cycle, and it is ...
27
votes
0answers
2k views

A Combinatorial Abstraction for The “Polynomial Hirsch Conjecture”

Consider $t$ disjoint families of subsets of {1,2,…,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ . Suppose that (*) For every $i \lt j \lt k$ and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$, ...
-1
votes
2answers
712 views

dynamic programming and combinatorics

Suppose there are $ K $ buckets each can be filled upto $ N-1 $ balls. The gain on putting $ i $ balls in the $ k^{th} $ bucket is given by $ \Delta l_{k,i}, \, i \in [1,N-1] $. The problem is to ...
1
vote
0answers
366 views

Minimizing quadratic form over permutations

Let $Q$ be an $n \times n$ real symmetric matrix and $x$ an $n \times 1$ real vector. Consider the following minimization problem: $\min_{\pi \in S_n} ~(\pi x)^{\rm T} Q (\pi x)$, where $S_n$ ...
5
votes
1answer
366 views

How to optimize student happiness in group work?

There are $n$ students in a class, and they must be divided into, say, $k$ groups. Each student ranks the other students in order of preference of working together. Is there a way to generally ...
5
votes
3answers
604 views

How can I embed an N-points metric space to a hypercube with low distortion?

I have a N-point metric space defined by the pairwise distance matrix. I want to encode these N points with binary strings, i.e. each point will be mapped to a vertex in a hypercube. The lengths of ...
11
votes
6answers
3k views

Solving NP problems in (usually) Polynomial time?

Just because a problem is NP-complete doesn't mean it can't be usually solved quickly. The best example of this is probably the traveling salesman problem, for which extraordinarily large instances ...
1
vote
0answers
120 views

Term to describe how much harder an optimization problem can become after constraining a small part of the domain?

This is a follow up to this question. I'm interested in discrete optimization problems formulated as 0-1 integer programs; essentially, anything of the form $$\Phi = \max_{\mathbf{x} \in ...
3
votes
2answers
272 views

Hardness of combinatorial optimization after adding one constraint

I'm interested generally in discrete optimization problems formulated as 0-1 integer programs; essentially, anything of the form $$\Phi = \max_{\mathbf{x} \in \left\{0,1\right\} ^N} f(\mathbf{x})$$ ...