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
vote
1answer
23 views

Is transfer learning applied on only similar datasets only?

I am trying to make a CNN model on different brands of logos . Firstly , I wrote a CNN from scratch and trained it on which I got 70% accuracy, I have total 40 classes and each class has 100 images . ...
1
vote
1answer
53 views

What is the Number of epochs with no improvement after which training will be stopped.?

I am trying to make a Convolutional neural network. Training the images of different brands of Logos. Have 100 images per class and there are 40 classes. I have trained the model now want to check ...
2
votes
1answer
52 views

Optimization problem over bidirectional connected graph

A company has several automatic vertical warehouses (called elevators). Each elevator have several trays and each tray has several slots. A slot contains a given quantity of a given article. Elevators,...
0
votes
0answers
14 views

How do I choose the right model for production?

I am trying to build a classification algorithm having 28 classes. These classes consists of Logo of companies like adidas , Nike etc. I have very low dataset below than 100 images and greater than 70 ...
1
vote
0answers
33 views

Given consumer grade hardware,what is a reasonable upper bound for size of search space?

There's a gacha RPG I'm trying to get better at. I estimate there are about 10^15 states for the 3 opening rounds of a match for which I am trying to evaluate damage output. The equations themselves ...
4
votes
1answer
57 views

Is there a computationally optimal point-in-polygon solution (for a dynamic scenario)?

I am approaching a problem where, among other things, I will have to repeatedly check if a point is within a (set of) polygon(s) in the 2D plane. the polygons are either convex or star-shaped with a ...
2
votes
2answers
83 views

Maximize number of subsets

Given a list of subsets $S_1, \ldots, S_n$ of the universal set $U = \{e_1,\ldots, e_m\}$, find a subset $S \subset U$ of size $k$ that contains the maximum number of subsets $S_i$. In another words, $...
1
vote
1answer
24 views

Finding optimal separating value

Problem description We are given two sorted arrays of even numbers: A and B. Values of A are generally supposed to be smaller than values of B. So we are asked to find a value X where X is an odd ...
0
votes
0answers
40 views

A multidimensional “moving van problem”: a mix of a knapsack and a bin-packing problem

This problem is a mix of the bin-packing and the knapsack problems. I call it "the moving van problem": there is a moving van with a limit on the weight it can transport, and a set of boxes ...
2
votes
1answer
33 views

Compute several histograms with multiple filter conditions

