New answers tagged optimization
1
I just found the answer myself. In this paper:
Lyle Ramshaw, Robert E. Tarjan (2012). "On minimum-cost assignments in unbalanced bipartite graphs". Technical reports, HP research labs.
in section 5, the authors show that the Hopcroft-Karp algorithm in fact solves the following problem: given an integer $s$, find matchings with $1,\ldots,s$ edges. The ...
4
The problem can be solved in time $\tilde{O}(n^{4/3})$, using several algorithms:
Agarwal, Partitioning arrangements of lines II: Applications.
Chazelle, Cutting hyperplanes for divide-and-conquer.
Matoušek, Range searching with efficient hierarchical cuttings.
There is an essentially matching lower bound due to Erickson, New lower bounds for Hopcroft's ...
1
Your problem is known as maximum coverage.
2
It seems you are confusing the terms minimal and minimum. The Hitting set problem is to find a hitting set of minimum cardinality, not a minimal set.
A set $S$ is called minimal with respect to some property (in this case, being a hitting set) if there exists no strict subset $T$ of $S$ (i.e. $T\subsetneq S$) that also satisfies that property.
On the ...
1
There is no heuristic that is "universal" in practice. Which heuristic works best in practice often depends on the specific problem you're dealing with. There's no one "silver bullet" heuristic that works great on every optimization problem.
0
Your question is not quite clear, but I believe you are asking how to show that 1in3SAT is NP-complete via a reduction from the known NP-complete problem 3SAT.
If this is your question, then consider the following set up, using your notation:
Let an instance of 3SAT be defined by a set of $n$, Boolean variables $V = \{x_1, ..., x_n\}$ and a Boolean equation ...
0
I believe the best algorithm known is Hopcroft and Karp, "An $n^{5/2}$ Algorithm for Maximum Matchings in Bipartite Graphs", SIAM Journal of Computing 2:4 (1973), pp 225-231.
0
During the forward pass, you compute F such that F[i] represents the maximum possible profit when restricting yourself to the elements with indices 0,1..,i.
During the backward pass, you compute B such that B[i] represents the maximum possible profit when restricting yourself to the elements with indices i,i+1,..,n-1 (where n is the size of your list). The ...
1
This statement seems quite vague and confused.
NP-hardness is precisely defined, and you shouldn't loosely say "optimization TSP problems" because it doesn't specify the problem(s). In fact, it is not uncommon that seemingly small changes in a problem lead to different complexities.
Further, because NP-hardness is precisely defined, a problem is not NP-...
0
The question is whether the distances between cities fulfil the triangular equation: For any three A, B and C, is distance (A, B) ≤ distance (A, C) + distance (C, B)?
In your example, where distance (A, B) = 10, distance (C, B) = 1,000,000,000 and distance (X, B) = infinite (or very, very large) for all other X: Yes, it seems that going A->B->A avoids the ...
Top 50 recent answers are included
