0
votes
0answers
9 views

maximizing a function involving factorial.

Can someone suggest a way to calculate the maximum with respect to $x \ge 1$ of: $$f(x)=\frac{1}{x!} \frac{1}{1-c^{1/\binom{x+n-1}{n-1}}}.$$ The constants $c$ and $n$ are parameters such that $c \in ...
-2
votes
0answers
22 views

Relaxation of optimization problem [duplicate]

Can I solve the following optimization problem, $$f= \max \{h(Y) - h(Y|U)\}$$ by solving an easier upperbound on $f$ for example $g > f$ where $g= \max\{h(Y)-h(Z)\}$. My aim is to prove that ...
1
vote
1answer
24 views

Number of Integer solutions for this optimization problem

What is the number of integer solutions to the problem $$\sum_{i=1}^{i=k}x_i = n$$ subject to $\forall_i\ \ x_i \ge 0 $ note This should hold for both cases $k < n$ and $k \ge n$
1
vote
0answers
61 views

Efficient calculation of minimal expected number of inversions

Problem: I have an array of size n with Z inversions initially and I am allowed to perform K operations where each operation can be decrease the number of inversions by 1. make a random shuffle of ...
2
votes
2answers
116 views

How to find the optimal mapping between two sets?

Given two sets $A$ and $B$, both of $n$ points $p \in \mathbb{R}^3$. I want to find a bijective function $f:A \rightarrow B$ so that the cost $C$ is minimal. It's defined as the sum of all pair's ...
0
votes
1answer
27 views

Distribute N items in K sets with minimum overlap