I have a numerical dataset of $N$ columns ($\approx 150$) and $K$ rows ($\approx 60000$). On a user interface, you can apply a filter to one or more columns. We can call the number of filters = $Z$ (...
2
votes
1answer
44 views

Graph partition that maximize the number of triangles within its parts

Given a graph $G = (V,E)$, how to partition $V$ into $k$ parts $P_1, P_2, \ldots P_k$ of at most $M$ vertices, such that the number of triangles (3-cliques) contained in the parts is maximal? This ...
0
votes
1answer
32 views

Area preserving distance optimization

I stumbled across the optimization problem described below and I am looking for how to approach it efficiently. I have the feeling that the problem at hand might be known, but I was not able to find ...
2
votes
1answer
54 views

This costs minimization problem, is it solvable in polynomial time?

I have the following problem: I have $c$ conflicts, named $(c_1, \ldots, c_c)$, where each conflict $c_i$ has certain size $s_i\in\mathbb{N}_0$: the number of times conflict $c_i$ has happened. Also, ...
2
votes
2answers
226 views

Partitioning a graph into subgraphs with overlapping nodes

I'd like to partition a graph into subgraphs with overlapping nodes. To do a simple partition into two, I could use kernighan_lin_bisection algorithm available in ...
0
votes
0answers
48 views

What is the significance of Bellman-Ford and linear programming for scheduling and makespans?

CLRS exercise 24.4-9 says the following: Show that the Bellman-Ford algorithm, when run on the constraint graph for a system $Ax \leq b$ of difference constraints, minimizes the quantity $\max_i\{x_i\...
1
vote
0answers
61 views

Can we make at most 3 comparisons in the closest points algorithm instead of 7?

Let's say I am using the divide and conquer algorithm outlined here, but I only want to return the minimum distance. I understand why that algorithm puts an upper-bound at 7 but I think that can be ...
0
votes
1answer
46 views

Local Search Optimization Algorithms in Applied Settings — How best to explain to applied researchers?

I realize this may be an opinion-based question, but relevant nonetheless in my opinion. Context: I have a local search optimization algorithm, A. I designed A to address a specific biological ...
1
vote
1answer
36 views

Find The “Best” Permutation of Inputs to Maximize Sum of Functions (or approximate “best”)

The Problem (in words) I want to sort $N$ items where the value of item $i$ at position $p$ is given by the function $f_i(p)$. The "best" order for these items is the one that maximizes the ...
3
votes
1answer
84 views

Algorithm to find the minimum (additional) popular votes to win the electoral college

So I'm thinking of a simple election prediction program to keep track of the minimum ballots the candidates must gain from the uncounted votes in order to win the election. Assuming we are considering ...
2
votes
2answers
21 views

Finding the rows/columns of an m-by-m symmetric similarity matrix M which minimizes the sum of the elements in an n-by-n submatrix N, where n < m

I have a machine learning problem where I need to find the most dissimilar subset of rows/columns of an $m$-by-$m$ symmetric similarity matrix $M$ which minimizes the sum of the elements in an $n$-by-$...
0
votes
0answers
19 views

Formatting the names of optimization problems

Excuse me in advance if this is a off topic question, but I do not know in which other forum I can ask this question. My question is of linguistic nature. What is the correct spelling of combinatorial ...
1
vote
0answers
23 views

Connection between convergence complexity of gradient descent and complexity of exactly solving convex program?

Let $f: \mathbb{R}^n \to \mathbb{R}$ be a convex function. Let $V \subseteq \mathbb{R}$ be some closed convex set. Consider the following convex minimization problem: \begin{align} \min_{\mathbf{x} \...
2
votes
0answers
19 views

Repairing a perfect binary merkle forest

Let's say we have a forest of imperfect binary merkle trees of different heights (this is an invariant). Only the numbered nodes store data, the rest store hashes. Here is an example with 4 trees, ...
0
votes
0answers
26 views

Is it possible to determine an instance of an NP-hard problem is easy or hard by the optimization?

I have an NP-hard problem and an optimization to deal with the problem. I want to know that is it possible to distinguish between easy and difficult instances of the problem by the parameters of the ...
0
votes
1answer
34 views

What parameter of optimizations, like time solving, can be used to show a phase transition in NP-hard problems?

Before asking the question, I should say that I am not sure here is a proper community to ask this question or not. I have an NP-hard problem and an optimization to deal with the problem. Recently, I ...
1
vote
0answers
7 views

Creating neighbours of solutions to binary knapsack instances

I am currently trying to implement a Tabu Search algorithm for the binary knapsack problem. Part of my goal is to have a variety of different configurations of attributes used and stopping conditions. ...
2
votes
0answers
20 views

Separating labelled points with a plane, minimizing label variance

Suppose we have observations with associated labels $\{({\bf x}_1, y_1), ({\bf x}_2, y_2), \dots, ({\bf x}_n, y_n)\}$ where ${\bf x}_i \in \mathbb{R}^d$ and $y_i \in \mathbb{R}$. Can we efficiently ...
0
votes
1answer
25 views

Find sets of weighted objects to maximize number of sets with weight >= X

I have N objects, each of which has a weight. I need to form combinations of the objects to maximize how many sets of objects add up to at least x total weight. Combinations can consist of any number ...
1
vote
1answer
28 views

Approximate LP for vertex cover problem

I am studying the topic of vertex cover on coursera and how it can be solved approximately by linear programming. Suppose the optimal solution for the vertex cover problem is $OPT$. I do not ...
2
votes
1answer
57 views

Min weighted edge cover - is the greedy algorithm sub-optimal?

The post here: Solving the min edge cover using the maximum matching algorithm provides a way to obtain the min edge cover from a maximum matching by greedily adding edges on top of the maximum ...
2
votes
1answer
30 views

What is the best algorithm to find the optimal path in reducing company's real-estate footprint?

I was hoping someone could point me in the right direction in terms of what type of problem I am describing and what type of algorithm I should use to answer it. Here is the problem: A company is in ...
1
vote
0answers
33 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
36 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
38 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
62 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
71 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
20 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
79 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
32 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. ...
3
votes
1answer
75 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: ...
2
votes
1answer
492 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
16 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
12 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
216 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
88 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
17 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
15 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
39 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
50 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 ...

1
2
3 4 5
31