The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
18 views

A variant of submodularity?

See the definition of submodulation functions: $$ f(A) + f(B) \geq f(A \cup B) + f(A \cap B) $$ Suppose I make this definition a little stronger: $$ f(A) + f(B) \geq f(A \cup B) + f(A \cap B) + A ...
1
vote
1answer
44 views

Minimizing image compression error (DCT)

I'm doing an assignement on image compression. I have to quantify the error given as $||A-\hat{A}||^2/||A||^2$, where $|\cdot|$ is the Eucledian norm. I really need help, so please just give some ...
0
votes
0answers
9 views

Algorithm to compare set of objects given a metric

Assume I have Objects $x\in X$ with an associated metric $d:X\times X\to\mathbb N_0$. I want to find a metric $d^*: \mathcal P(X) \times \mathcal P(X) \to\mathbb N_0$ wich compares sets of these ...
0
votes
1answer
40 views

Example Intersection Matroid is not a matroid.

Consider any two matroids $M_1=(E,\mathcal{I})$ and $M_2=(E,\mathcal{K})$ and let $\mathcal{Z}=\mathcal{I}\cap\mathcal{K}$. Can someone give an example where $(E,\mathcal{Z})=M_1 \cap M_2$ is not a ...
0
votes
0answers
14 views

What is an optimal order for integer vectors for minimization of the total distances?