I am working on an optimization problem to distribute N distinct items (each of the items is available in infinite quantity), among K sets. Each set should have T items. (The constraint of T can be ...
4
votes
3answers
174 views

Biggest subset of $\{1, 2 … 1000\}$ such that difference between any pair of elements $\neq 4, 7$

The problem, as stated in the title, is to find the maximal size of a subset $V$ of $S = \{1, 2, ... 1000 \}$ such that no two elements of $V$ have a difference of 4 or 7 between them, i.e. $x \in V ...
2
votes
0answers
49 views

How to load warehouse pallets efficiently?

Assume that we would wan't to develop a warehouse management system, which picks up plastick boxes and stacks them on a pallet. A pallet has a maximum of 5 vertical box stacks and the maximum height ...
0
votes
0answers
53 views

How to determine if a convex polytope is contained in a union of convex polytopes?

Given that we are in a Euclidean space of dimension d, that we have a bounded convex H-defined polytope P, and N possibly unbounded convex H-defined polytopes, I am looking for an "efficient" ...
2
votes
0answers
28 views

what does “modular” mean?

I find some similarity of the concept "modular set functions" to the cardinality function. But I don't see the cardinality function is also called "modular" or something else. I wonder what "modular" ...
1
vote
0answers
25 views

What does “modular” in “modulr functions” mean?

From Wikipedia If $\Omega$ is a set, a submodular function is a set function $f:2^{\Omega}\rightarrow \mathbb{R}$, where $2^\Omega$ denotes the power set of $\Omega$, which satisfies one of the ...
0
votes
0answers
41 views

Find maximum combination between elements in multiple sets

Here is my problem: I have multiple ordered sets of different length and I want to find the maximum sum that conforms to a constraint (upper or lower bounded) using zero or one element from each set. ...
6
votes
1answer
53 views

maximize a function which contains factorials

Suppose I have a function $$ f(k) = \binom{500}{k} \binom{500}{1100-3k}$$ where $k$ is an integer from $200$ to $366$. How can I find the maximum analytically?
0
votes
1answer
39 views

Assigning workers to tasks such that difference of the number of workers for each task to a given optimum is minimized

Im trying to find an algorithm to solve the following problem: We have a set of workers and some tasks, with not every worker being able to do any kind of task (but at least one). Theres is ...
1
vote
1answer
39 views

Minimizing the risk of misfires and duds in a missile control system

I was thinking the other day about all the different ways humanity could end itself -- I won't depress you all by listing them here -- and misfired nuclear missiles came to mind. The problem below is ...
0
votes
0answers
16 views

finding argmax for similarity graph

I am wondering if there is any general method for solving the following combinatorial optimization problem. Let's suppose that there are m objects and you would like to know what class each object ...
0
votes
0answers
37 views

Keller 6 graph and maximum clique

Based on the DIMACS maximum clique benchmark, http://iridia.ulb.ac.be/~fmascia/maximum_clique/, the Keller 6 graph contains a clique of size 59. The clique number however is at least 59 (as can be ...
2
votes
0answers
31 views

How do you find a minimum of a function with these tools?

Let's say I can define a group $G$ acting on a set of combinatorial objects $X$ and I have a function $f: X \to \Bbb{N}$ that I want to find a minimum of in $X$. Is there a polynomial time ...
0
votes
2answers
42 views

Solving Problem by different Method ( non-induction)

I have this problem , which I was able to prove it by induction, but I wonder could be solve by direct method ( for example combinatorial method). I want to find number of solution for $$0 \le ...
0
votes
4answers
140 views

Maximizing the Magnitude of the Resultant Vector

Given a set of $n$ two-dimensional unit vectors: $\left\{ \mathbf{v}_1, \dots, \mathbf{v}_n \right\}$, I want to find the coefficients $\left\{ \alpha_1, \dots, \alpha_n \right\}$, $0 \leq \alpha_i ...
3
votes
2answers
181 views

How many routes possible in the traveling salesman problem with $n$ cities? And more…

SO the general answer I come across on the internet is $(n-1)!/2$. But it would seem to be $n!$, or at least $(n-1)!$. Which one is it? If you have 2 cities, you would have 1 path. So $(n-1)!/2$ ...
4
votes
3answers
152 views

How do you prove ${n \choose k}$ is maximum when k is $ \lceil \frac n2 \rceil$ or $ \lfloor \frac n2\rfloor $?

How do you prove ${n \choose k}$ is maximum when k is $ \lceil \frac{n}{2} \rceil $ or $ \lfloor \frac{n}{2} \rfloor$ ? This link provides a proof of sorts but it is not satisfying. From what I ...
6
votes
1answer
705 views

Why is Dantzig's solution to the knapsack problem only approximate

For a bunch of items with values $v_i$ and weights $w_i$, and with a total weight $W$ that our bag can carry, how do we achieve maximum total value without breaking the bag? Dantzig proposed that we ...
1
vote
0answers
60 views

Prove that there exists a subset with sum >=1 such that the remaining integer sum reduces by 1

let $ n \in \mathbb{N} $ and $ \frac{1}{w_1},\ldots, \frac{1}{w_n} $ for some (not necessarily distinct) $ w_1,\ldots,w_n \in \mathbb{N} $ and $ w_1,\ldots,w_n \ge 2 $ be given. Assume that $ ...
0
votes
3answers
64 views

How to find a set of ascending natural numbers which when added to another set of ascending natural numbers sums to a certain number

Given: $$ X = \left\{ x_1, x_2, \ldots , x_n \right\}\text{ with }x_i \in \mathbb N\text{ and }1 \le x_i \le x_{i+1} $$ $$ z \in \mathbb N $$ Wanted result: $$ Y = \left\{ y_1, y_2, \ldots , y_n ...
1
vote
1answer
25 views

Proxy optimisation problem

Suppose we have a set of participants $p$ who should attend $e$ number of events and everyone of them must declare his presence with signature. Each can however sign for $s$ number of other ...
0
votes
0answers
31 views

How can Ant Colony Optimization be made to produce more consistent results?

I developed a software implementation of Ant Colony Optimization to solve the Traveling Salesman Problem, but due to ACO's stochastic nature, each execution of the ACO algorithm produces a different ...
1
vote
0answers
46 views

Maximum of the minimal distance of a set of points in an equilateral triangle

In this question, a closed triangle on a plane is a set of all points in its area and on its boundary, while an open triangle excludes its boundary. Now, the problems: Let $T$ be an equilateral ...
0
votes
1answer
83 views

Stock cutting and column generation giving suboptimal answers?

I'm doing a stock cutting implementation. I use the delayed column generation approach. I'm getting suboptimal answers with the following simple case: raws length: 630 in. demands: 10 x ...
0
votes
0answers
76 views

Proving a minimum spanning tree is unique iff any edge (a,b) not in T has larger weight than any edge on the circuit created by adding it

Proving a minimum spanning tree is unique iff any edge (a,b) not in T has larger weight than any edge on the circuit created by adding it I'm not sure how to prove this because I'm new to these style ...
5
votes
0answers
88 views

Measure minimization for a combination of overlapping sets

This problem may have been worked out before but I don't know where to start looking so I hope one of you can help me. The problem is as follows: There are $N$ variable-sized finite sets ...
0
votes
0answers
19 views

Upper bound on loss of value

A bag contains $n$ items with different values. The value of each item is in $[\frac{1}{n},1]$, and the sum of values is $U$. Now, the bag is shaken so that some items break and their value ...
0
votes
0answers
65 views

travelling salesman problem with pairs of cities and constraints

I am looking for the name of the following two problems, and an approach to solve them. Problem#1: given N nodes, find the shortest path starting at a given start node and ending at a given end node, ...
1
vote
1answer
30 views

organizing rectangles on top of each other

We have some rectangles that should be organized in a number of columns. Each column height should be in the range of $[H, H+d]$ in which $d$ is a small number relative to the height of the ...
6
votes
0answers
148 views

Selecting a subset from a set such that a given quantity is minimized

Let $A$ be is a set of some $p$-dimensional points $x \in \mathbb{R}^p$. Let $d_x^A$ denote the mean Euclidean distance from the point $x$ to its $k$ nearest points in $A$ (others than $x$). Let $C ...
2
votes
1answer
57 views

Maximum of a sequence $\left({n\choose k} \lambda^k\right)_k$

Is there an expression for the maximum of a sequence $\left({n\choose k} \lambda^k\right)_k$ (i.e. $\max_{k\in\{0,\ldots,n\}}{n\choose k}\lambda^k)$ in terms of elementary functions of $n$ and ...
4
votes
1answer
120 views

Maximising probability for financial advice

I have the following problem: A financial advisor tries to impress his clients if immediately following a week in which the ftse index moves by more than $5\%$ in some direction he correctly ...
0
votes
1answer
63 views

Combinatorics : Prove - Graph Algorithm

I am studying Graph Algorithms. I can solve the graph algorithm problems but I am confused with this proposition. If I were to prove this proposition, how would I start? Can anyone help here? Thank ...
2
votes
3answers
74 views

Maximizing a product of factorials

I would like to maximize $n_1! n_2! \cdots n_k!$ under the constraint $n_1 + n_2 + \cdots + n_k = N$ and $n_i > 0$ for all $i$. Intuitively, I think the maximum occurs when all $n_i$ are $1$ except ...
0
votes
1answer
18 views

Lower bound on maximal value

A bag contains $n$ items with different values. The total value is $1$. I am allowed to pick one item, and pick the item with the maximal value. Obviously, in the worst case I will get a value of $1 ...
1
vote
1answer
126 views

Baseball Roster Optimization

I'm trying to programmatically optimize a Fantasy Baseball Roster that requires a fixed number of players at position (2 Catchers, 5 Outfielders, etc.) and has a salary constraint (total draft price ...
0
votes
0answers
38 views

How to find a disjoint set covering with maximum cost function

Given a set U of m elements, $U=\{u_1, u_2,\ldots, u_m\}$ (called the universe), and a set S of all subsets of U, $S=\{s_1, s_2, \ldots, s_{2^n}\}, |S|=2^m$. Each subset $s_j$ is associated with a ...
2
votes
2answers
73 views

Minimisation of a distance sum

I have a list $L$ of $N$ numbers, and I want to choose $k$ numbers $\{x_1,x_2, \ldots,x_k\} \subseteq L$ in such a way value $S$ of the those K numbers is minimum. $$ S = \sum_{0< i < j <= k} ...
1
vote
0answers
173 views

Strange but practical Bin packing problem

I am trying to solve the following MILP through LP solve. A link for the original problem is here I am re-iterating the problem as follows: I am trying to write an application that generates drawing ...
1
vote
2answers
55 views

Why compare f(n)/f(n-1) = 1 to solve for the maxima of a discrete function?

I am aware of a general strategy where you have a discrete function, e.g., $f = \dfrac{{10 \choose 5}{n-10 \choose 15}}{n \choose 20}$ And in order to find the maximum, you solve ...
0
votes
1answer
74 views

Minimum number of money to make each element in list greater than or equal to 0?

Given list with positive and negative integers.We have to make each element greater than or equal to zero.There are two types of moves first increase all elements by 1 requires P unit of money, second ...
2
votes
2answers
139 views

Shortest ternary string containing all ternary strings of length 3?

How can we find/construct the shortest ternary string that contains all ternary strings of length 3? For instance, $120011$ contains $120$, $200$, $001$, and $011$. (The shortest such a string could ...
1
vote
0answers
56 views

Confusion related to k neighborly polytope

I was reading this paper related to neighborly polytope where they mentioned: Consider a $d \times n$ matrix $A$, with $d < n$. The problem of solving for $x$ in $y = Ax$ is underdetermined, ...
3
votes
1answer
146 views

Dividing a set of points into two sets of roughly equal diameter

Let $S$ be a finite set whose cardinality is more than 1 and $d: S\times S\rightarrow\mathbb R$ be a positive symmetric function (that is, $d$ is a distance without the axiom of triangle inequality). ...
2
votes
1answer
39 views

For what variables these equalities are satisfied?

Assume: $$ P \subseteq \{1,2,\dots,N\},\quad |P| = K, \qquad x \in \mathbb{R}_+^K , \qquad w = e^{-j\frac{2\pi}N} $$ Consider: $$ h_{P,X}(l) = \sum_{i=1}^K \sum_{j=1}^K x_ix_jw^{(p_i-p_j)l} $$ Now ...