21

I was wondering, if there are variations of those in reality such as $O(2n^2)$ or $O(\log (n^2))$, or if those are mathematically incorrect. Yes, $O(2n^2)$ or $O(\log (n^2))$ are valid variations. However, you will see them rarely if you would see them at all, especially in the end results. The reason is that $O(2n^2)$ is $O(n^2)$. Similarly, $O(\log (n^2)...


13

You are always free to not use this notation at all. That is, you can determine a function $f(n)$ as precisely as possible, and then try to improve on that. For example, you might have a sorting algorithm that makes $f(n)$ comparisons, so you could try to come up with another sorting algorithm that only does $g(n)$ comparisons. Of course, all kinds of ...


7

Let’s use $a_i$ for the array. You are interested in $$ \begin{align*} \max_{i,j} a_i + a_j + |i-j| &= \max_{i,j} a_i + a_j + \max(i-j,j-i) \\ &= \max_{i,j} \max((a_i+i)+(a_j-j), (a_j+j)+(a_i-i)) \\ &= \max \left[ \max_{i,j} (a_i+i) + (a_j-j), \max_{i,j} (a_j+j) + (a_i-i) \right] \\ &\stackrel{(*)}= \max_{i,j} (a_i+i) + (a_j-j) \\ &= \...


7

Since Vince asked me to publish my solution, I decided to write this long post. Please bear in mind that this code is really really basic and absolutely not optimized, written as fast as possible to perform some test. Credits for Hungarian algorithm code must be done to vivet. PURPOSE I need to create shifts for M workers (variable number each week) on N ...


7

While the accepted answer is quite good, it still doesn't touch at the real reason why $O(n) = O(2n)$. Big-O Notation describes scalability At its core, Big-O Notation is not a description of how long an algorithm takes to run. Nor is it a description of how many steps, lines of code, or comparisons an algorithm makes. It is most useful when used to ...


6

For the sake of completeness (since Vince has given you good help already, and it seems like you've got a program that works): This is known as the assignment problem: given some set of workers and some set of shifts, where each worker might have preferences about which shifts they take, how can you find the optimal schedule? The standard solution to it is ...


5

You can write $O(f)$ for any function $f$ and it makes perfect sense. As per the definition, $g(n)=O(f(n))$ if there is some constant $c$ such that $g(n)\leq c\,f(n)$ for all large enough $n$. Nothing in that definition says that $f$ must be some sort of "nice" function. But, as other answers have pointed out, $g(n)=O(f(n))$ and $g(n)=O(2f(n))$ ...


5

Your conceptual difficulty stems from not distinguishing between TSP and Weighted Hamiltonian Cycle. These are usually discussed as if they are the same problem, but they're not. In Weighted Hamiltonian Cycle, we are given a graph with nonnegative edge weights and we wish to determine the minimum-weight Hamiltonian cycle, i.e., the minimum-weight cycle that ...


4

You ask for a graph where your (nondeterministic) algorithm gives the optimal solution even in the worst case. We're looking for a set of vertices that cover all edges. The difficulty with your algorithm is not only that it could pick the edges in an "inconvenient" order, but also that it adds both vertices belonging to the edge, which is suboptimal in most ...


4

Using any/all (a.k.a. or/and) gives rise to alternating Turing machines. Goldschlager and Parberry (On the construction of parallel computers from various bases of boolean functions, Theoretical Computer Science 48:43–58, 1986) consider the generalization to allowing arbitrary Boolean functions, and they call the resulting machines extended Turing ...


4

This problem, which I'll call CO for Column Ordering, is NP-hard. Here's a reduction from the NP-hard problem Vertex Cover (VC) to it: Decision problem forms of VC and CO Let the input VC instance be $(V, E, k)$. It represents the question: "Given the graph $(V, E)$, is it possible to choose a set of at most $k$ vertices from $V$ such that every edge in $...


4

You can consider the 1D-position of the 2 runners as one 2D-position. X-coordinate and Y-coordinate for respectively runners 1 and 2. So in your instance, the starting point is (0, 100). Then all the goal points coordiantes can have a 2D-position in the same way, for instance (40, 70). Now the Travelling salesman problem has to be solved using the ...


4

Look at the definition of O(f(n)), and you see that for example O(2n^2) and O(n^2) are exactly the same. Changing an algorithm from 5n^2 to 3n^2 operations is a 40 percent improvement. Changing from O(5n^2) to O(3n^2) isn’t actually any change, they are the same. Again, read the definition of O(f(n)).


4

It may be helpful to understand that Big-O describes a set of functions. That is $O(f(n)) = \lbrace g(n) | \exists n,c>0: \forall m > n: c\times g(m) \le f(m)\rbrace$ The usage of $=$ is kind of unfortunate and using $\in$ would make that relationship a lot clearer. but the set notation symbols are a bit difficult to type so now we are stuck with the ...


3

I am a bit cautious just in case you might be taking part of some kind of open competition or exam. Before I could reasonably believe that you are raising this question in good faith, I will just say I can reach 51 iterations without going to all zeros using less than 18 digits for each number. As an evidence that I do have an answer, here are the last 5 ...


3

$\mathsf{3LIN}$ is the following problem: Given a set of linear equations of the form $x_i \oplus x_j \oplus x_k = b$, where $1 \leq i,j,k \leq n$ and $b$ is a bit, find an assignment for the bits $x_1,\ldots,x_n$ that satisfies the largest number of equations. There is a simple 1/2-approximation algorithm, which simply chooses a random assignment. Such ...


3

Assume that $a$ is given. Then a valid $b$ has to satisfy (just rearrange the inequality) : $$b > \frac{a}{a - 1}$$ Notice, if the array is sorted, then you can find the number of valid $b$ using binary search, which gives $O(n \log n)$ to compute the number of all pairs. Also notice, that if $a$ gets bigger, then $b$ is allowed to be smaller. So if ...


3

Edit: See my answer to the same question on math stackexchange here. I've copy and pasted the answer again for ease of use. There has been a recent line of work investigating algorithms for submodular optimization problems when the objective may take negative values. So far, the non-negativity that we can handle is when the submodular objective decomposes ...


3

I would say that this approach falls under the umbrella of iterative rounding. I believe that the seminal paper regarding this kind of strategy is [1]. The heuristic outlined here differs in signifcant ways from the algorithm described in Jain's paper but I think the basic idea is in the same vein. Jain, K. (2001). A factor 2 approximation algorithm for the ...


3

This is extremely optimistic. The first problem you face is that an approximate smallest grammar will at best help you find strings which occur frequently. It won't distinguish keywords from names, and it won't isolate words. (Note for reference that Lempel-Ziv has a good approximation ratio. Charikar, Lehman, Liu, Panigrahy, Prabhakaran, Sahai, & ...


3

As Vince observes, your problem is TSPP (traveling salesman path problem) on the plane with respect to the $L_\infty$ metric. On the plane, the $L_\infty$ and $L_1$ metrics are equivalent (the unit balls differ by a rotation of $45^\circ$), so your problem is equivalent to TSPP on the plane with respect to the $L_1$ metric. This problem has been addressed on ...


3

The problem is strongly $NP$-complete by reduction from 3-Partition. Given a set of $3n$ integers with total sum $3M$, we want to determine whether they can be partitioned into $n$ triples, each having sum $M$. Note that we can assume that no four integers have sum $\leq M$. Suppose a day is $3M+n-1$ units of time long. We want to visit $n-1$ museums $m_1,\...


2

Hints: The goal is to pick four values from the sequence such that $$\frac{v_j}{v_i}\frac{v_l}{v_k}$$ is maximized. The solution is made of the two ratios that fulfill the order constraint while maximizing the product. The best ratio in an interval is given by the maximum over the minimum, which you can find in time proportional to the interval size. You ...


2

An active learning approach using which combines an incrementally-learned Regression Tree with bandit-style sampling from leaf nodes to determine which instance to request a label for next is described in the “Adapting to Concept Drift in Credit Card Transaction Data Streams Using Contextual Bandits and Decision Trees” paper (disclaimer: I'm an author on the ...


2

Apply the golden rule of DP (that is how I name it), namely, adding another parameter to the subproblems/object function when there is an extra condition or dimension of freedom. This rule is simple and powerful, yet it can be overlooked by DP beginners and sometimes experienced guys. In this particular question, instead of $V(i,w)$, define $V(i,w,c)$, ...


2

In general, this is not possible unless P=NP. So, it is unlikely that such a method exists. Many NP-hard problems can be modeled as an integer program, we take 3SAT for an example. Suppose we are given a 3SAT instance with clauses $C_i$ and variables $v$. For each clause, denote the variables that appear positive by $C_i^+$ and the variables that appear ...


2

Maybe it depends on what it means by solving an optimization problem. If it is to find "how big is the biggest $f(x)$", then the answer is no (see the answer of @David Richerby). If it is to find "the $x$ that maximizes $f(x)$", then consider the function $f(x) = \max_{y\in Y}g(y)$ such that $\max_{y\in Y}g(y)$ is hard to compute. The optimization problem is ...


2

I would solve this problem with an SMT solver like z3. Example in Python: import z3 buckets = [ [(2, 4), (2, 4), (4, 4)], [(1, 1), (2, 4), (13, 15)], ] solver = z3.Optimize() m = z3.Int("m") for bnr, bucket in enumerate(buckets): springs = [] for b, (lo, hi) in enumerate(bucket): include_spring = z3.Bool(f"is{bnr},{b}") ...


2

Let there be $n$ such pairs, and $k$ vertices. Then you can translate this problem into a minimum-cost integer multi-commodity flow problem. The core trick is to encode the minimum intersections by turning each vertex of your original problem into a triplet of vertices in the minimum-cost flow problem, an input node, and output node, and $n$ edges ...


2

For starters I assume that you can't guess the impact the values of a solution have on its fitness, otherwise you could relax the fitness function to roughly estimate which solutions are promising, and try to find a good solution from there. However you do know that similar solutions have a similar fitness, so let's work with that. I would suggest something ...


Only top voted, non community-wiki answers of a minimum length are eligible