I want to find an optimal order for a number of vectors (or a permutation of vectors) to minimize the sum of distances regarding to the following norm: (this norm is based on the distance on a cycle ...
0
votes
1answer
90 views

Algorithm producing a minimum spanning tree?

I need to prove that the following algorithm produces a minimum spanning tree(MST) upon termination. I think, looking at the lecture notes, that I need to reduce the operations to red and blue rules ...
0
votes
0answers
13 views

How to make likely-to-be-right-guess in “guess and verify method” in dynamic programming

So, in infinite horizon model with autonomous function, guess and verify method is used to solve the dynamic programming problem. But I can't simply rely on that method. At least I need to make ...
1
vote
1answer
28 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$
0
votes
0answers
17 views

Significance of eigen vectors in Max-Plus algebra

In Max-Plus algebra we have notion of eigen values and eigen vectors. Given a matrix $A \in \mathbb{R}_{max}^{n\times n}$ , $\mu$ is an eigen value of $A$ if it satisfies $A \otimes v = \mu \otimes v$ ...
1
vote
0answers
92 views

Find maximum height of smallest flower

Little beaver planted n flowers in a row on his windowsill and started waiting for them to grow. However, after some time the beaver noticed that the flowers stopped growing.So he decided to come up ...
3
votes
0answers
132 views

Finding optimal velocity profile using Dynamic Programming

This question has been asked on scicomp but I thought maybe it's more a mathematical problem of how Bellman's idea is to be applied here. The main problem for me is: How to introduce the time ...
1
vote
1answer
113 views

Knuth's Sandwich Theorem: requesting proof clarification

The question is about F6 of Section 8 ("Elementary facts about cones") in Donald Knuth's Sandwich Theorem (http://arxiv.org/pdf/math/9312214.pdf). He claims to prove $(A \cap B)^* = A^* + B^*$ when ...
2
votes
0answers
39 views

Given a set of nonnegative numbers, put $\pm$ between them to minimize the magnitude of the result

Let's say I have a finite set of non-negative numbers. I have to put $+$ or $-$ between the numbers, in order to minimize the absolute sum.(i.e the sum has to be closest to 0) For example: the set: ...
0
votes
1answer
27 views

Book recommendations for Binary Integer Linear Programming

I'm looking for a book on BILP, which focuses on algorithms / solutions methods. So far, I only found the following books on ILP "Integer and combinatorial optimization" by Nemhauser, George L. ...
0
votes
0answers
16 views

Must the weight function be nonnegative for the greedy algorithm to be optimal for both a matroid and a greedoid?

Must the weight function be nonnegative for the greedy algorithm to be optimal for both a matroid and a greedoid? For a matroid, the codomain of the weight function is $[0,\infty)$, from Wikipedia ...
0
votes
0answers
20 views

$k$ edge-disjoint $r$-arborescences in an acylic digraph

An $r$-arborescence of a digraph $D$ is a rooted spanning tree with root $r\in V(D)$ in which all the edges of $D$ are directed away from $r$. I would like to prove the following: I have thought ...
1
vote
1answer
39 views

Reduce problem to max flow

I have the following question: Assume each student can borrow at most 10 books from the library, and the library has three copies of each title in its inventory. Each student submits a list of ...
0
votes
0answers
11 views

About the logistic map.

I need guide line about it I also wanted to know how it will appear in graph if we use mathematica or some other software for this.
1
vote
2answers
42 views

About Recurrence Relations.

I need help in order to solve the following question, Here RR is for Recurrence Relations.
1
vote
0answers
40 views

Proof that a Polytope has vertices

As part of my Discrete Optimization course, I have a homework where I have to prove that a Polytope has vertices. I seems to have all tools in hand (definition of a vertex, polytop, convex hull, etc.) ...
1
vote
0answers
18 views

Comparing the hardness of optimizing two similar, but different expressions

Suppose we have binary variables $y_1, ..., y_n$. To make the representation simple, we show the concatenated vector as $\mathbf{y} = (y_1, ..., y_n)$. Consider the two following functions: $$ ...
0
votes
0answers
41 views

Removing backups in an exponential fashion

Background: I want to create a backup system that utilizes the full space of a hard-disk. Given that all backups are approximately equal in size this means that I can save a fixed amount of backups. ...
3
votes
0answers
78 views

How to find the minimal path between points in a planar set with holes in it?

When I was a commuter student, I would park in a very large parking that that had a set of stairs in a corner that I had to climb. In general, I had to park far away from this corner in an almost full ...
2
votes
1answer
28 views

How is the upper bound of a minimisation IP determined during branch-and-bound?

When using the branch-and-bound algorithm to solve an Integer Programming (IP) problem, the entire enumeration tree doesn't need to be evaluated and that's where the speed-up is achieved. Suppose the ...
1
vote
0answers
28 views

Finding 'closest' function subject to constraints on derivatives

Suppose I have a real-valued function $f(t)$ for $t\in[0,T]$ s.t. $f'''(t)$ is defined as piecewise constant values: $$ f'''(t) = \begin{cases} k_0, & 0 < t \le t_0 \\ k_1, & t_0 < t ...
3
votes
1answer
112 views

Minimizing Height of a Table

This optimization question popped into my mind while working with latex tables: Suppose we have a table with $m$ rows and $n$ columns, and for each $1\le i\le m,1\le j\le n$ we are given $T(i,j)$ ...
2
votes
0answers
15 views

is it a discrete optimization problem?

I have a function 'F' which has five input variables p1,p2,p3,p4,p5. Each one of the variable from p1 to p5 can have values from the sets S1,S2,S3,S4 and S5 respectively. S1,S2,S3,S4 and S5 are ...
1
vote
2answers
38 views

Knapsack variation NP-complete

I have C processors and $C$ items that have to be run on it. I can either run each item on a seperate processor and have a running time of $\sum_{i=1}^{c} c_i$, or divide the $C$ items into $k$ ...
0
votes
1answer
38 views

Can the search space of a solvable linear optimization problem be discontinuous?

Background Say you have a traditional linear-optimization problem, there is a linear cost function, $\vec{c}\cdot\vec{x}$ and a set of linear constraints, $A_1\vec{x} \geq b_1 $ $A_2\vec{x} \leq ...
0
votes
1answer
64 views

Polyhedron's Representations and spanning the Euclidian space

Let's say you have to different representations of the same polyhedron $P\neq \emptyset$: $$P=\{x\in \mathbb{R}^n\;|\;h_i^Tx\leq c_i, i=1,...,k \} =\{x\in \mathbb{R}^n\;|\;g_j^Tx\leq d_i, j=1,...,l ...
0
votes
0answers
27 views

Finding equivalent minimization problem

I am having some trouble while implementing the minimization problem of a paper. My goal is to minimize the following: $\epsilon_L = \epsilon_1 + \lambda \epsilon_2$ where: $\epsilon_1 = \sum_i ...
2
votes
1answer
65 views

Combination Problem with mulitiple variables

I am new to this, but getting into math more and have a question regarding combinations and permutations with several variables involved. I work for a sales company and this question is based on ...
0
votes
1answer
105 views

Mathematical Induction for greedy algorithm problem?

Suppose you want to place towers along a straight road, so that every building on the road receives cellular service. Assume that a building receives cellular service if it is within one mile of a ...
0
votes
1answer
85 views

How do I optimize a function subject to a two-part constraint?

I would like to maximize the following function $$\max\; U= log(xT_o + (1-x)T_s) + log(Y)$$ by choosing levels of $T_o$, $T_s$, and $Y$, and where $x\in[0:1]$ subject to $$N = \binom{P_sT_s+Y ...
2
votes
1answer
68 views

How to maximize $\left({a+b \choose a} 2^{-a-b}\right)$?

How can you maximize $\left({a+b \choose a} 2^{-a-b}\right)$ assuming, $a,b \geq 0$ and $0< (a+b) \leq n$, where all the variables are non-negative integers? Is the maximum when $a=b=n/2$, ...
1
vote
1answer
43 views

Minimise Total $x$, Maximum $x$ or $|x|$ in integer/linear programming

Suppose we have a linear program (it may be integer, it probably doesn't matter). Suppose the variables $t_j$ give the tardiness for job $j$, and we want to minimise something to do with this ...
0
votes
0answers
23 views

Weighted partial MaxSAT (and MinSAT) with real-valued weights?

Consider the following optimization problem ($\min$-version also of interest): $$ \max_{β\in\{0,1\}^m}\{c'φ(β): ψ(β)=1\} = \max_{\phi\in\{0,1\}^n}\{c'\phi: β\in\{0,1\}^m, \phi=φ(β), ψ(β)=1\},$$ ...
1
vote
1answer
41 views

A non-linear optimization problem

I have the following optimization problem on the variables $a_1, ..., a_n$: $$ minimize \frac{\sum_{k=1}^{n}\max(k\cdot a_{k},1)}{\sum_{k=1}^{n}a_{k}} $$ $$ such\ that\ \ 0\leq a_k\leq 1\ \ \ (k=1, ...
0
votes
1answer
82 views

Simplex Algorithm

I'm currently trying to implement the (revised) Simplex Algorithm, but according to my notes the LP in standard form $\left( Ax = b, x \geq 0 \right)$ with $A \in \mathbb R^{m \times n}$ has to have ...
1
vote
0answers
225 views

Constraints of a linear programming problem

QUESTION Sandy Arledge is the program scheduling manager for WCBN‐TV. Sandy would like to plan the schedule of television shows for next Wednesday evening. Of the nine possible one‐half hour ...
6
votes
1answer
380 views

Minimum number of lines covering n points

Let there be n points in the plane. I want to know the minimum number of horizontal and vertical lines covering all the points in the plane. My initial approach started like this, 1) for each point I ...
0
votes
1answer
263 views

Variations of the transportation problem in linear programming

The transportation problem is a famous problem in linear programming. For instance, http://www.utdallas.edu/~scniu/OPRE-6201/documents/TP1-Formulation.pdf or http://www.math.ucla.edu/~tom/LP.pdf ...
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). ...
0
votes
1answer
49 views

Checking whether a solution to MIP is optimal

Consider a binary integer program \begin{align} \min \quad &\sum _{j \in J}f_j x_j +\sum _{i \in I} c_i y_i \notag \\ \mbox{s.t.} \quad &\sum _{j \in N_i} x_j \ge 1-y_i, \quad \forall i\in I ...
4
votes
2answers
56 views

What is an approach for optimizing the values of a matrix?

My apologies if I get some terminology wrong, I don't have a formal math background; half my problem is articulating what I'm trying to do and identifying the domain of math that deals with this kind ...
0
votes
0answers
48 views

Is there an easy solution to this constrained discrete minimisation?

Given $\vec{a}$, $\vec{b}$, and $c$ I want to find a discrete combination $\vec{n}$ (i.e. a vector with non-negative integer elements) to $$\mathrm{minimise}\left(\vec{n}\cdot\vec{a}\right)$$ Under ...
0
votes
1answer
48 views

Optimising profit in responding to offers of customers

I have an linear algebra problem to solve. Currently I have n number of customer lists and m number of offers. I have matrix (P) with dimension m x n. Elements of P indicates probability of ...
0
votes
1answer
108 views

How to solve this minimization (maximization)?

I'm facing this problem: $$ \large \min_{x \in \mathbb{R}_+^3} \max \left\{ { \sum_{i=1}^3 x_i^2-2 x_1 x_3 \over \left(\sum_{i=1}^3 x_i \right)^2} , { \sum_{i=1}^3 x_i^2 + 2 (x_1 x_3 - ...
6
votes
2answers
345 views

How can I, as a future mathematician, contribute most to Smart Grid research?

After I've finished my Master's degree in mathematics, I too want to use my powers for good. One endeavour I consider good is the pursuit of the design and implementation of a Smart Grid which will, ...
2
votes
1answer
235 views

Proof by Contradiction: $100$ Balls & $9$ Boxes

Show, by giving a proof by contradiction, that if $100$ balls are placed in nine boxes, some box contains 12 or more balls. I would like to ask for a hint for this quesiton. Thank you.