Questions tagged [optimization]

Questions about problems that entail selecting the best element from some set of available alternatives, and methods to solve them.

Filter by
Sorted by
Tagged with
-1
votes
1answer
29 views

Finding the count of 0's bounded by all 1's

Given N * M 2-D matrix find out all the 0's which are completely bounded by the all 1's. ( This is not any online platform question ) (This problem statement I faced during an interview). Sub-matrix ...
0
votes
1answer
17 views

simple question about epsilon and estimation turing machines

i am getting really confused by it. i got to a point i had to calculate the lim when $n \rightarrow \infty$ for an optimization problem, and i got to the point that i had to calculate a fairly simple ...
0
votes
1answer
19 views

Minimum total waiting time for arrivals/durations

I have come up with the following problem, and cannot seem to find an effective way of solving it: Consider $n$ clients arriving at a service point at time moments $\{a_i\}_{i=1}^n$ whose duration ...
0
votes
0answers
14 views

Exploding gradients problem in gradient descent in multi-output ridge regression setting [closed]

Multi-output ridge regression: $W^{*}=\underset{W}{\arg \min } \frac{1}{\mathcal{N}}\|Y-WX\|_{F}^{2}+\lambda\|W\|_{F}^{2}$ There are $Q$ outputs, $N$ samples, and $P$ covariates (features). $\hat{Y}...
1
vote
1answer
42 views

Is there a defined set of steps or principles on how to reduce time complexity of algorithms?

I have been watching some big (Google, Facebook,..) company interview examples and usually when pair programming, they develop the most straightforward algorithm and then the interviewer asks 'could ...
0
votes
0answers
14 views

Duplicate dominating parents when using Deterministic Crowding in Genetic Algorithm

This is the pseudocode for using deterministic crowding: ...
1
vote
0answers
20 views

Find an algorithm to fully consume items with criteria and produce minimal result

So here are the prerequisites: There are items to be consumed. Consider an item is just an object with a bunch of properties (e.g. size, weight), and there are tens or hundreds of properties. Items ...
0
votes
1answer
37 views

Integer Linear programming formulation if then condition

I want to create constraints such that I can implement the following condition: Let A be an integer variable >= 0 with an upper bound of 12 I want to introduce the following variable B also an ...
0
votes
1answer
20 views

Bin Packing variant

I am currently struggling with a bin packing variant, where we have fuel and compartments of a tank truck. Some industry constraints apply, but the whole picture is that you must fit the total volume ...
0
votes
2answers
33 views

Approach for algorithm to find closest 3-D object in a list of many similar objects to a given test case

