Questions tagged [search-problem]
A class of computational problems. Where decision problems call for a yes-or-no answer, search problems are looking for an object satisfying a certain property.
16 questions
33
votes
2
answers
15k
views
Optimization version of decision problems
It is known that each optimization/search problem has an equivalent decision problem. For example the shortest path problem
optimization/search version:
Given an undirected unweighted graph $G =...
bek
11
votes
5
answers
2k
views
Can finding a witness be NP-hard even if we already know there is one?
The common examples of NP-hard problems (clique, 3-SAT, vertex cover, etc.) are of the type where we don't know whether the answer is "yes" or "no" beforehand.
Suppose that we have a problem in which ...
- 385
9
votes
5
answers
19k
views
Minimum number of tree cuts so that each pair of trees alternates between strictly decreasing and strictly increasing
A gardener considers aesthetically appealing gardens in which the tops of sequential physical trees (eg palm trees) are always sequentially going up and down, that is:
...
- 257
7
votes
2
answers
2k
views
Is there any strategy to brute force search?
I don't know how to state it elegantly, but basically, I want to implement a brute force search algorithm, but there are many different ways that I could enumerate through the search space. This ...
- 246
6
votes
4
answers
1k
views
Are there any optimization problems in P whose decision version is hard?
Normally to show that an optimization problem is hard, we show the corresponding decision version of the problem is hard. However, is this sufficient to support the conclusion? Does there exist any ...
- 143
4
votes
1
answer
714
views
Maximize ratio of sums
I have a $2 \times n$ matrix of positive integers, where the elements are denoted by $a_{ij}$ for all $i$ in the set $\{1,2\}$ and for all $j$ in the set $\{1,\ldots,n\}$.
I would like to select a ...
- 1,000
4
votes
1
answer
1k
views
Solving cycle in undirected graph in log space?
Setting
Let:
$$UCYLE = \mathcal \{ <G> ~:~ G \text{ is an undirected graph that contains a simple cycle}\}.$$
My Solution
we show $UCYLE \in L$ by constructing $\mathcal M$ that decides $...
- 215
3
votes
1
answer
170
views
Finding a word that minimizes the sum of squared Hamming distances in a data set of words
Suppose we have a set of words of common length randomly sampled from a dictionary of words; assume you have access to that dictionary. Let $d(x,y)$ be the Hamming distance between words $x$ and $y$. ...
- 143
2
votes
1
answer
669
views
What is the lower bound for finding the third largest in a set of $n$ distinct elements?
What is the lower bound for finding the third largest in a set of $n$ distinct elements?
For the case of finding the second largest, we have the tight lower bound of $n + \lceil \lg n \rceil ...
- 9,711
2
votes
1
answer
233
views
Difference between function and search problems?
I am a bit confused on what the difference between a "function problem" and a "search problem" is.
The specific problem I have been studying is known as End-Of-The-Line:
Given two ...
- 121
1
vote
1
answer
319
views
Efficient algorithms for finding a region in $\mathbf R^2$
This question is an extension of a previous question I've asked.
Consider the rectangle $a<x<b , c<y<d$ in the $\mathbf R^2$ plane. Each point in this rectangle can be of kind #1 or #2 (...
- 147
1
vote
2
answers
1k
views
Difference Between k-center and k-mean/median
I know that k-mean/median is to find a set $F$ that minimize
$$\sum_{i\in C}\min_{j \in F} d(i,j)$$
Where $C$ is set of clients and $F$ set of facilities. (For k-mean you just square the distance).
...
user138945
1
vote
1
answer
559
views
Are there search problems that cannot be written as decision problems?
I'm not sure whether the distinction between decision and search problems has a deeper significance or if it is just concerns the immediate answer to the problem.
Of course, if you have a finite ...
- 133
1
vote
0
answers
66
views
Classification with optional/catchall attributes
Context
Let $S$ be a set of objects, each object $S_k$ containing a set of attributes $A_k\subseteq A$, where $A$ is a global set of attributes. Suppose each attribute $a_k\in A$ can take on integer ...
- 311
1
vote
3
answers
4k
views
What data structure would help find nearby coordinates quickly?
I need to write a program that does the following:
Take an input list of objects whose properties include latitude and longitude to, say, 5 decimal places
Store them in a data structure once
Provide a ...
- 273