Questions tagged [optimization]

Questions about problems that entail selecting the best element from some set of available alternatives, and methods to solve them.

1,199 questions
Filter by
Sorted by
Tagged with
33 views

If value of LP relaxation of s-t minimum cuts is P ,then wen can find a s-t cut at most P edges?

My problem is mainly from this lecture notes on convex optimization here page4 Consider a s-t Minimum problem, on unweighted undirected graph $G=(V,E)$,we can formalize in following linear integer ...
50 views

Interpretation of Backtracking Algorithm Problem - weighted matching

I am attempting to resolve the following problem using Backtracking: Suppose that you have $n$ men and $n$ women and two matrices P y Q (n x n); such that $P_{ij}$ is the preference of the man $i$ ...
4 views

Looking for a specific type of ADMM iterates

For a $k-$dimensional optimization variable $b \in \mathbb{R}^k$ say the objective is given as, $$f(b) = \langle b, v \rangle + \langle b , Ab \rangle + \lambda \Vert b \Vert_1$$ for some parameter ...
431 views

Knapsack problem: equal profits

I am looking for references to efficient algorithms that solve knapsack problem where all profits are equal. More formal definition of the problem from a Wikipedia article on KPs: If all the ...
26 views

32 views

optimize string search on black-box function

Given a lower-bound predicate function which returns true if an input is greater than or equal to a constant string, what is the optimal way to search for the ...
17 views

Finding many different minima of nonlinear cost function

Given a nonlinear cost function $G(\vec{x})$ of many variables, does there exist a method that allows one to find successive local minima $\vec{x}_0, \vec{x}_1, \dots$ so that $\vec{x}_n$ is ...
405 views

Optimal meeting point

I'm interested in studying the problem of the optimal meeting point, which can be described as follow: $n$ individuals who want to gather in a restaurant (for example). They want a fair meeting point ...