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

learn more… | top users | synonyms

9
votes
0answers
90 views

NP-hardness of approximation for unconstrained submodular maximization

The problem of unconstrained submodular maximization can be phrased as follows: Given a non-negative submodular function $f$ on a domain $D$ find a set $S \subseteq D$ maximizing $f(S)$. Here a ...
0
votes
0answers
27 views

Vector Product in the constrinats on an optimization problem

Can the following optimization problem be solved using Semi-Definite Programming or Linear Programming. We are given a data matrix $A$, which is known. We have the following optimization problem. This ...
3
votes
0answers
119 views

Non-Linear Programming with \min operator in the constraint

Can the following non-linear program be solved in polynomial time? $c_{ij}$'s are constants and known. Each $c_{ij}$ is either -1 or 1. \begin{align} \text{maximize } &\sum_{i,j=1}^{m,n} ...
-2
votes
0answers
51 views

The importance of objective function min and max values in multi-objective optimization by sorting non-dominated fronts

Assume you want to optimize according to some functions. When the relative value of the fitness functions is unknown, multi-objective optimization can be done sorting a list of potential solutions ...
4
votes
1answer
136 views

Positivstellensatz and sum of squares method

This question comes from many online resources that introduce Sum-of-Squares method, such as the survey of Barak and Steurer (http://arxiv.org/abs/1404.5236). Let me focus on Theorem 2.1 of this ...
1
vote
1answer
187 views

Is finding an optimal solution to this Knapsack-like problem NP-hard?

Suppose our inputs are a set of objects with weights $w_1,...,w_n$. We have two separate sets of profits: $p_1,...,p_n$ and $v_1,...,v_n$. We wish to maximize $ \sum_{i=1}^{n} p_i(1-x_i)+\alpha_i ...
0
votes
0answers
36 views

Structural properties of Markov decision processes

My question is about structural properties of Markov decision processes (MDPs). In particular, I am interested in partially observable MDPs, or POMDPs, and what can be said about their optimal ...
0
votes
0answers
22 views

On the Continuous Relaxation of the Quadratic Assignment Problem

Consider the Quadratic Assignment Problem: Minimize $$\sum_{i=1}^n\sum_{j=1}^nc_{ij} x_{ij} + \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^n c_{ijkl}x_{ij}x_{kl}$$ subject to $$\sum_{i=1}^n x_{ij} ...
2
votes
0answers
23 views

Stochastic optimization with erroneous oracles

I am interested in a class of optimization problems of which we know that the input variable is first subjected to noise $\xi$ before entering the data-producing process $f$. I write the objective in ...
5
votes
1answer
126 views

Maximizing a monotone supermodular function s.t. cardinality

I've tried to comb the literature and seen a lot of references to results that almost but don't quite seem to address this. Question: Is it known to be true or is there a hardness result ...
0
votes
0answers
20 views

Optimization of process duration when multiple processes interact

When you have a process composed of multiple steps (e.g., a recipe), where: each step S has a specific duration d(S) steps ...
3
votes
0answers
44 views

First-order methods for solving SDP with geometric convergence or better

Is there any first-order method that can solve general SDP in a geometric (linear) rate? or super-geometric (super-linear) rate?
7
votes
1answer
232 views

Inexact labelled binary tree matching

Does anyone recognise the following problems? Do they have names? Are they hard? If we were looking for an exact match (0 mismatches), these would be solvable in polynomial time (using e.g. standard ...
2
votes
0answers
70 views

How to prove integrality of LP with not totally unimodular matrix

I have a linear program (LP) for which the constraint matrix is NOT totally unimodular (TU). However, even though constraint matrix is small (14x20), extensive generation of random coefficients for ...
1
vote
1answer
74 views

On a Linearization of the Quadratic Assignment Problem

The Quadratic Assignment Problem formulated as an integer program: \begin{align} \mbox{minimize}\quad & \sum_{i=1}^n\sum_{j=1}^nc_{ij} x_{ij} + \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^n ...
0
votes
0answers
87 views

Binary Search for optimisation problems

This maybe is either a question out of place or it is a very elementary one. I wonder what kind of optimization problems can be solved by Binary Search. Looking around some coding competitions, there ...
2
votes
0answers
97 views

Empty sudoku and NP-completeness [closed]

My question is straightforward: Is an empty sudoku grid (not partially completed) still NP-complete?
10
votes
2answers
230 views

Easy to optimize but hard to evaluate

Are there any known natural examples of optimization problems for which it is much easier to produce an optimal solution than to evaluate the quality of a given candidate solution? For the sake of ...
3
votes
0answers
53 views

Quantum annealing or adiabatic quantum optimization with continuous optimization problems

How do quantum annealing or adiabatic quantum optimization deal with continuous optimization problems such as SDP?
1
vote
0answers
127 views

Optimization Problem on a Directed Graph

I have the following graph optimization problem. In a directed graph $G$, each node $i$ is endowed with a real value $v_i$ (input) that encodes the minimum "activation threshold" of that node. For ...
0
votes
0answers
37 views

Integer sublattice of unit hyperplane

Consider the polytope $\mathcal{H}=\{(x_1,\dots,x_n)| \ell_i\leq x_i\leq u_i\; i=1,\dots,n; \sum_{i=1}^n x_i=1\}$ where $\ell_i,u_i\in [0,1]$ for $i=1,\dots,n$. It is easy to see that $\mathcal{H}$ ...
3
votes
0answers
59 views

Pathfinding search over a space with known changing costs

I'm working on a research project which involves iterative pathfinding over a space whose cells have danger values that change over time. More specifically, the danger values represent bad weather, ...
1
vote
0answers
40 views

How to compute the basis

Given $n$ sets of linear constraints $\Theta_1, \cdots, \Theta_n$ which are over $\vec{x}_1, \cdots, \vec{x}_n$ respectively where $\vec{x}_i$ and $\vec{x}_j$ are pairwise disjoint, and $W= ...
6
votes
0answers
86 views

SVM - running time for detecting if data is linearly separable?

If my understanding is correct, one way to check if a set of $m$ data points is linearly separable is to use support vector machines to find a maximum margin hyperlane for separating the data; the ...
1
vote
0answers
20 views

Which matrix of Q values is being used here?

This question refers to this paper: Using Free Energies to Represent Q-values in a Multiagent Reinforcement Learning Task In section 2.1, equations (5) and (6), I am wondering which Q values are ...
0
votes
0answers
145 views

NP-hardness of minimizing sum of complicated objective function

In our research, we faced the following problem optimization problem: Input: a list of $k$ pairs of positive integers $(n_1,d_1), \ldots, (n_k,d_k)$; an integer $m$. Output: $P$, a partition of the ...
4
votes
1answer
71 views

Approximate matching in table of integer vectors

Disclaimer: This is my first question on cstheory.stackexchange.com so please be forgiving. I have a list of M (M is big, more than 1 million elements) vectors of integers. Each vector can contain ...
4
votes
1answer
170 views

What do you call the join of two optimization problems?

I have two optimization problems, both of whose inputs are from the set $I$ and whose solutions are from the set $S$, one a minimization with objective function $m_{\min}$ and one a maximization with ...
4
votes
1answer
104 views

Minimum weight matching in general graphs with additional input specifying the number of matched edges

We know of the minimum weight perfect matching problem in general graphs which can be solved using a primal-dual algorithm. Assume, we have an additional constraint specifying the exact number of ...
3
votes
2answers
806 views

Finding the two shortest paths while minimizing the number of nearby/common edges

The shortest path problem between 2 arbitrary nodes is one that has been covered extensively and the solution is well-known. Consider the edge costs to be arbitrary. Consider the following variant: ...
5
votes
0answers
114 views

Completing a matrix (over the reals) to be singular

Consider the following problem: you are given a matrix (say, with rational entries) some of whose entries are actually left blank; can these blanks be filled in with real numbers so that the resulting ...
5
votes
2answers
218 views

What are some of the most ingenious linear programs developed for tackling hard combinatorial problems?

What are some known ingenious linear programs that have been developed for tackling hard combinatorial optimization problems, especially any linear programs which had helped in getting good ...
3
votes
0answers
96 views

NP-hardness of a quadratic programming problem

Motivated by the mean-variance optimization, I came up with the following question: Given $n$ integers $a_1, \cdots, a_n$; $n$ lower bounds $0<\ell_1, \cdots, \ell_n<1$ $n$ upper bounds ...
0
votes
2answers
110 views

Finding a set of hubs in a graph

Suppose, we are given a graph $G = (V,E,d)$, where $V$ is the set of vertices, $E$ is the set of edges, and $d$ is a distance function $d: E \mapsto \mathbb{R^+}$. Let $S$ be the set of source ...
1
vote
1answer
177 views

NP-Hardness for an optimization problem

I want to prove that the following optimization problem is NP-Hard. max $\prod_{i = 1}^{N} \frac{\left[\sum_{j =1}^M x_j \mathcal{R}_{ij}\right]^2}{ \sum_{j=1}^M x_j}$ subject to $x_j \in ...
0
votes
1answer
95 views

TSP heuristics for limited distance information

this is my first question on Theoretical CS. :) I've posted a similiar question on Mathoverflow and a friendly user advised me to post my question on this site. Problem: I'm looking for TSP ...
11
votes
0answers
249 views

How good is greedy in average?

Given a family ${\cal F}\subset 2^E$ of (feasible solutions), the maximization problem on ${\cal F}$ is, for every weighting $x:E\to \{0,1,\ldots\}$ of ground elements, to compute the maximum weight ...
0
votes
0answers
210 views

How to solve such a graph optimization problem?

I have a graph optimization problem which is hard to describe in the title. There is a component based system which consists of components and data transmissions between components(components and ...
5
votes
1answer
115 views

Is computing the dual optimum of a degenerate LP equivalent in complexity to solving LP?

Given a primal LP and an optimum solution thereof, it is well-known that complementary slackness conditions [1] can be used in non-degenerate cases to produce a dual optimum solution. For instance, ...
2
votes
0answers
134 views

Complexity: simulated annealing vs. quantum annealing

How do I compare the performance of simulated annealing against the performance of quantum annealing algorithms? In Convergence theorems for quantum annealing by Morita and Nishimori, it has been ...
2
votes
0answers
117 views

Dynamical systems analysis of deep learning

I am interested in finding out references that apply dynamical systems analysis to develop the "theory" of deep learning, specifically (say) feedforward deep neural nets. The only paper I seem to have ...
2
votes
0answers
101 views

Is minimizing sum of distances hard?

The Problem Given a set of $n$ points $S = \{v_1, v_2, \cdots, v_n\} \subset \Re^d$, find a unit vector $s \in \Re^d$ such that $s$ minimizes $$ \sum_{i=1}^{n}\sqrt{\|v_i\|^2 - \langle v_i, s ...
13
votes
1answer
247 views

Second Smallest $s$-$t$-Cut in a Network

Is anything known about the second smallest $s$-$t$-cut in a flow network? Or, more general, about this problem: Input: A network $N$ and a number $k$, all in binary. Output: A $k$th smallest ...
9
votes
1answer
328 views

Is the complexity of this covering problem known?

Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...
25
votes
5answers
4k views

Is it a rule that discrete problems are NP-hard and continuous problems are not?

In my computer science education, I increasingly notice that most discrete problems are NP-complete (at least), whereas optimizing continuous problems is almost always easily achievable, usually ...
11
votes
1answer
419 views

Numerical precision in sum-of-squares method?

I have been reading a bit about the sum-of-squares method (SOS) from the survey of Barak & Steurer and the lecture notes of Barak. In both cases they sweep issues of numerical accuracy under the ...
8
votes
2answers
149 views

Reordering data to optimize for compression?

Are there any algorithms for reordering data to optimize for compression? I understand this is specific to the data and the compression algorithm, but is there a word for this topic? Where can I ...
5
votes
0answers
98 views

Optimizing over symmetric polynomials [closed]

Consider the following constraint satisfaction problem: Let $\alpha_1 , \ldots, \alpha_k \in \mathbb{R}$ be given as well as an error parameter $\epsilon$. Find $p_1, \ldots, p_n$ such that (i) $0 ...
4
votes
2answers
468 views

Good algorithms to solve ATSP

What are some good neighborhood-based local search algorithms or strategies to solve the Asymmetric TSP ? I see many 2-OPT and K-opt based algorithms (e.g. Lin-Kernighan implementations), but I think ...
2
votes
1answer
111 views

Is there a name for this Assignment definition

The standard Assignment Problem asks for an optimal one-to-one assignment between agents and tasks. Now consider the following generalization: Instead of specifying a cost of a single agent-task ...