2
votes
0answers
24 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 ...
0
votes
0answers
30 views

Online machine learning algorithm for dynamical system

I have a complex dynamical system which takes input as x1, x2, x3 and gives output as y1, y2, y3. I don't have any mathematical model of the system. x(k) is the present input to the system and y(k) is ...
4
votes
0answers
50 views

Minimizing the distance between points in two sets

Given two sets $A, B\subset \mathbb{N}^2$, each with finite cardinality, what's the most efficient algorithm to compute $\min_{u\in A, v\in B}d(u, v)$ where $d(u,v)$ is the (Euclidean) distance ...
2
votes
1answer
91 views

Sort objects into groups based on group size preference

I have a research question that involves human subjects being sorted into groups before playing a social game. Before sorting, each person decides on their preferred group size, from 1 to n; where n ...
0
votes
0answers
78 views

Create theoretical model for scheduling and allocation problem

I want to create a theoretical model for my scheduling and allocation problem instance, but I'm having some difficulties with a clear definition, since I have slightly different circumstances than the ...
0
votes
1answer
190 views

Integer Linear Programming (ILP): NP-hard vs. NP-complete?

I was thinking about examples where a problem is NP-hard but was not NP-complete and ILP came to mind. It is obviously NP-hard but is it NP-complete? I.e., is it in NP? Given a certificate (the ...
0
votes
0answers
39 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
37 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
487 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 ...
1
vote
1answer
57 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 ...
1
vote
1answer
96 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 ...
10
votes
5answers
707 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
150 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
315 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
81 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 ...
2
votes
1answer
292 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
224 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
1answer
191 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
550 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 ...
3
votes
1answer
4k 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 ...
12
votes
4answers
5k 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
359 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
979 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 ...