# Tagged Questions

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" ...
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" ...
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 ...
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. ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
40 views

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

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

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