0
votes
0answers
48 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
25 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
20 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
36 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
49 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
33 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
38 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
12 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
30 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
40 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
125 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 ...
6
votes
1answer
678 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
61 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
26 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
44 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
79 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
74 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
78 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
59 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
141 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
118 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
62 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
67 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
115 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
72 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
167 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
54 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
73 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
137 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
41 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
38 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 ...
3
votes
2answers
147 views

Is $\binom{52}{n}\cdot\binom{52-n}{n}$ maximised by $n=\frac{52}{3}$? If so why?

I've been thinking a lot about cards, and recently about the combination of combination of hands....if you drew $n$ cards from a deck of $52$, and then drew another $n$ cards, how many combinations ...
6
votes
3answers
829 views

Minimizing Appreciating Quantities vs. Maximizing Depreciating Quantities

Suppose you have a set $S = \{r_1, ..., r_n :\, r_k \in (1, \infty)\, \forall \,k \in \{1,...,n\}\}$. Find a bijective mapping $f: \{0,...,n-1\}\rightarrow \{1,...,n\}$ that minimizes \begin{align*} ...
1
vote
1answer
48 views

Simple question of maximum value a part can have?

We have to partition n chocolates among m children. Children will be happy if max and min a child has got is less than 2. What is the max a child can get?? For n=6 m=3 ,the partition will be 2 2 2 ...
0
votes
0answers
48 views

What is that type of TSP

I'm searching for the name of the TSP-like problem. The basic principal is like it follows: When a city is visited by the salesman, he will came in one point and exit the city in another. The ...
1
vote
0answers
136 views

Finding the fractional vertex-cover number ($\tau ^ \star$) for k-cycle hypergraphs.

Given a hypergraph $H$, we define $\tau (H)$ to be the minimum-vertex-cover number of $H$. That is, the size of the smallest $C \subseteq V(H)$ such that $C$ meets all edges in $E(H)$. A quite ...
0
votes
3answers
143 views

Maximizing triangle area

Here is the problem: We start with a triangle ABC with area 1. We choose a point (F) on side AB, then someone else chooses a point (G) on side BC. We then choose the last point (H) on side CA. Our ...
1
vote
1answer
69 views

Hungarian Algorithm with different metric

I have a modified Assignment Problem, that can almost be solved using the Hungarian Algorithm. Instead of trying to minimize the sum of costs of assignments, I want to minimize the cost of the ...
1
vote
1answer
109 views

How to cast the “Numberdrum” problem mathematically

I came across the numberdrum problem in the Evening Standard, where the objective is to obtain a number in the centre using each of the numbers in the outer ring exactly once, along with the four ...
4
votes
1answer
150 views

A variant of assignment problem (different sizes of sets)

I'm given objects divided into two disjoint sets, $A$ and $B$. There's a cost function defined, so that I know a positive cost (or distance) of any assignment $(a,b)\;|\;a \in A,\; b \in B$. It always ...
4
votes
2answers
675 views

Change-making problem - counterexample for greedy algorithm

Let D be set of denominations and m the largest element of D. We say c is counterexample if greedy algorithm is giving answer different from optimal one. I found statement that if for given set ...