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}...
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
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
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 ...
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 ...
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 ...
2
votes
2answers
1k views

Given a set of 2D vectors, find the furthest reachable point

Input: a set of 2D vectors $S=\{v_1,v_2,\dots,v_n\mid v_i\in \mathbb{Z}^2 \}$ Question: name $P=\{\sum_{v_i\in S'}v_i\mid S'\subseteq S \}$ for all subsets of $S$ (obviously $|P|=O(2^n)$). In ...
5
votes
2answers
3k views

Optimization problem vs decision problem - reduction

Assume we have an optimization problem with function $f$ to maximize. Then, the corresponding decision problem 'Does there exist a solution with $f\ge k$ for a given $k$?' can easily be reduced to ...
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
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 ...
2
votes
3answers
2k views

Given an array of integers and a value k, find the length of the longest subarray with max-gap no more than k

I'm struggling with this problem: you are given an array $A$ of $n$ integers and a number $k \in \mathbb{N} : k \neq 0$. The problem asks to find an algorithm that runs in $\Theta(n)$ that returns the ...
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
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
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 ...
0
votes
1answer
36 views

Change the structure from 3SAT to 1in3 3SAT

There is a variable set V = {x1,x2,x3} and clause set C1={x1,x2,-x3} C2={x1,-x1,-x2} C3={-x1,-x2,x3} C4={x2,x3,-x3}. For this structure, no matter each variable is positive or negative, the clause can ...
-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 ...
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
vote
1answer
48 views

Intuition behind this specific algorithm for time series

Going through the EPI book and I need some help understanding this part. There's a problem, 5.7, that deals with buying and selling twice over a single time-series in order to maximise profit. The ...
-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 ...
-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 ...
2
votes
0answers
49 views

Goemans' Extended Formulation of the Permutahedron And Comparator Networks that are not Sorting Networks

I am interested in using Michel Goemans' extended formulation first developed for the permutahedron to study comparator networks that are not sorting networks. In his paper "Smallest Compact ...
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 -> ...
0
votes
1answer
221 views

Distribute repeated values into bins as evenly as possible

Preface I've asked a very similar question already on stack overflow in a different wording and gotten a working answer under the assumption that there is no way to go through all possibilities (np-...
0
votes
1answer
57 views

Looking for the name of this job scheduling algorithm

You have a list of jobs. Each job has a deadline and an associated profit if completed before the deadline. Also, each job takes 1 unit of time to complete, and only one job can be completed at any ...
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 ...
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$, $$ ...
1
vote
1answer
1k views

Using 2-opt Heuristic in a Genetic Algorithm for TSP

I read few papers while trying to find some better approachs to solve the TSP (Traveling salesman problem) as close to the optimal solution as possible. I implemented a Improved Greedy Crossover (...
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 ...
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 ...
2
votes
2answers
340 views

Scheduling / Queuing jobs with multiple different workers

I have a stream of jobs (so I don't know upfront how many jobs). And I have N workers in the system. Now I want to schedule / queue a job to one worker (a worker can have multiple jobs in his queue). ...
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 ...
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 ...
-1
votes
3answers
1k views

Divide N sticks among M boys as homogeneously as possible (ignoring order)

There are $N$ sticks. $N$ is an integer greater than zero. I want to divide it among $M$ boys. $M$ is also a positive integer. Partitioning $N$ among $M$ is easy, but doing it as evenly as possible is ...
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{...
4
votes
1answer
353 views

Vehicle Routing Problem with multiple deliveries?

I have a problem that can be reduced to the following: There are three types of objects, A, B, and C. For each type of object, there are a number of "pickup points" and a number of "delivery points"...
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 ...
0
votes
1answer
188 views

Finding longest prefix of a given string in set of strings that satisies some property

I have a set of strings, lets call them RULES. I have a function F which given 2 strings deterministically returns boolean value. Given one string, lets call it QUERY, what is the fastest way to find ...
1
vote
1answer
209 views

Solve Max 3 color problem using 3 color decision problem

I've been stumped on this question for a while and can't find a solution. How can I find the max 3 colorability of a graph(optimization problem) with 3 colorability (decision problem) without brute ...
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 ...
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 ...

1 2 3 4 5 26