# Questions tagged [optimization]

general questions about selecting a best element from some set of available alternatives.

371 questions
Filter by
Sorted by
Tagged with
19 views

### Subset selection with maximum sum and minimum variance? [closed]

So I am trying to tackle a combinatorial optimization problem and would like some insights on how to approach it. The problem statement is as follows: Consider a set of elements of size N, how do I ...
110 views

### Is this homework problem on T-joins wrong? [closed]

In Question 9.3a, it states that if $T=V$, then the minimum cost perfect matching is the minimum cost T-join. Is this actually true? I think I have a counterexample which I have drawn below.
32 views

### Graph-based backjumping vs Conflict-based backjumping comparison in CSP

Graph-based backjumping vs Conflict-based backjumping in CSP I have been studying techniques to find solutions in backtracking to model and solve a problem in c++ with this methods and I have the ...
143 views

### How to calculate complexity in a high dimensional space?

Edit: 'Fitness landscape analysis' was mentioned as a relevant measure. If you're going to downvote the post, at least leave a comment what is wrong. For a specific f(), I'm defining a term '...
98 views

108 views

### Is the matching polytope integral?

In this document https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture9.pdf they prove the integrality of the matching polytope using the integrality of the perfect matching polytope. The ...
100 views

### Where to find info on (polytime) approximability of various discrete optimization problems?

Where to find info on (polytime) approximability of various discrete optimization problems? Sorry if this is stupid,but is there a site or reference that keeps up to date info on approximability of ...
102 views

### Parametrized complexity of sparse optimization

Optimization problems of the type: minimize $c^T x$ subject to [maybe some linear constraints and] $||x||_0\le k$ are known to be NP-hard. [Actually, I just realized that I don't have a reference, so ...
83 views

84 views

### Optimal point placement on integer lattice

What is known about the following point placement problem? For positive integers $N$, $n<N^2$, and $N\times N$ grid $\mathcal{G}$, compute \begin{eqnarray*} \mu_1(N,n)\triangleq\min_{\mathcal{P}\...
49 views

### Tight estimates on the Lovász and Multilinear extensions of a submodular function

I assume here some familiarity with the jargon used in submodular optimization (please let me know if something is unclear). Let $f:2^V \to \mathbb{R}$ be monotone, normalized and submodular. For ...
30 views

63 views

### Complexity of multi-objective optimization problems

How can we define and prove the worst-case complexity of multi-objective optimization problems (MOOP)? It is easy to see that, if one of the objectives is an NP-Hard optimization problem, then the ...
78 views

447 views

### Formalizing and optimizing constraints involving booleans, pairs of booleans, and integer sums

My scenario has various flavors of SAT, constrained quadratic pseudo-Boolean, and integer programming. My attempts to formalize and solve the problem with Z3's ...
146 views

### Sum From A List Of Numbers (Algorithm) [closed]

I came upon a problem and have been trying to find a method more efficient then brute force, but I came up with nothing; and I am not even sure how to approach it... You have a list of numbers and a ...
208 views

### Run Length eXtreme encoded length

In run length encoding (RLE) the code stream consists of pairs $(c_i,\ell_i)$, which is understood as writing the character $c_i$ repeatedly $\ell_i$ times. Consider the following "improvement" of ...
49 views

### AMQ (Bloom-filter like structure) lower bounds

I want an Approximate Member Query structure (that is, something like Bloom filter), but with the highest possible compression ratio. I know that for AMQs where query is done in constant time, the ...
100 views

115 views

### Finding the maximum no. of people who get along in a group [closed]

Suppose that there are 15 people in a room. Assume that each person gets along with other people in the room (but not everyone). (Note that the "feeling is mutual" between any two people who are ...
100 views

### Vehicle scheduling

Suppose there are $n$ resources which can do some work. Each resource has a number of time windows: $tw_{i,k}=\{start_{i, k},stop_{i, k}\}$, such that the resource can perform its functions only ...
84 views

### Problems rephrased as quadratic unconstrained binary optimization

I was impressed when i came across Quadratic unconstrained binary optimization (QUBO) recently, and saw how one can rephrase many combinatorial problems into questions about optima of binary functions....
166 views

### Intuitive explanation behind Goemans-Williamson randomized rounding

A very simple randomized cut algorithm achieves $1/2$ of the optimal value: just choose each vertex to be in the cut with probability $1/2$, independently. Goemans-Williamson does something more ...
130 views

### 3 dimensional matching shortest solution NP-hard?

We have array of arbitrary number of elements - 3d vectors with positive integers components - for example ...
149 views

### Generalizations of linear programming

Linear problems can be solved in polynomial time. So can semidefinite programs and, presumably, many other useful classes of optimization programs. Is there a survey/lecture notes describing ...
98 views

### Bellman-Ford with Non-edge-decomposable Path Weights

Consider a directed graph $G(V,E)$ with non-negative edge weights. Also, let us define the weight of a path as non-edge-decomposable, that is, the weight of a path cannot be written as the sum of a ...