general questions about selecting a best element from some set of available alternatives.
3
votes
0answers
29 views
Minimize in polynomial time a super-additive increasing function under linear constraints?
I am looking for references whether this problem can be doable in polynomial time (or other known approximation results):
Let $f$ a super-additive function ($\forall x,y, f(x+y) \geq f(y)+f(y)$),
$$
...
2
votes
0answers
106 views
Proving greedy algorithm is optimal for a scheduling problem
First, the problem discription:
For a sequence of $4n$ tasks, $a_1a_2\dots a_{4n}$, where $a_i\in\{0,1\}\forall i$, put them sequentially to the tail of one of the two initially empty queues of ...
1
vote
0answers
20 views
Optimal additive basis for decomposing/partitioning an integer as a sum of two integers
I'm going to be given a positive integer $z$, and I want to find an optimal basis $B$ that is good for $z$.
A basis $B$ is a multiset of positive integers. The basis $B$ is considered good for $z$ ...
-1
votes
0answers
25 views
A* for utility maximization in path finding [closed]
The A* algorithm is usually implemented in such cases in which the shortest path from a node to another in a graph G has to be found. At each step, the node minimizing
f(n) = g(n) + h(n)
is selected ...
0
votes
0answers
56 views
Application of adiabatic quantum algorithm and quantum annealing algorithm [closed]
I am looking for a paper where the same problem is solved with both the adiabatic quantum algorithm and quantum annealing algorithm along with comparison between their performances. Any one with any ...
-1
votes
0answers
44 views
Instance optimality
Let $A \in \mathcal{A}$ an online algorithm and $\mathcal{A}$ the class of online algorithms. $A$ is defined such that at each step a decision is taken depending on the current context. The context ...
10
votes
0answers
114 views
the largest element of a matrix product
Given two matrices, I'm interested in finding the largest element of their product. I wonder if it's possible to do it significantly faster than the matrix multiplication the solution seems to ...
0
votes
1answer
73 views
Ising spin vs Pauli spin matrices [closed]
Are Ising spins scalar or operators? I am not a condensed matter physicist hence having some confusion. I have learnt about Ising models from adiabatic quantum algorithm papers. For example this ...
4
votes
3answers
187 views
Maximize quadratic function subject to linear constraints
Can one maximize $\sum_i c_i x_i^2$ where the $c_i$ are constants (possibly negative), subject to linear constraints over the $x_i$?
This paper seems to come close to answering "no." They show it is ...
1
vote
0answers
87 views
Quantum annealing vs adiabatic quantum computation
I had this impression that quantum annealing is an optimization technique which may or may not produce exact solutions. On the other hand adiabatic quantum computation always gives exact solutions ...
1
vote
0answers
23 views
Confusion related to minimization of a gaussian likelihood function
I have this confusion related to minimization of gaussian likelihood function. The negative of the log likelihood of gaussian distribution is
$-logdet(Q) + tr(SQ) + \lambda||Q||_{1}$ where Q is the ...
3
votes
0answers
46 views
Closest Vector Problem with sparse basis and target vector
The Closest Vector Problem (and related problems) is random self-reducible and in general is NP-Hard, making it a useful tool in cryptography research and post-quantum public key crypto. For a variety ...
8
votes
0answers
121 views
Expected length of a self-avoiding random walk
We're given an arbitrary graph $G=(V,E)$. A self-avoiding random walk is a random walk such that in each step, a random neighbour which was not previously visited is chosen, if such one exists.
...
1
vote
0answers
42 views
confusion related to the dual of svm
I have a confusion related to the dual of svm
In the main objective function I have
Now to solve the dual of this objective function, I will minimize with respect to the primal variables first to ...
2
votes
0answers
163 views
Confusion related to L1 and L2 svm
I have this confusion related to L1 and L2 svm. It is given in this paper that
The dual problem is given by
$$
min(\alpha) = 1/2*\alpha^T\hat Q\alpha - e^T\alpha
$$
subject to
$$
0 <= \alpha_i ...
1
vote
0answers
70 views
Poly-time Algorithm for Non-Linear Optimization
As we know, linear programming is one of the most basic area of optimization theory, and computing an optimal solution can be excuted within poly-time. My question is about an extention of this ...
2
votes
2answers
207 views
Undecidability of program optimization
A program is an encoded Turing Machine. And a size optimizer of a program is a TM $M_1$ such that:
On any input $M$, $M_1$ outputs $M_{min}$ such that $M_{min}$ is the shortest TM which is ...
3
votes
1answer
155 views
A weighted sorting problem
Given a data matrix $D=[d_1 ... d_N]$, one would like to sort it in terms of rows such that the weighted distance of sorted $d$s to a target vector $y$ is being minimized.
It can be formulated as ...
1
vote
0answers
107 views
What does “no integrality gap” implies?
I'm currently working on a linear time heuristic for the rectangle decomposition of binary matrix. This problem has a polynomial time solution, which in our case it too slow for large scale ...
-2
votes
2answers
146 views
how do you turn an algorithm for a decision problem into an algorithm for an optimization problem?
It is well-known, I believe, that theoretically, in quite a few cases, an algorithm that solves a decision problem can be turned into an algorithm that solves the corresponding optimization problem.
...
2
votes
0answers
62 views
Small area containing large amount of patterns
The problem:
I come across a theoretical problem when designing characters for electron-Beam lithography. Abstractly, given an integer $m$, let $\mathcal{M}$ be the set of $(0,1)$-matrix $A_{p\times ...
3
votes
0answers
102 views
Slightly Faster Exponential Algorithm for Integer Programming with Multi-linear Variables
Integer programing is one of the most narutal optimization tools.
As an analogy of DNF or CNF in the Boolean function theory, we can consider the following equation.
$x_{1}x_{2}x_{3}+$ ...
1
vote
0answers
82 views
What is the shape of cost function of weighted graph matching problem?
According to Umeyama, the weighted graph matching problem can be formulated as
$min_P || PA_GP^T - A_H ||$
s.t. $P$ is a permutation matrix.
where $A_G$ and $A_H$ are n-by-n matrices
If we relax ...
3
votes
0answers
94 views
Existence of complete “asymptotic” optimization problems
Define a function $u:\lbrace 0,1 \rbrace^* \rightarrow \mathbb{R}$ to be an asymptotic optimization problem when the following conditions hold:
There is an algorithm $U$ which computes the first $n$ ...
8
votes
2answers
159 views
Generating interesting combinatorial optimization problems
I'm teaching a course on meta-heuristics and need to generate interesting instances of classic combinatorial problems for the term project. Let's focus on TSP. We are tackling graphs of dimension ...
0
votes
0answers
46 views
Nonmetric TSP and Functional Compleixty Classes
Non-metric TSP that is TSP and some instance is not hold the triangle inequality is NP-hard by gap-reduction method.
Is this general TSP a complete problem in some functional complexity classes ?
...
-1
votes
1answer
136 views
Integer compression
I'm looking to devise a scheme for compressing integers which have a known sampled distribution (they might be clustered around a value, say, or have several areas of differing density). So far, I've ...
2
votes
0answers
70 views
Benchmarks for approximation algorithms
I'm working on a Haskell library for approximation algorithms. In particular, I'm working on Partition, Knapsack, Vertex Cover, and possibly a few others. Of course, I'd like to benchmark my library ...
1
vote
0answers
120 views
Properties of the subgradient method
The subgradient algorithm for minimizing a convex function $f(x)$ is the update rule
$$ x(t+1) = x(t) - \alpha(t) d(t)$$ where $d(t)$ is any subgradient of $f(x)$ at $x(t)$ and
$\alpha(t)$ is a ...
4
votes
1answer
119 views
Splitting line segments with a line
Given is a finite set $S$ of line segments in the plane.
I am interested in finding a line $l$ which splits some segments in $S$ into two, thus yielding a new set of line segments $S'$.
Here ...
5
votes
1answer
130 views
Effective algorithm of searching the “nearest” doubly stochastic matrix
Given a data matrix $D$, is there any effective algorithm to solve the optimization problem
$\min_Q || D - Q ||_F$
such that
$Qe=e$,
$e^TQ=e^T$, and
$Q_{i,j} \geq 0 $ $\forall i,j$,
where ...
6
votes
0answers
114 views
Numerical stability of Simplex method
The simplex algorithm is often treated either within real arithmetic, or in the discrete world with exact computations. However, it seems to be implemented most often with floating-point arithmetic.
...
2
votes
1answer
53 views
Covering only one of two types of objects in a cartesian space using minimum number of rectangles
There is a side problem in my research that I believe should be a known problem. I do not want to spend lots of time on a problem that already has been studied, but I do not have a name for the ...
2
votes
1answer
108 views
NP-complete problems related to Minimizing Variance
I am interested in references to NP-complete problems that involve some non-linear terms (e.g. quadratic terms). So far I am aware of the "Quadratic Assignment problem" and "Quadratic Programming". ...
0
votes
0answers
35 views
Effective algorithm to search for closest vector set under certain constraints
The problem is given a set of data vectors $D = [d_1,d_2,...,d_N]$ and an diagonal weighting matrix $W$, search for vectors $Q = [q_1,q_2,...,q_N]$ that are closest to $[d_1,d_2,...,d_N]$ and at the ...
9
votes
1answer
387 views
Minimum spanning tree over all vertex matchings
I ran into this matching problem for which I am unable to write down a polynomial time algorithm.
Let $P, Q$ be complete weighted graphs with vertex sets $P_V$ and $Q_V$, respectively, where $|P_V| ...
4
votes
1answer
104 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 ...
-6
votes
1answer
106 views
Minimizing edges of an FSM [closed]
There are various well-understood, efficient, and theoretically interesting algorithms to minimize a DFA in terms of states.
Is there research into minimizing based on edges of the FSM?
edit: ...
1
vote
0answers
58 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
204 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 ...
6
votes
1answer
226 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$,
...
10
votes
1answer
223 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
3answers
506 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
232 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
138 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
99 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 ...
1
vote
1answer
222 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}$ ...
0
votes
1answer
315 views
Is quantum annealing faster than simulated annealing/genetic/other state-of-the-art optimization algorithms?
Forgive me wise men for my simple words, for I am but a noob.
There's the idea of quantum annealing being used to solve optimization problems in terms of a QUBO problem for D-Wave's quantum ...
1
vote
1answer
214 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' ...
5
votes
2answers
334 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 ...