Lets say I have a list of many (10s of thousands - millions) objects, and each of these objects has a given number of 3-D vertices (my current implementation uses 8 vertices each, but this number can ...
4
votes
1answer
100 views

Minimizing total distance traveled by points in points cloud transformation

I have a point cloud of size n (in the example on picture n = 5). The starting coordinates are in green, destination coordinates are in red. What I need is to move the points from the starting ...
0
votes
0answers
64 views

Making Candies - HackerRank question - proof of optimality of a greedy approach

I stumbled across this question in HackerRank: Karl loves playing games on social networking sites. His current favorite is CandyMaker, where the goal is to make candies. Karl just started a ...
1
vote
1answer
22 views

Do we understand when metaheuristics are optimal? (gradient descent & simulated annealing in particular)

Gradient descent sometimes works better than simulated annealing and vice versa. Are there conditions under which we can prove that, given perhaps a restriction on the set of allowed algorithms, one ...
1
vote
1answer
45 views

Given an array with N elements and an array of N indices find the lowest possible amounts of swaps [duplicate]

So I have two arrays $d$ and $s$ with size $n \in \mathbb{N}$. Array $d$ contains the elements and array $s$ contains indices. Array $s$ contains all numbers from $0$ upto $n$ with no duplicates. The ...
-1
votes
0answers
13 views

Difference between the north-west corner method and Vogel Approximation Method

The North-west Corner Method returns $z = 5425$. The Vogel Approximation Method returns $z = 4525$. Which is correct?
0
votes
0answers
11 views

Is there any case that using pipeline reduces throughput?

We know that one of the ways to make implementation more efficient is to use pipeline which is to process new data before completely finishing the previous ones. I want to know is there any case that ...
1
vote
1answer
56 views

Mutli-Path Collision Avoidance

I need an algorithm which can do the following: Given some finite number of particles (circles) each with the same radius, and a list of prescribed points for each particle, find paths in $\mathbb{...
-1
votes
0answers
16 views

Whats the name of the library for dynamically choosing a sorting algorithm?

I got tired of googling for it, IIRC Facebook or Google created a library that explored the data before deciding which algorithm to use, I thought it was called F15 or something. it made some insights ...
3
votes
0answers
77 views

Order the vertices to maximize the weights of edges in the induced subgraph

I have a complete directed graph $G:=(V,E)$ with directed edge weights $c_{ij}$ for every distinct nodes $i$ and $j$. Goal: Find the topological order such that the smallest edge weight of the ...
-1
votes
0answers
43 views

Among the following which all affects the processing power, considering one at a time?

1. Data bus capability 2. Addressing scheme 3. Clock speed Keeping " Data bus capability " and " Clock speed " as constant or fixed, If we manipulate the ...
0
votes
0answers
15 views

Maximizing a sequence of items under order and pairwise restriction

Suppose I have a number of items $\{A ... Z$} which are ordered accordingly. Each item has an associated weight, for example $W_A$. Between all items, there's a criterion $c$ which determines whether ...
0
votes
0answers
28 views

Artificial ant colony algorithm for graph

let's assume we have ant at node $1$ and she has $\{2,3,4\}$ vertices. How do I compute which one she choose? I mean if the formula $p_{ij}(k)$ is the probability of $k$-th ant at node $i$ choose $j$ ...
0
votes
0answers
51 views

How to maximize $f$ while minimizing $g$ at the same time?

Lately, I have been dealing with a problem that I didn't know how to name it to solve it properly. The problem is as follow: let's assume that we have a set of elements $A$. And, we have two ...
0
votes
0answers
14 views

Relation between shape descriptors and featured connected component in matching problems

Hope I'm asking in the correct community, from the title, I need a clarification regarding the idea of dealing with 3d descriptor and featured connected components. I have this approach: model -> ...
1
vote
0answers
24 views

Looking for some references on voting theory

After reading through this paper on optimizing the sum of sigmoid functions, http://www.web.stanford.edu/~boyd/papers/pdf/max_sum_sigmoids.pdf, I am interested in the problem addressed in section 7.3 ...
2
votes
1answer
50 views

Encoding set of At-Most-One constraints as a MAX-SAT problem

Assume a set of variable $V$ = $\{v_1,...,v_m\}$. Given total $n$ at-most-one (AMO) constraints (at most one element in a given set is true) set [of the below form], over the variable set $V$, $$ ...
4
votes
0answers
26 views

Strongly connected subgraph that contains no negative cycles

Is there an efficient algorithm that solves the following decision problem: Given a strongly connected weighted directed graph $G$, defined by its transition matrix, is there a strongly connected ...
1
vote
1answer
52 views

What strategy should I use to sovle this interview problem? May I apply DP on this?

The problem description is as below and it feels like a DP problem but I am not sure, thank you for helping! You have a certain dose of a drug, say, 200 milliliters, and now some patients need this ...
1
vote
0answers
19 views

Algorithm to position samples minimizing error

We have a 1D function f(x). We would like to approximate this function with a polyline of n points. How can we find the ...
2
votes
2answers
52 views

Linear programming: reduce a contstraint that includes minimun

I have an almost linear programme. However one of the constraints has a form $z = min(x,y)$ (all the other things are linear in the model). Is there a way to substitute this with something (or ...
0
votes
0answers
29 views

Schedule a Seminar in Minimum Time

There are t1, t2, t3,.....,tn topics which are to be scheduled in a building with c1,c2,c3,....ck halls. Members have already registered there interests on the topics, and they have liberty to choose ...
1
vote
1answer
794 views

How can ideas like Lagrange Multipliers and Penalty Method be applied for solving algorithms?

I have a programming assignment which I was told that is solvable with some DP algorithm. The question involves some $k$ which is essentially a constraint. In particular the question is a variant of ...
9
votes
0answers
167 views

2D interval scheduling problem

Suppose I give you $n$ axis-aligned rectangles with a specified width, height, and x-position (of the left edge) $\{(w_i, h_i, x_i) \mid i \in \{0, \ldots, n - 1\}\}$, as well as a bound $(y_\mathrm{...
0
votes
0answers
15 views

How to model most optimized encoding of string data

Sorry if this question isn't super well defined, I am just struggling currently with figuring out what an "ideal solution" looks like to the following problem, and haven't pinned down an equation. I ...
3
votes
1answer
48 views

Find the minimal subset of rows of some matrix such that the sum of each column over this rows exceeds some threshold

Let $A$ be a an $n\times m$ real valued matrix. The problem is to find the minimal subset $I$ of rows (if there is any) such that the sum of each column $j$ over the corresponding rows exceeds some ...
17
votes
13answers
10k views

Why do we need full-fledged workstations running massive OSes with massive software?

I've grown up with computers. While watching old computer TV programmes and documentaries and reading the news about constant issues with these modern systems -- everything from the sheer amount of ...
1
vote
0answers
34 views

Proof of Fundamental Lower Bound on Regret

Online Convex Optimization sees optimization as a continuous process in which the algorithm learns new aspects of the problem and improves upon. Every iteration consists of the player making a ...
0
votes
1answer
59 views

Does Warnsdorff’s algorithm for Knight’s tour problem always gives complete tour

I have implemented the basic algorithm. easily available but I am not getting the complete tour. The visited square never equals N * N;
4
votes
0answers
39 views

Rectangle Packing with Constraints

I am aware that the general rectangle packing problem is NP-hard. I am trying to form an estimate for a version of the problem with constraints. Consider fitting rectangles of smaller size into a ...
0
votes
1answer
24 views

How to maximize the number of filled grid squares in a partially filled grid with Tetris shapes

So here's the problem: -You are given a partially filled grid of size mxn (represented by a matrix of 1s and 0s where a 1 signifies that grid square is occupied by a block and a 0 signifies that grid ...
3
votes
1answer
109 views

Minimum XOR for queries

I was asked the following question in an interview. Given an array $A$ with $n$ integers and an array $B$ with $m$ integers. For each integer $b \in B$ return and integer $a \in A$ such that $a \...
2
votes
1answer
27 views

What's the correct algorithm to filter accumulating string concatenations?

I have a function that is receiving messages with the following pattern: (In this picture, "string" and "message" are synonymous.) I'm only interested in the largest messages, such as these: over a ...
0
votes
1answer
31 views

What happens with register usage in deeply nested functions calls (in theory)?

I am far from being able to construct a meaningful test for this using godbolt or some C compilation tool. But basically I am wondering what it would look like to have deeply nested function calls, ...
0
votes
0answers
6 views

Efficiently populate a look-up table for a function over a range of arguments

I am minimizing a scalar function $f$ which takes a $n$-dimensional vector input and outputs a scalar value. I have code that given an input $x$ will compute the output of $f(x)$ (a scalar), its ...
0
votes
0answers
20 views

Optimization problem (maximize output)

Problem I have an optimization problem, where I want to find the value of parameters X1, X2 ... Xn which will give the highest output Y. Variables Several X variables are dependant. For example, ...
0
votes
0answers
16 views

What does the gradient mean in evolutionary algorithm?

I have been reading about evolutionary algorithms and I often find the concept of gradient that is used as "to follow a gradient"...
1
vote
0answers
21 views

Ranking function approximation

I have a matrix function, which roughly looks like this: $$ Y_{i,j,k} = f(coef, A, B) = coef[i] * A_{i,j} * B_{i,k} $$ ...
1
vote
2answers
54 views

What algorithm to use for this problem?

I was recently faced with a hackerrank interview test where I couldn't solve the following problem correctly. I would not want to name the exact problem for privacy purposes, but I can tell that it ...
0
votes
0answers
10 views

In multithreaded computations, how does parallelism, slackness and speedup affect the running time?

In the CLRS book it mentions that during some world-class multithreaded chess-playing program, developers had to prototype their program on a 32-processor computer then run it on a supercomputer with ...
0
votes
1answer
26 views

Mixed integer non convex optimization problem

If an optimization problem is mixed integer non-convex problem. The optimal solution by applying brute exhaustive search is infeasible to be applied in practice due to high complexity i.e. $O(N^K)$. ...

1 2 3 4 5 26