Tagged Questions

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

learn more… | top users | synonyms

4
votes
1answer
134 views

Nearly-Eulerian Tours

The Eulerian Tour problem is of course a well-studied classical problem in graph theory (Wikipedia article). This question concerns non-Eulerian graphs; i.e., graphs that contain one or more ...
1
vote
0answers
63 views

Can I apply the constraint while constructing the Lagrangian?

Consider the problem: $\min_X ||XAX^T||_F$ s.t. $X^TX=I$ If A and X are real matrices, the lagrangian will be $tr(XAX^TXA^TX^T)+\sum_i\alpha_i(x_i^Tx_i-1)+\sum_i\sum_{j\neq i}\beta_{ij} q_i^Tq_j$ ...
3
votes
1answer
245 views

Stochastic version of a strongly NP-Complete problem

Does a strongly NP-Complete problem remain strongly NP-Complete if the variable set on which the objective/cost function depends are made stochastic ? The problem Tree CVRP(Capacitated Vehicle ...
7
votes
1answer
281 views

NP-hardness of an optimization problem

While studying a problem in algorithmic game theory I got interested in the complexity of the following optimization question: Problem Given: ground set $U = [n] = \{1,\ldots,n\}$ given by $n$, ...
11
votes
1answer
317 views

Exact algorithms for non-convex quadratic programming

This question is about quadratic programming problems with box constraints (box-QP), i.e., optimisation problems of the form minimise $f(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{c}^T ...
13
votes
2answers
774 views

0-1 Linear Programming: computing the Optimal Formulation

Consider the $n$ dimensional space $\{0,1\}^n$, and let $c$ be a linear constraint of the form $a_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq k$, where $a_i \in \mathbb{R}$, $x_i \in ...
5
votes
0answers
345 views

Which problems in graph theory can be stated as quadratic programs?

There seem to be many very interesting problems in graph theory that can be written in the form of maximizing/minimizing a quadratic form on either the Adjacency ${\bf A}$ or the Laplacian matrix ...
5
votes
1answer
207 views

Splitting a graph into minimum number of subpaths

I have an ordinary weighted graph. I need to traverse every edge in the graph at least once. BUT I must do it in subpaths of maximum length L. Those subpaths need not be connected to each other. There ...
1
vote
0answers
125 views

Trace minimization with an orthogonality constraint

For positive semi-definite matrices $A,B$, how can I find an $X$ that minimizes $\text{Trace}(AX^TBX$) under the constraint: that $X$ is orthogonal. All the matrices have real entries and $A,B$ are ...
2
votes
1answer
646 views

Difference between weak duality and strong duality?

For an optimization problem $(P)$ and its dual $(D)$, I have read about two concepts: Weak Duality, and strong Duality. What I don't understand is how they are different: Weak duality: If $\bar{x}$ ...
2
votes
1answer
729 views

Is quantum annealing faster than simulated annealing/genetic/other state-of-the-art optimization algorithms?

There's the idea of quantum annealing being used to solve optimization problems in terms of a QUBO problem for D-Wave's quantum algorithm. I understand that the advantage of quantum annealing as ...
2
votes
1answer
601 views

What are some good references for mathematical optimization for the layman?

I've been getting myself involved with this topic and would like to read more to gain a conceptual understanding of the various techniques and what each one is trying to achieve and their 'idea' ...
7
votes
2answers
582 views

How/Why are linear systems so crucial to computer science?

I've begun to get involved with Mathematical Optimization quite recently and am loving it. It seems a lot of optimization problems can be easily expressed and solved as linear programs (e.g. network ...
3
votes
1answer
269 views

Is this multiprocessor scheduling problem with overlaps NP-Hard?

The problem statement is: "Given a set $J$ of jobs where job $J_i$ has length $L_i$ and a number of processors $m$, jobs have inter-overlapping (For example, if job $J_i$ and $J_k$ are assigned to the ...
8
votes
1answer
226 views

Maximizing a submodular function of two sets with different size constraints

I have two totally distinct domains (apples and oranges) and I have a function $f$ that takes a set of objects from the first domain and a set of objects from the second domain and returns a real ...
2
votes
0answers
190 views

Maximizing a convex function where the objective function is separable but the search space is not

The problem statement is Given convex functions $f_i$ over $X$, find $$\arg\max_{x\in X} \sum_i f_i(x)$$ Does this kind of problem structure allow one to use specific strategies to solve the ...
1
vote
1answer
494 views

Vehicle routing problem over Manhattan distances

I am looking for references to the variant of the vehicle routing problem over Manhattan distance metric where the aim is to optimize the number of tours starting at the depot. Is the following ...
5
votes
1answer
571 views

Implementation that solves minimum set cover

Does anyone know of any tools that solve the approximate minimum set cover problem? I know of the greedy algorithm (which is straightforward to implement myself), but I've also been reading about ...
1
vote
0answers
234 views

Optimizing along a cube $s=\{0,1\}^n$

I am doing an optimization on a n-dimensional cube. That means that every solution is a set of $0$ and $1$, hence $s=\{0,1\}^n$. Most optimization algorithms though need a differential to work. E.g. ...
4
votes
0answers
606 views

Can the Hungarian method be used with real edge weights?

I had a problem where I need to apply bipartite weighted matching on a graph where the edge weights are real (positive and negative). I have looked at several implementations of the Hungarian method ...
0
votes
1answer
301 views

To what extent is it possible to use genetic algorithms to make wind mill turbine blades more efficient?

I recently watched this video on youtube. It featured someone explaining how he used genetic algorithms to improve the efficiency of wind mill turbines by finding the optimal shape for the blades. ...
5
votes
0answers
162 views

Maximizing difference of a submodular and a modular function

I'm considering a network planning problem which is stated as follows: From the given ground set $\mathcal{V}$, select $\mathcal{A} \subseteq \mathcal{V}$ such that \begin{equation} f(\mathcal{A}) - ...
3
votes
3answers
238 views

Facility location problem with a cost function

I'm struggling with a facility location problem. In its original form the problem is quite straightforward: Given a matrix of distances between cities, I have to pick a minimal number of centers from ...
3
votes
1answer
386 views

Maximizing a convex function with linear constraints

I have the following optimization problem: $$ \arg\max_{\{\phi_p\}_{p=1}^M}\sum_{i=1}^N \max_{p=1,\ldots,M}\{\phi_p a_{ip}\} \mbox{ such that }\sum_{p}\phi_p\leq 1\mbox{ and }0\leq \phi_p\leq ...
25
votes
3answers
805 views

Rounding to minimise the sum of errors in pairwise distances

What is known about the complexity of the following problem: Given: rational numbers $x_1 < x_2 < \dotso < x_n$. Output: integers $y_1 \le y_2 \le \dotso \le y_n$. Objective: minimise ...
-5
votes
1answer
239 views

Solving a system of linear inequations

Consider the following system of inequalities: $Ax=b$; $x\geq 0$; A is a $m\times n$ (non-square) and sparse matrix in which some part of entries are rational. a) How feasibility of this system can ...
0
votes
1answer
187 views

Boyd & Vandenberghe, question 2.31(d). Stuck on simple problem regarding interior of a dual cone

In Boyd & Vandenberghe's "Convex Optimization", question 2.31(d) asks to prove that the interior of the dual cone $K^*$ is equal to (1) $\text{int } K^* = \{ z \mid z^\top x > 0 $ for all $ x ...
0
votes
0answers
88 views

Control optimization for a black box model

Computer science is not my major, hence my question is two folded : how is defined the problem I have (if I can name it, it will be easier for me to look for references) ? what kind algorithm would ...
14
votes
1answer
446 views

Does zero integrality gap imply zero duality gap for certain problems?

We know that if the gap between the values of an integer program and its dual (the "duality gap") is zero, then the linear programming relaxations of the integer program and the dual of the ...
0
votes
1answer
210 views

putting objects in buckets — optimization problem

Let $\mathcal B$ and $\mathcal O$ denote finite sets ("buckets" and "objects", respectively) and let $$ E: \mathcal O \times \mathcal B \to \mathbb{R}_{>= 0} $$ be a function. Is there an ...
4
votes
1answer
197 views

Algorithms for Interval Coloring with Capacities and Demands

We are given a graph $G = (V,E)$, where each edge $e \in E$ has a capacity $c_e$. There are a set of $k$ requests $R_1,\ldots,R_k$. Request $R_i$ has a demand $d_i$, and has an interval $I_i = ...
8
votes
2answers
335 views

Hardest optimization problems in NC

When learning optimization problems, we usually consider linear programming (or more generally: convex optimization) as the simplest example. It is solvable in polynomial time, and has relatively easy ...
5
votes
1answer
241 views

Is it possible to include an optimization algorithm's own running time in the cost?

Fix $f(\_; \_)$, which represents a class of optimization problems, ie, for a specific $P$, $f(\_; P)$ is a function we'd like to optimize. Now, we have an algorithm $A$ that takes as input $P, a, ...
0
votes
1answer
119 views

Name of the problem to find the maximum number of characters covered by a set of strings

I am interested in the following problem. One has two collections $Q$ and $T$ of strings, and a set $A$ of alignments of strings in $Q$ to strings in $T$. I want to find a subset $A'$ of $A$ that (i) ...
10
votes
3answers
289 views

min hitting set of every base of a matroid

We are given a matroid. Our goal is to find a set of elements of minimum size that has non-empty intersection with every base of the matroid. Is the problem studied before? Is it in P? For example, ...
0
votes
1answer
187 views

PH and Optimization Problems

If we have a machine which can solve any problem in the second level of PH, can this machine solve optimization problems which is generalized version of NP-complete problems such as MAX-CLIQUE or ...
3
votes
0answers
308 views

Minimal context-free Grammar for a special one-letter Language

For natural numbers $n \geq 5$, $m \geq 2^{n-2} + 1$ the following context-free language is given: $$ L_{n,m} = \{ a^i | 2 \leq i \leq m \} \setminus \{a^{2^i}|2 \leq i \leq n-2\} $$ Find and ...
9
votes
2answers
312 views

A variation on discrepancy involving random graphs

Suppose we have a graph on $n$ nodes. We would like to assign to each node either a $+1$ or a $−1$. Call this a configuration $\sigma \in \{+1,−1\}^n$. The number of $+1$s that we have to assign is ...
14
votes
2answers
337 views

Complexity of optimization over unitary group

What is the computational complexity of optimizing various functions over the unitary group $\mathcal{U}(n)$? A typical task, arising often in quantum information theory, would be maximizing a ...
1
vote
1answer
526 views

Primal vs dual decomposition methods

I noticed that dual decomposition methods tend to be preferred over primal ones in the large scale optimization literature (here are some examples: (1), (2)). The reason seems to be, from what I ...
3
votes
1answer
224 views

Minimum length walk from s to t covering a subset of vertices

I want to find the current literature for the following problem (I have searched on google/asked friends/some Profs didn't get much useful results yet): Input: weighted undirected graph G = (V,E), ...
5
votes
1answer
908 views

Optimality of Greedy algorithm for minimization Knapsack Problem

Given items with weight $w_i$ and profits $p_i$, minimization Knapsack problem is to pick a subset of items $I$, s.t. $\sum_{i\in{I}}{w_i} \geq W$ and $\sum_{i\in{I}}{p_i}$ is minimized. The greedy ...
0
votes
1answer
684 views

Linear Programming with Modulo Linear Constraints

Given $G = (V,E)$ I can formulate a relaxation of graph $K$-coloring as: find feasible point s.t. $\min \sum_{ij}v_{ij}$ for all $(i,j)$ in $E$ $z_{ij} \le (c_i - c_j) \bmod k$ (i) $z_{ij} \le ...
4
votes
1answer
126 views

Minimum ($\ell_1$ or $\ell_2$) norm of sum of edge length in multigraph over linear ordering of vertices

Suppose we have a multigraph with vertex set $V$ where for each $v \in V$, $d_v > 0$ is the diameter of the vertex. We want to put a linear ordering on the set of vertices such it minimizes ($L_1$ ...
21
votes
3answers
777 views

Clique problem on fixed graphs

As we know, the $k$-clique function $CLIQUE(n,k)$ takes a (spanning) subgraph $G\subseteq K_n$ of a complete $n$-vertex graph $K_n$, and outputs $1$ iff $G$ contains a $k$-clique. Variables in this ...
8
votes
1answer
973 views

computing the minimal NFA for a DFA

Many years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question, as opposed to the vice versa direction which has been known ...
1
vote
1answer
175 views

Distribution of variable sized images/boxes(only aspect ratio given) on a 2D area

I'm trying to find a solution for the following problem. You have a set of pictures or let us assume they are just boxes with a given aspect ratio. And you have a two-dimensional area with width and ...
6
votes
2answers
526 views

machine learning for code and compiler optimization?

I am looking into ML for generating more efficient code (i.e. compile time and run time heuristics). I have a phd (compilers, hpc), but very little ML experience. I would appreciate any references ...
2
votes
2answers
407 views

Is the following optimization problem NP-hard?

Set S, which is an non-empty finite subset of $\{ (i,j) : i, j \in N \land i \neq j \}$, is given. E.g. $S=\{(1,3), (2,3), (1,4), (2,4), (3,1), (3,4)\}$ . For each element $(i,j)$, we have weight ...
1
vote
0answers
180 views

Minimization on a binary matrix

Assume you are given a matrix $$ X= \begin{bmatrix} x_1^1 & x_1^2 & \dots & x_1^m \\ x_2^1 & x_2^2 & \dots & x_2^m \\ \vdots & \vdots & \ddots & \vdots \\ ...