All Questions
24
questions
1
vote
1
answer
74
views
Generate superset with maximum overlap
I have a set $S$ with a total of 20000 items. I am also given a list $L$ of 0.5 million sets, with each set having 1-20 elements from the original set. I am given an integer $n$. Now I need a new set $...
- 129
0
votes
1
answer
27
views
Choosing k elements with multiple weights maximizing the minimum weight
Consider the following optimisation problem.
Given a set $S$ with $q$ weight functions $w_1, \ldots, w_q: S\rightarrow \mathbb{R}_+$ and a constant $1\leq k\leq |S|-1$.
Find an $X\subset S, |X|=k$ ...
- 31
2
votes
2
answers
86
views
Is this problem NP-hard？Or what kind of mathematical problem does it belong to?
Assuming there are n types of gifts, each with a number of $a_n$. Now we have to pack them into gift packs, each containing several types of gifts, and each gift has only one.If a gift package ...
- 33
1
vote
0
answers
48
views
Squared multiplicty minimization in multiple set choosing problem
The problem is the IOI 2007 competition's Sails problem. It has also appeared in Pranav A. Sriram Olympiad Combinatorics notes (Chapter 1 Exercise 14). I copied the problem description from Pranav. ...
- 11
0
votes
0
answers
36
views
Understanding the optimality bound for Greedy algorithm in maximization of monotone submodular functions
I am trying to understand whether the Greedy algorithm guarantee for maximization of monotone submodular functions with a cardinality constraint is a lower bound on the performance. This is the ...
1
vote
1
answer
149
views
How to assign tasks to a set of machines, given that the more tasks you assign to a machine the slower they will run? Bin covering with merging bins?
Intro
I need to design an algorithm that will distribute a known set of tasks with a known RAM requirement to a known set of machines with known RAM capacities. The tasks require a certain amount of ...
- 113
2
votes
1
answer
281
views
An efficient algorithm to generate a set of tuples satisfying a given upper bound for a distance between two arbitrary elements
Let $T_i^n$ denote a particular tuple of $n$ natural numbers (here $i < n!$ and we assume that the tuple contains all elements of the set $\{0, 1, \ldots, n-2, n-1\}$, i.e. there are no duplicates)....
- 922
0
votes
1
answer
53
views
Optimal Card Game Schedule
I have the responsibility of creating a schedule for a card game league. While creating the schedule, the following problem has arisen...
Let $n,g,s \in \mathbb{N+}$ where $s \leq n$.
Let $P = \{1, 2, ...
- 213
1
vote
1
answer
73
views
Trivial approximation ratio of $n/2$ for 2-Opt for TSP
I recently read that the 2-Opt algorithm for the TSP yielded an approximation ratio of $n/2$ by trivial reasons. However, there was neither proof nor further context provided and I am curious how this ...
- 177
3
votes
2
answers
147
views
Select five vectors that upon undergoing elementwise multiplication are most similar to another vector
I have a sparse $60000\times10000$ matrix where each element is either a $1$ or $0$ as follows.
$$M=\begin{bmatrix}1 & 0 & 1 & \cdots & 1 \\1 & 1 & 0 & \cdots & 1 \\0 &...
- 31
0
votes
1
answer
544
views
Algorithm to find the largest intersection of sets
Edit:
I've tried to be more precise, clear up my examples, and to clarify the problem. Hopefully the problem makes more sense now.
The problem is this:
I have a list of sets $$S_1, S_2,... S_N$$ ...
- 171
7
votes
1
answer
132
views
A hat allocation problem
This is an abstraction of a problem that has come up in my research.
Imagine we have $N$ wizards and $N$ hats. The hats have $C$ different colours. There are $n_1>0$ hats with the first colour, $...
- 1,295
0
votes
2
answers
70
views
Maximizing a combinatorial identity
So here is my problem. If we have a vector $\textbf{x}=(x_1,...,x_n)$ where $x_j \in \mathbb{N}$ for each $j \in \{1,...,n\}$, then is there a way to maximize the value of the following combinatorial ...
user830143
1
vote
2
answers
100
views
Uniformly distribute N colored balls to P players, minimizing number of colors
I am facing the following combination problem :
I do have $B$ colored boxes, each one containing $N_b$ balls of the given color.
The total number of balls is thus $\sum_{b=1}^{B} N_b = N$.
I want ...
- 11
0
votes
0
answers
185
views
Greedy Algorithm on Knockout Tournaments: Proof of Correctness
You are given a function $\operatorname{rk}:\{1\dots 2^k\}\rightarrow \mathbb{N^+}$ representing the ranks of the players $1\dots2^k$ in a participating in a tournament. The tournament evolves in a ...
- 11
14
votes
1
answer
337
views
$200n$ diagonals are drawn in a convex $n$-gon. Prove that one of them intersects at least $10000$ others.
$200n$ diagonals are drawn in a convex $n$-gon. Prove that one of them intersects at least $10000$ others.
There was no information about $n$ in a original problem.
Attempt: Choose at random and ...
- 90.7k
1
vote
1
answer
54
views
Minimize the sum of components of a hypercube under a system of $0,1$ equations.
Let $x_1, \dots, x_5, y_1, \dots, y_4$ be a total of nine variables taking values merely in $\{0, 1\} \subset \Bbb{Z}$. Therefore a solution is a point on a hypercube.
These are the constraint ...
0
votes
0
answers
31
views
What is the name of following optimization problem and algorithms to solve them
Let $S=\{1,\ldots,n\}$ be a set and $w_i (\geq 0)$ be the weight of element $i$. Let $R_j, j = 1,\ldots,m$ be subsets of $S$, called the restriction sets. Choose elements from set $S$ to maximize ...
- 101
15
votes
2
answers
1k
views
Domination problem with sets
Let $M$ be a non-empty and finite set, $S_1,...,S_k$ subsets
of $M$, satisfying:
(1) $|S_i|\leq 3,i=1,2,...,k$
(2) Any element of $M$ is an element of at least $4$ sets among
$S_1,....,...
- 90.7k
2
votes
1
answer
962
views
Optimal permutation of sequence using a graph based approach
I am stuck with an optimization problem in one of my projects which requires me to find a permutation $\Sigma = \{x_{\sigma_1}, x_{\sigma_2}, \ldots, x_{\sigma_N}\}$ of a sequence $\{x_1, x_2, \ldots, ...
- 482
1
vote
1
answer
78
views
Groups that cover weighted set
I am trying to find an efficient algorithm to give solutions to the following problem.
There is a set of unknown groups of elements $g_1$, $g_2$, $g_3$, etc. that together contain and cover a set of ...
- 11
3
votes
3
answers
129
views
Efficient algorithm for optimization problem.
I had an interesting interview problem today. Let's assume that we have n boxes, containing many numbers. For instance, let's say $n=4$, and four boxes contain the following numbers:
...
- 391
4
votes
1
answer
395
views
Algorithm to find shortest path to net values across nodes
I have an undirected graph $G = (V, E)$ with nodes $V$ and edges $E$.
Each node $v$ has an associated number $n_v \in \mathbf{Z}$
Let us define for any two nodes $v, w \in V$ connected by an edge $e ...
- 595
2
votes
2
answers
689
views
Combining kindergardeners in 'fair' cookie-baking groups. Kirkman's schoolgirl problem extended version
I am coordinating cookie-baking events with kindergarten kids. This turns out to be a challenging problem, and I could use a little help:
We would like a general way of creating 'fair' cookie-baking ...
- 123