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
0
votes
0answers
15 views

Find exact sum in path

So the question is Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. You can only move down and to ...
0
votes
0answers
19 views

How does AlphaGo perform when increasing the size of the board?

I recently watched AlphaGo, a documentary on the recent defeat by the best human player of Go by a computer, AlphaGo. The commentary the beginning points out this was ten years ahead of schedule (...
0
votes
0answers
21 views

Subset selection with maximum sum and minimum variance?

So I am trying to tackle a combinatorial optimization problem and would like some insights on how to approach it. The problem statement is as follows: Consider a set of elements of size N, how do I ...
4
votes
1answer
44 views

Graph coloring with fixed-size color classes

I'm interested in coloring a graph, but with slightly different objectives than the standard problem. It seems like the focus of most graph-coloring algorithms (DSATUR etc) is to minimize the number ...
2
votes
0answers
44 views

Monte Carlo tree search optimizations

I am designing a algoritm for a game using a Monte Carlo tree search AI that I implemented. I play against another player and want to get the best move. Every time I do a move I completely build a new ...
2
votes
0answers
12 views

Messy Representation Encoding example

I am currently working through Metaheuristics by El-Ghazali Talbi where he discusses encodings of algorithms. "Messy representations: In linear representations of fixed length, the semantics of ...
3
votes
2answers
75 views

Classify an algorithm to maximize number of tips used by liquid handlers concurrently

I'm looking for suggestions on algorithms, data structures or at least problems (so that I look for solutions in that domain) to consider. I realize that exact solution probably doesn't exist. But the ...
3
votes
1answer
26 views

Optimise the size of union of sets

We consider a set of sets $S = \{S_1, S_2, \dots, S_n\}$, and we want to find a subset $I$ of $S$ that maximises the size of the union of the set $S_i$ included with a penalty for each set included. ...
2
votes
1answer
50 views

Loop optimization of non-tail recursion

When researching how to optimize recursion into loops, I came upon (on Wikipedia) a general rule about this: Whenever a function is in form: ...
1
vote
1answer
30 views

How to understand the solution to Task Scheduler problem on LeetCode?

LeetCode Task Scheduler problem is the following: Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any ...
0
votes
0answers
14 views

How to predict the number of patients from the number of diagnoses

I have data on the diagnostic measures that individual patients received that year. For that individual data, I would like to make a prediction of how many such patients are in the country. To do so, ...
0
votes
0answers
9 views

How to combine multiple Boolean Functions in CDNF efficiently for implementation on a CPU?

I am trying to see how fast I can implement a 6-bits to 6-bites lookup table. Generally, I am attempting to do this by using the common method mentioned in CS textbooks of using the Quine-McCluskey ...
2
votes
0answers
148 views

Strong polynomial time algorithm for deciding LP feasibility

Let $$A \cdot X + B \preceq 0$$ be a system of linear inequalities with $X \in \mathbb{R}^n$ $A\in \mathbb{R}^{m\times n}$ and $B \in \mathbb{R}^m$ where $m \geq n$. According to Farkas lemma, exactly ...
2
votes
1answer
37 views

0-1 Knapsack problem with item discounts

I recently encountered this kind of problem in a real world setting, and could not for the sake of me find any literature relating to the problem statement I came up with. An example will be included ...
1
vote
0answers
13 views

Dynamic Chromosome Length in Genetic Algorithms

My inquiry concerns the length of chromosomes employed in genetic algorithms (GA), and more broadly in other classes of evolutionary algorithms. The chromosome length is fixed throughout a GA's run. ...
0
votes
0answers
12 views

Encoding a lot of categorical variables

I have 10 million categorical variables (each variable has 3 categories). What is the best way to encode these 10 million variables to train a deep learning model on them? (If I use one hot encoding, ...
2
votes
0answers
28 views

Maximize the minimum gap while scheduling within intervals?

Problem There are N intervals in which a particular integer can be chosen. What is the maximum possible minimum gap between each integer if one integer is chosen for each of those intervals? For ...
2
votes
2answers
48 views

Parall execution of algorithms that solves polynomically disjoint subsets each of a NP-hard problem

I was thinking in the following approach for solving a problem that is believe to be a NP-hard problems today in polynomial time, assuming the following: There exists a believed-today NP-hard problem ...
0
votes
1answer
22 views

Polynomial-time algorithm to solve the maximum vertex bipartite subgraph problem

I'm trying to find an algorithm that solves the maximum vertex biclique problem. I know that that algorithm can be solved in polynomial time (in contrast with the maximum edge biclique problem, which ...
1
vote
1answer
22 views

In a set of sentences, how could I determine the fewest sentences that contains all characters?

So, for the sake of simplicity, I am going to use English characters for this example. Let's say I have a set of strings of characters in English ranked by difficulty: Easy, Intermediate, Advanced. So ...
4
votes
1answer
64 views

Optimising an exhaustive search for a card game

I'd like to search for a combination of resources that when used, would produce at least up to a threshold of different kinds of materials. For the majority who are not in the know, I'll use an ...
0
votes
1answer
34 views

If a poly-time solution exists for an NP-Complete (Decision) problem, then there exists a poly-time solution for the NP-hard (Optimization) flavor?

This question boils down to: If a polynomial time solution exists for a decision problem, is there also a polynomial time solution for the same problems optimization flavor? Let's take the Traveling ...
0
votes
0answers
13 views

What are all local optima of the six-hump camel back function?

This is a famous function to test optimization heuristics such as genetic algorithms and others. The 2 global optima are described clearly in many webpages, but surprisingly I'm unable to find any ...
0
votes
0answers
38 views

offline Bin Packing problem with multiple size bins

As per my research on stack overflow communities, This is probably known as cutting stock problem / multiple Knapsack problem (a variant of the bin packing problem) which is NP hard. here are the ...
1
vote
0answers
47 views

Why does a kalman filter work better in a simulation than in real life?

I am trying to use a classical Kalman filter for getting indoor location. I am using geolocation API of HTML to get latitude, longitude, position accuracy and speed. I am also using the smartphone's ...
0
votes
0answers
18 views

How to justify the choice of using a specific metaheuristic?

For a problem how to justify the use of a metaheuristic upon another? For exemple for scheduling problem, could the same heuristic be efficient for different variants of the problem? What are the ...
0
votes
2answers
34 views

Maximization problem

I work at a company and i got to a seminar we're they told us to solve this problem below in the picture Is there an algorithm that can help me solve this question. I thought about a randomized ...
1
vote
1answer
38 views

Algorithm for maximizing the number of same-sized groups

Let's say you have groups of objects, and a certain amount of objects you can add to these groups (you cannot create new groups, and do not necessarily have to use all your extra objects), and the ...
1
vote
1answer
30 views

Find maximal subset with interesting weight function

You are given $n$ rows of positive integers of length $k$. We define a weight function for every subset of given $n$ rows as follows - for every $i = 1, 2, \dots, k$ take the maximum value of $i$-th ...
1
vote
1answer
31 views

How important is initial state for local search optimisation?

I have been enjoying Pascal van Hentenryck's Discrete Optimisation course and we're in Week 4 on the wonders of Local Search algorithms for combinatorial optimisation. I'm wondering how important the ...
1
vote
1answer
26 views

Search for range in continuous function satisfying some condition

I am attempting to define an optimization for the following problem: given a graph find the largest interval(s) where S > S_th (the narrower the interval the ...
1
vote
0answers
18 views

Variant of ridge regression loss function

We can create variants of the loss function, especially of ridge regression by adding more regularizer terms. One of the variants I saw in a book is given below $min_{w \in \mathbf{R}^d} \ \ \alpha....
0
votes
0answers
60 views

Is it possible to form this as a linear program?

My problem is as follows: I have some number $n\in \mathbb{N}$ of items all of size $s\in \mathbb{N}$ that need to be fit into a distributed storage of sizes $[b_1, b_2, ..., b_m], \forall i, b_i \in \...
2
votes
1answer
62 views

How to convert a recursive function to a non recursive one using stack while keeping memoization?

Let's say I want to count the number of ways a string can be decoded, once encoding algorithm follows this map: 'a'=>'1', 'b'=>'2', ... 'z'=>'26'. I could ...
3
votes
1answer
254 views

efficient algorithm for min cut with specified number of vertices

Consider a graph with vertices $V$ and edges $E$. The standard version of the min cut problem is to find the partition of $V$ into a (non-empty) subset $C$ and its complement $\bar{C}$ so as to ...
2
votes
0answers
42 views

What is the largest sum that can be constructed with the given recipes?

There are $n$ sets of distinct positive integers, $S_1,\ldots,S_n$. There is a set of recipes that allows us to construct tuples of integers from these sets. For example, the recipe {1,2} allows us to ...
2
votes
0answers
23 views

How to linearly combine loss functions to preserve optimal substructure property?

I've been working on a binary tree optimization problem with two choices of loss function (let's call them A and B). I'm fairly certain that the problem of minimizing either A or B individually has ...
0
votes
0answers
18 views

Minimizing the length a Boolean Algebra Expression in disjunctive normal form

I'm looking to minimize the length of an expression in boolean algebra that has been given in disjunctive normal form and is free from redundancy. To remove redundancy from the original expression I ...
4
votes
0answers
45 views

Repeated linear programming with similar (not identical) problems

I have multiple linear programming problems of the form: $$ Minimize\{c^{T}\cdot x\} s.t. Ax = b, x \ge 0 $$ Where $c$ and $A$ are fixed for all the problems. Is there any way to utilize that for a ...
1
vote
0answers
45 views

Algorithm for summation with lowest maximum temporary sum

I've got this problem on my last exam, which I struggle to deal with. Let's say we have array of $N$ integers (it can be float too, but let's say integers for sake of simplicity. We need to sum those ...
2
votes
1answer
34 views

Approximation factor preserving reduction

The definition of approximation factor preserving reduction from the book by Vijay V. Vazirani, page 365: Let $\Pi_1$ and $\Pi_2$ be two minimization problems, an approximation factor preserving ...
1
vote
0answers
73 views

Minimum vertex cover and odd cycles [closed]

Suppose we have a graph $G$. Consider the minimum vertex cover problem of $G$ formulated as a linear programming problem, that is for each vertex $v_{i}$ we have the variable $x_{i}$, for each edge $...
3
votes
1answer
40 views

Is MAX-averageSAT a well-known problem?

Is there any variant of the Boolean SAT or Max-SAT problem that has a flavor of maximizing or minimizing the average of the weights of the satisfied clauses of a WCNF formula? Any literature on an ...
2
votes
2answers
59 views

optimizing for loops

Disclaimer: I'm not a compiler expert. I'm simply curious and come seeking enlightenment. I've seen people claim that -- for efficiency -- for loops should ...
0
votes
0answers
34 views

'Traders's Route' problem optimization algorithm

I've come up with a problem which we'll call the Trader's Route Problem (If it's an already understood problem that would be great as well, let me know). Say there exist N cities, with some arbitrary ...
0
votes
0answers
23 views

Optimal placement of radio towers

Imagine there is an area on which you have to put radio towers. Each radio tower sends signal to a circular area of fixed size. How do I determine the optimal number and placements of these towers so ...
2
votes
1answer
102 views

Minimum vertex cover algorithm with linear programming

Consider the following algorithm: given a graph $G$ with $n$ vertices, set up a linear programming problem LP where there is a variable $x_i$ for each vertex $v_i$ of $G$, each variable can take value ...
0
votes
0answers
21 views

Value Maximisation Algorithm with multiple costs

So in front of me lies different items. To buy each item you will need a certain amount of multiple things. For example, to buy a lamp, you will need to pay 3 apples, 4 oranges and 17 bananas. Each ...
6
votes
2answers
185 views

Odd cycle transversal and linear programming

Suppose we have a graph $G$ with $n$ vertices. Suppose LP is a linear programming problem where there is a variable for each vertex of $G$, each variable can take value $≥0$, for each odd cycle of $G$ ...
0
votes
0answers
54 views

Why can't a compiler just “think more” about optimization?

This happens to me from time to time: I compile my code with the highest optimization level (-Ofast) of the allegedly fastest compiler (GCC) of one of the fastest ...

1
2 3 4 5
29