Tagged Questions

0
votes
0answers
18 views

Questions about the Bresenham Line Algorithim?

For my AP Computer Science class we had to write a code illustrating the effectiveness of Bresenham Algorithm, an optimization type problem. I have some questions about the algorithm. Let us say ...
1
vote
1answer
23 views

Dynamic Programming Trouble, Optimizing time

A robot goes from terminal to terminal collecting bolts. The robot needs to collect at least $m$ bolts and there are $n$ terminals. Terminal $i$ gives the robot a certain number of bolts denoted by ...
4
votes
1answer
149 views

Optimal Yahtzee (Dice roll) decisions: Probability and weighting choices

I'm a senior in computer science, and I have a hobby of taking on little projects that I find interesting. My current one is a Yahtzee optimal play solver. One would enter their current roll, and it ...
0
votes
1answer
37 views

Knapsack-like problem

I need to express an integer $n$ as the sum of integers $x_i$ below some threshold $t$, minimizing the number of $x$s, and maximizing a lower threshold $q$. $$\min_{\# x} \max_{q} : \sum_i x_i = n ...
0
votes
0answers
37 views

Generalization of many-values logic minimization

What approaches of ternary and many-valued logic minimization algorithms (for example, Quine–McCluskey or Karnaugh map) are exists?
1
vote
1answer
71 views

Hausdorff-like distance between two arrays

Let $(X,d)$ be a metric space and $a,b\in X^n$ be two arrays of elements of $X$. Define $$ \rho(a,b):=\inf\limits_{\sigma\in \Sigma}\sup\limits_{1\leq i\leq n}d(a_i,b_{\sigma(i)}) $$ where the ...
0
votes
0answers
77 views

2D Correlation Optimized Warping algorithm (COW) - dynamic programming

I have read this paper about correlation optimized warping algorithm for time series (or here chromatograms) alignment. Level of detail is not sufficient regarding implementation of optimization ...
10
votes
5answers
418 views

Why is convexity more important than quasi-convexity in optimization?

In the mathematical optimization literature it is common to distinguish problems according to whether or not they are convex. The reason seems to be that convex problems are guaranteed to have ...
2
votes
1answer
123 views

Longest cycle containing two nodes

We're given a directed unweighted graph $G = (V, E)$, with $|V| \leq 100$. The purpose of this problem is to find the longest cycle containing the two nodes $a$ and $b$. Only the length of that cycle ...
3
votes
1answer
218 views

How shall I understand this simple example of No Free Lunch theorem?

I have trouble in understanding a simple example following No Free Lunch theorem in James Spall's Introduction to stochastic search and optimization: My understanding is that a cost function is a ...
3
votes
0answers
61 views

Existence of a general-purpose (almost) universal optimization strategy

From Wikipedia about interpretations of no free lunch theorem A conventional, but not entirely accurate, interpretation of the NFL results is that "a general-purpose universal optimization ...
1
vote
1answer
280 views

Understanding no free lunch theorem

From Wikipedia: $Y^X$ is the set of all objective functions $f$:$X$→$Y$, where $X$ is a finite solution space and $Y$ is a finite poset. The set of all permutations of $X$ is $J$. A random ...
3
votes
1answer
155 views

What is the complexity of computing the minimum distance between two convex polyhedra that both have $n$ faces?

EDIT: (in response to what deinst said) sometimes using a sledgehammer for some menial task is rather convenient - especially if it also has the complexity $O(n)$ (which is what my question is about) ...
2
votes
0answers
160 views

Approximate Set Cover Problem by Rounding

Here is the simple algorithm for approximating set cover problem using rounding: Algorithm 14.1 (Set cover via LP-rounding) Find an optimal solution to the LP-relaxation. Pick all sets ...
2
votes
1answer
342 views

Greedy Algorithm Proof

My problem seems similar to the Interval Scheduling problem (processing as many jobs as possible), which I understand but can't seem to apply properly in this case. I've tried to simplify the problem ...
1
vote
1answer
2k views

Degeneracy in Linear Programming

Consider the standard form polyhedron, and assume that the rows of the matrix A are linearly independent. $$ \left \{ x | Ax = b, x \geq 0 \right \} $$ (a) Suppose that two different bases lead to ...
9
votes
4answers
3k views

Do dynamic programming and greedy algorithms solve the same type of problems?

I wonder if dynamic programming and greedy algorithms solve the same type of problems, either accurately or approximately? Specifically, As far as I know, the type of problems that dynamic ...
3
votes
1answer
326 views

pickup and delivery driver problem

Let's assume food delivery for multiple restaurants (say 20). There are (say 10) drivers available. Further, let's say we get 100 orders over a 4 hour period to deliver food from these restaurants to ...
6
votes
3answers
893 views

What is linear programming?

I asked this question on Stack Overflow but it was closed as "not programming related". So I think this is probably the best place for it... I read over the wikipedia article, but it seems to be ...