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

learn more… | top users | synonyms

-5
votes
1answer
246 views

Attacking TSP via small nonintersecting circuits

Consider the problem of finding smaller "non-intersecting" circuits or paths in graphs embedded in the euclidean plane (visiting all vertices) in the sense of geometric intersections of edges plotted ...
3
votes
1answer
87 views

Questions about Farhi's pre-Adiabatic paper

I have been going through Eddie Farhi's 6-pages long pre-Adiabatic paper, An Analog Analogue of a Digital Quantum Computation. I guess I understand most of the math and physics but I am struggling ...
1
vote
0answers
29 views

Nonlinear optimization using parallel input/output

I have a system that accepts a vector and returns a function value. The goal is to change the elements of the vector such that the function value is minimized using a derivative-free solver, eg. using ...
3
votes
0answers
97 views

Symmetry of optimal solutions to discrete optimization problems

Given a graph, say one wants to find the clique number, independence number, chromatic number, vertex cover number etc., one knows that a solution exists. However if the solution space has more than ...
11
votes
2answers
366 views

Linear time algorithm for finding shifted max

Assume that we are given an array $A[1..n]$ containing nonnegative integers (not necessarily distinct). Let $B$ be $A$ sorted in the nonincreasing order. We want to compute $$m = \max_{i\in [n]} ...
3
votes
1answer
103 views

Approximation algorithms for multicut for special classes of graphs

The multicut problem is the following. Given a graph $G=(V,E)$ with edge costs $c_e$ for edge $e$ and a set of $k$ terminal pairs $\{(s_1,t_1),\ldots,(s_k,t_k)\}$, the objective is to find a set of ...
-3
votes
1answer
96 views

what problem is this? [closed]

I have this instance: Let's say I have two (could be more) friends, one weighing 200 pounds and another weighing 100 pounds; I won a box with 30 chocolates in a contest and I want to divide among ...
-1
votes
1answer
1k views

Program optimization - 90/10 law

I found this "law" somewhere on Wikipedia: In software engineering, it is often a better approximation that 90% of the execution time of a computer program is spent executing 10% of the code ...
5
votes
1answer
123 views

Investigation of Symbol Minimal Context-Free Grammars for the Language $a^n$

Question Given the language $L_n = \{ a^n \}$ for a natural number $n \geq 2$. Is there a symbol minimal context-free grammar $G$ that generates $L_n$ and contains a rule of the form $A \rightarrow ...
2
votes
0answers
167 views

Quadratic Binary Optimization formulation of Steiner Tree problem

can someone point out to me a solution or give advice on how to formulate as efficiently as possible in terms of number of bits the minimum Steiner tree problem as a 0-1 quadratic optimization ...
1
vote
1answer
117 views

Looking for algorithm (or at least name) for this optimization problem

Suppose that we have $n \geq 2$ distinct triplets $t_0, t_1, ..., t_{n-1}$ of real numbers, $t_i = (x_i, l_i, r_i)$. Define $$\Delta(s) = \max_{i, j} \left[ s (x_j - x_i) + (r_j - l_i) \right]$$ The ...
1
vote
0answers
95 views

Why do people like using evolution computing techniques like GA on multi-objective optimisation?

I am new to the field of multi-objective optimisation and I try to find some books to read on this topic. Yet when I search around my library I found there are many books on using evolution computing ...
1
vote
0answers
210 views

Time complexity of clustering based on random walk

What is the time complexity of the following algorithm (from this paper suggested by Zhou) to partition directed graph? Can I use the complexity of eigen vector computation for this purpose? The ...
3
votes
1answer
138 views

Complexity class for Optimization problems over #P functions

Is there any complexity class which contains problems that can be expressed as an optimization over polynomially many #P functions ? i.e: $$\tilde{f}(x) = \text{Max}_{f \in F}f(x)$$ where $f\in\# ...
1
vote
0answers
82 views

Has anybody studied the problem of finding maximal weighted rooted spanning DAGs?

Let G=(V,E) be a directed weighted graph (not necessarily a tournament) and s be a special node of G so that all nodes in G are reachable from s. The problem is to find a subgraph G'=(V,E') of G so ...
0
votes
0answers
152 views

Continuous version of rod cutting

This is an attempt to extend an idea from Computer Science.. the dynamic programming based solution of the rod cutting problem (given a rod of an integral length and an array of prices for each ...
-1
votes
1answer
148 views

Is l1-norm works better that l2-norm in minimization using projection method?

Given a vector of errors $e(x)$ obtained by variable $x$ In the following problem : $min_x || e(x) ||$ Besides the robustness, consider only convergence speed, is it l1 norm works better than l2 ...
0
votes
1answer
115 views

Finding Tours through Near-Hamiltonian Paths?

Say I have a connected graph. I want to find a tour that visits each vertex at least once. It's not always possible, though, for there to be a solution if there is a bridge in the graph. Is there a ...
4
votes
1answer
155 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
123 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 ...
2
votes
0answers
89 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$ ...
11
votes
0answers
162 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 ...
1
vote
1answer
155 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 ...
3
votes
3answers
632 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 ...
0
votes
1answer
2k 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 ...
3
votes
0answers
72 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 ...
10
votes
0answers
167 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
264 views

Confusion related to L1 and L2 svm [closed]

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
1answer
166 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
260 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
188 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
138 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
255 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
69 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
202 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
150 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
126 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
498 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
89 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
304 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
98 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
173 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
139 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
276 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 ...
12
votes
1answer
297 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
59 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
143 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". ...
9
votes
1answer
548 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
137 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
64 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$ ...