Tagged Questions

0
votes
0answers
40 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
42 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
84 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
31 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
91 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 ...
3
votes
1answer
99 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
317 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 ...
11
votes
3answers
358 views

Combinatorial optimization - improve performance

I am writing a program to solve a combinatorial optimization problem. I have been working on an algorithm that gets the desired results, but I am having difficulties getting the algorithm to perform ...
1
vote
1answer
136 views

Maximize distance between points on a line

So lets say I have a certain duration of time starting at time(0) ranging to time(N). I also have a set of points whose values all exist within the range of values of that time frame. I want to pick ...
0
votes
1answer
81 views

How to minimize cost of group of items given that weights of item sums up to fixed value and atmost 'n' number of items are allowed?

Given that we have a set of items :- { (c1, w1) , (c2, w2), (c3, w3) , ... } where (ci, wi) are the respective cost and weight of the ith item. Its required to minimize total cost of items C such ...
0
votes
0answers
40 views

How to minimize cost of group of items given that weights of item sums up to fixed value and atmost 'n' number of items are allowed? [duplicate]

Possible Duplicate: How to minimize cost of group of items given that weights of item sums up to fixed value and atmost 'n' number of items are allowed? Given that we have a set of ...
1
vote
1answer
50 views

“Cookbook” methods for neighborhood structure design in simulated annealing for combinatorial optimization?

What are some "cookbook" methods for neighborhood structure design in simulated annealing for combinatorial optimization? Are some reviews or books that contain some "cookbook" methods for ...
1
vote
0answers
62 views

Local consistency and constraint propagation for intervals

I would like to solve constraint satisfaction problem for intervals. I denote each interval by coordinate of its begin $x_i$. The length of the interval is known convex function $l_i(x_i)$ of begin of ...
3
votes
1answer
44 views

Convex programming when the problem has an underlying combinatorial structure that's a DAG

I have a nonlinear convex objective function to minimize. The function is defined on a set of variables: $\{ x_1,x_2, \ldots ,x_p \},$ where each $x_i$ is a number associated with a path in the DAG. ...
0
votes
1answer
72 views

Solution for assigning independent tasks to independent individuals

I have $n$ tasks that I wish to delegate to $m$ independent individuals, where $m$ is a factor or divisor of $n$. Each of the tasks $T_{1} ... T_{n}$ is independent. From the following two extremes, ...
1
vote
0answers
45 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 ...
3
votes
1answer
67 views

Allocate items to an unknown number of resources

I have this problem that I want to understand how to model as a mathematical program: there is a set $N$ of $n$ items; each item has a known weight $w_i$. I have bags of equal capacity $W$. I want ...
4
votes
0answers
912 views

Optimal Resolvable Steiner Quintuple System covering with circles and ellipses

Here is a resolvable Steiner quintuple system. Every tuple from 1-25 appears in exactly one of the sets. {{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15},{16,17,18,19,20},{21,22,23,24,25}, ...
1
vote
0answers
86 views

Shortest path variation

I'm looking for a solution to the following problem, related to shortest path. You are given a directed Graph $G = (V,E)$, source $s$, targets $t_1, t_2, \cdots , t_k$ and costs $c_{ij}$ for ...
4
votes
1answer
183 views

minimum number of vertices for a specific graph

Today I saw this problem: Find the smallest $n\ge 5$ such that there exists a simple graph on $n$ vertices such that any two adjacent vertices have no common neighbours, and any two non-adjacent ...
2
votes
3answers
451 views

Dividing a set into two subsets the optimal way (May be similar to the knapsack problem)

We have n stones having weight m[1]..m[n], and two sacks. We put each stone into first or second sack; the resulting sacks ...
0
votes
2answers
43 views

Upper bound of the optimal value in one particular maximization problem

Suppose that we have a integer $m$, and we need to choose $n\le m$ and $x_1,x_2,...,x_n$ such that $\sum_{i=1}^nx_i=m$ and $\prod_{i=1}^nx_i$ is maximized, where $n$ and all $x_i$'s are integers. In ...
2
votes
1answer
105 views

Simplify the Hungarian Algorithm for cases of an extremely sparse cost matrix?

I have an optimization problem on a set of data that is solvable with the Hungarian Algorithm and works well on small sets. But the full set of data is large and only 0.1% of the cost matrix is even ...
2
votes
0answers
94 views

An optimization problem involving Latin Squares

Let $C$ be a given $n \times n$ matrix of real numbers and let $p$ be a given $n$ vector of non-negative numbers such that wlog $\sum_i p_i = 1$ and wlog the $p_i$ are non-increasing. I'll write ...
2
votes
2answers
162 views

To minimise max bin sizes in two-level balls-and-bin problem

Basically we consider two levels of mapping (the first is called partition and second mapping strategy) of balls into bins. And try to find the best partition strategy (the first level of mapping) to ...
3
votes
2answers
130 views

Calculate max/min of $x_1 x_2+y_1 y_2+z_1 z_2+w_1 w_2$

What is a good way to calculate max/min of $$x_1 x_2+y_1 y_2+z_1 z_2+w_1 w_2$$ where $x_1+y_1+z_1+w_1=a$ and $x_2+y_2+z_2+w_2=b$ and $x, y, z, w, a, b \in \mathbb{N} \cup \{0 \}$, and please explain ...
8
votes
4answers
975 views

Looking to understand the rationale for money denomination

Money is typically denominated in a way that allows for a greedy algorithm when computing a given amount $s$ as a sum of denominations $d_i$ of coins or bills: $$ s = \sum_{i=1}^k n_i ...
8
votes
1answer
773 views

On problems of coins totaling to a given amount

I don't know the proper terms to type into Google, so please pardon me for asking here first. While jingling around a few coins, I realized that one nice puzzle might be to figure out which $n$ or so ...
1
vote
1answer
138 views

Combinatorial Optimization Problem (can I/how do I solve this with integer programming?)

Inputs: 1) A set of M x N matrices, {A,B,C...N} containing only integers. 2) A single 1 x N matrix of floats, W (weights). I need to pull one row from each input matrix and sum values for each ...
4
votes
2answers
311 views

Sparsest matrix with specified row and column sums

Given a sequence of row sums $r_1, \ldots, r_m$ and column sums $c_1, \ldots, c_n$, all positive, I'd like to find a matrix $A_{m\times n}$ consistent with the given row and column sums that has the ...
10
votes
1answer
204 views

Split up $n \in \mathbb{N}$ into sum of naturals with maximum LCM

Question: Given some natural number, we can of course split it up into various sums of other naturals (e.g. $7 = 6 + 1 = 1 + 4 + 2 = \ldots$) More precisely, for $n \in \mathbb{N}$, we can a find ...