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.

Filter by
Sorted by
Tagged with
30
votes
2answers
10k 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 ...
11
votes
5answers
973 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 ...
6
votes
3answers
8k views

Minimum number of tree cuts so that each pair of trees alternates between strictly decreasing and strictly increasing

A gardener consider aesthetically appealing gardens in which the tops of sequential physical trees (eg palm trees) are always sequentially going up and down, that is: ...
7
votes
2answers
1k 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 ...
4
votes
1answer
471 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 ...
3
votes
1answer
913 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 $...
2
votes
1answer
309 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 \...
1
vote
0answers
34 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 ...
1
vote
3answers
2k 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 ...
1
vote
1answer
222 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 (...