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

Using graph symmetries to speed up subgraph enumeration

I have an undirected graph $G$. It has some symmetries in the sense that I know it's automorphism group $\text{Aut}(G)$. I am searching for a specific subgraph defined by some constraints $\phi$ and ...
-1
votes
0answers
25 views

Minimum cost required to cover a line with line segments

We are given a line segment $[1, n]$ with $m$ smaller line segments $[l_{i}, r_{i}]$. An example being $[1, 4]$ and line segments ${[1,2], [2,3], [3,4]}$. We can cover this using first and third ...
0
votes
1answer
12 views

Finding the distance from a point to a $R^m$ restricted area in $R^n$

The problem is described below: When m=2 and n=3, it is basically finding the distance between a point and a line segment in $R^3$. But when both m and n are larger, do I have to use a generic ...
-1
votes
0answers
12 views

Connected component- feature regions extraction

I'm trying to extract the connected component from a graph, in the following way: ...
1
vote
1answer
36 views

Find optimal play by optimizing orders of each player alternatingly

A zero-sum game for two players allows a player to take no action during a turn. Can I reach optimal play (where both players always choose the best possible action in each turn) by the following ...
0
votes
1answer
60 views

Non-convex linear program optimisation with infinite number of OR constraints

I am aware that when we have a linear problem subject to OR constraints, the LP would be a non-convex optimisation problem. For example, ${x = 0}$ OR ${1<=x<=2}$. My question is in such a ...
0
votes
0answers
21 views

Optimisation of workforce allocation

I am looking at a problem of cost optimisation by dynamic staff allocation.This could be for any public space like Airport/Railway Station etc. where the maintenance work is outsourced to other ...
0
votes
2answers
76 views

Minimum number of moves puzzle

Let K players be among N towns in a circular position. On each turn, only one player can move. A player cannot move if he is the one who moved in the previous turn. A player can only move clockwise ...
0
votes
2answers
59 views

Find the largest rectangle inscribed in a region partitionable into rectangles

Given a rectilinear polygon, what is an run-time efficient algorithm that finds the largest inscribed rectangle the sides of which either parallel or perpendicular to the sides of the rectilinear ...
3
votes
0answers
41 views

Find the largest interior rectangle composed of partitioning rectangles

Suppose a rectangle $R$ is partitioned into more than one smaller rectangles of positive area. What is the fastest algorithm to find the largest rectangle strictly within the all-enclosing rectangle $...
0
votes
0answers
43 views

A paper claiming that optimization version of symmetric TSP can be solved in polynomial time

In the following paper : Czopik, J. (2019) An Application of the Hungarian Algorithm to Solve Traveling Salesman Problem. American Journal of Computational Mathematics,9, 61-67. In the Introduction, ...
2
votes
0answers
73 views

An unknown combinatorial optimization problem

I have $N$ available sensors and $M$ devices. Each device needs $a$ sensors. One sensor cannot be used on multiple devices. Each sensor has two properties defined by $H$ and $R$. Let $\sigma_{i\_H}$ ...
1
vote
0answers
25 views

Is the problem “find the sequence of $N$ numbers between 1 and $D$ with least cost”, NP-hard?

Consider sequences $p=(p_1,\dots,p_N)$ (the order matters) of length $N$, where $p_i\in\{1,\dots,D\}$ for fixed $D$. Moreover, consider a cost function $c:\{1,\dots,D\}^N\to\mathbb{R}$ which comply $c(...
0
votes
1answer
25 views

Is this variation of the traveling salesman problem NP-hard

Consider the following setting. You have $n$ cities, and there is a cost to travel from a city $i$ to a city $j$ given by $c_{ij}>0$ where $c_{ij}\neq c_{ji}$. Moreover, if you are traveling to ...
0
votes
0answers
38 views

Is this combinatorial seach problem NP-complete?

The context: Consider the following optimization problem. Let $f_1,\dots,f_L:\mathbb{R}\to\mathbb{R}$ arbitrary (continous) functions for $L>1$ and $x_k\in\mathbb{R}$ evolve according to $$ x_{k+1}...
1
vote
0answers
21 views

Applications of derivative only, zeroth-order free optimization

I understand what is derivative-free optimization, and I am thinking a similar problem where the function $f$ we are optimizing is unknown and the only information we can acquire is the derivative. In ...
0
votes
1answer
18 views

Solving linear programming problem with mixed type of constraints

I have a query in solving the problem below: An automobile company has two factories. One factory has 400 cars (of a certain model) in stock and the other factory has 300 cars (of the model) in stock. ...
2
votes
0answers
31 views

Min Cost Max Flow algorithms for providing multiple solutions

Minimum Cost Maximum Flow algorithms have been known to provide an optimal flow routing for network flow problems in satisfactory runtime. Some of the algorithms for solving a min-cost max-flow ...
0
votes
1answer
33 views

reference request: solving problems by dynamic programming + quantization to avoid combinatorial explosion

The context: I have been working lately with problems like the following: Let $x_{k}\in\mathbb{R}^n$ be a state evolving accroding to: $$ x_{k+1} = f(x_k,u_k), k=0,\dots,N-1 $$ given some $x_0$ and ...
0
votes
0answers
8 views

Resource Allocation problem using Deep Reinforcement Learning

I am working on a resource allocation problem, and I need some help. I have a few Jobs (J) and few Machines (M) to complete them. Each job has a size (s_j), resource demand (c_j), and a delay bound (...
3
votes
1answer
27 views

Transform a set of points to have a minimum distance between them

Assume I have a set of $N$ ordered points, $X$. I would like to find the set of $N$ points, $Y$, where the distance between $X$ and $Y$ $(d = \sum_{i=0}^{N-1} |X_i - Y_i| )$ is minimized but there is ...
2
votes
0answers
38 views

Efficient solution to this scheduling problem or integer optimization problem

Context: Suppose I have a matrix $P_k\in\mathbb{R}^{n\times n}$ that evolves in time $k$ according to $$ P_{k+1} = H_{\sigma(k)}^TP_kH_{\sigma(k)} $$ where $H_{\sigma(k)}\in\{H_1,\dots,H_L\}$, $H_i\in\...
0
votes
1answer
35 views

Why do the following algorithms for Quadratic Primes perform so differently?

I'm trying to solve for https://projecteuler.net/problem=27, and I have to optimize one part of the implementation from slow() to fast(). Why do they perform so differently? I'm guessing branch ...
1
vote
1answer
61 views

Find the element $x$ that maximizes $f(x)$ for $x \in \sum A_i$

I have a collection of sets $A_i \subset \mathbb{Z}$ where I want to find the global maximum after combining the sets using sumset. The sumset is $$ A + B = \{ a + b : a \in A , b \in B \} $$ and $R$ ...
0
votes
0answers
22 views

Calculate math function depend on N value

I have method with the following prototype : R[] = method(k,n) which : ...
2
votes
1answer
24 views

Optimize stacking time series by offsetting start times (feels like a backpack problem?)

Given a time-series of data collected from a single running process that takes 8 hours to complete: Minute GB of Disk Space Used 0 0 1 8 2 15 3 22 ...Etc. It is sampled every minute, for 8 ...
1
vote
2answers
35 views

Optimal clustering with optimal number of clusters as well as max and min cluster size constraints

I need to cluster $N$ data points. I don't know the number of clusters to be formed. It needs to be found optimally. Also, there is maximum and minimum cluster size constraints, where $C_{\max}$ is ...
3
votes
1answer
88 views

Polynomial time optimization problems belong to which complexity class?

I know that $\mathsf{P}$ class is only defined for decision problems. Therefore, a problem like "Does there exist an $(s,t)$ path of length $k$ in the graph $G$?" is in $\mathsf{P}$. One can ...
1
vote
0answers
52 views

What does a recursive min s,t-cut optimize?

Consider the following algorithm sketch: Given an edge-weighted directed acyclic graph $G = (V, E, w : E \to \mathbb{N})$, adjoin a temporary source $s$ and sink $t$ to get $G' = (V', E', w')$. $G'$ ...
3
votes
0answers
47 views

Minimum Vertex Cover of 2 vertex disjoint odd cycles that have edges between them

Consider the graph $G$, which is comprised of 2 vertex disjoint odd cycles ($C_1$, $C_2$) where $|C_1|$ and $|C_2| \geq 5$. $G$ is sub-cubic and connected, with edges in between the cycles. Because $G$...
1
vote
1answer
32 views

Reduction from TSP to ATSP does not imply constant factor approximation algorithm

As I understand there is a constant factor approximation algorithm (e.g Christofides algorithm) for the symmetric TSP problem. This is however not the case for the asymmetric TSP problem (I am ...
0
votes
0answers
14 views

Multi-Objective Implicit Hitting Set for Multi-Objective MaxSAT

MaxSAT is a problem related to SAT where there is a finite collection of hard and soft clauses which share boolean variables. The hard clauses must be satisfied while the soft clauses have a weight. ...
3
votes
0answers
59 views

How to check whether a lattice polytope embeds into another lattice polytope?

Suppose I have two polytopes $P\subset \mathbb R^m$ and $Q\subset \mathbb R^n$ with vertices with integral coordinates. How do I check whether $P$ is embeddable into $Q$? More precisely, "...
1
vote
0answers
26 views

Which branch of computer science uses mathematical optimization the most?

I am beginning with my masters degree in mathematics and I will specialize in optimization theory. My minor is computer science and wanted to know which branch of computer science fits my ...
1
vote
1answer
31 views

Find the k length path that maximize a node associate metric

Let's say I have : a Graph g v vertices. Each vertex is associated to a cost c. A special vertex called the starter vertex or vs. I want to find the path p of length 10 (for example), that start ...
0
votes
1answer
45 views

If P = NP, do these NP-complete problems reduce to these specific easier versions?

I am trying to understand reductions and NP-completeness from Algorithms by Dasgupta et al. Chapter 8 has the table below and I am wondering: if $P = NP$ does each of the problems on the left reduce ...
3
votes
0answers
46 views

SSA Copy Folding

When can we fold copies in SSA? We are clearly allowed to fold a copy such as a0 = call foo() b0 = a0 But what about a program such as ...
1
vote
0answers
16 views

How to calculate image gradient with respect to homogeneous coordinate vector?

I want to use the direct method of computing the homography between two images to estimate the plane parameters (normal and depth [= distance from camera]) of a 3D plane. If we have two images of the ...
1
vote
0answers
32 views

Minimal number of unions of sets such that no union has more than N elements

I have some sets, and can combine them by taking their union. I can take unions of the unions, too. I want to take unions until the total number of sets is as small as possible, with one caveat: that ...
1
vote
1answer
55 views

Variant of assignment problem

This is something like assignment problem, we have 2 group of people, first contains $n$ person and second contains $m$ person. we have a matrix $C$ which is an $n \times m$ matrix and our goal is to ...
1
vote
1answer
52 views

solve a rational equation as fast as possible

I would like to find the first positive solution(if there is one) to this equation: $$\frac{ax^2+bx+c}{dx^2+ex+f} = gx+h$$ The simplest way I fond would be to do the following: $$ax^2+bx+c = (dx^2+ex+...
0
votes
0answers
31 views

Coordinate descent for Lasso, Question about algorithm

I'm not sure why the algorithm computes $c_k$ with $\sum_{j \neq k} w_j x_{i, j}$. Why does one need to ignore the $k^{th}$ feature here? I'm not sure how this is derived. Is this the result of taking ...
1
vote
0answers
13 views

How are randomized restarts in local search 4 times likely to give bad local minima?

I am reading section 9.3.3 Dealing with local optima in Algorithms by Dasgupta et al. and the authors mention that in randomized restarts, it is four times likely to end up with a bad solution. They, ...
5
votes
0answers
41 views

2-Dimensional interval scheduling problem

I have a problem that is similar to the conventional interval scheduling algorithm but it is two dimensional, so I have another metric to take into account. My dataset format: Cars with the start and ...
1
vote
0answers
72 views

0/1 Knapsack problem with minimal cost

so i have this problem where: I have to accomplish a challenge A with n quests. Each quest gives me: p points and needs t time to be done. The object is to complete the challenge A that needs M ...
1
vote
1answer
25 views

Online approximation algorithm for median?

Is there a well-known or (relatively) easily-implementable streaming algorithm for approximating the median of the last, say, $k$ elements of a stream $c_1,c_2,c_3,\dots$? The scenario is: I have a ...
0
votes
1answer
49 views

Exit quickly from a maze with a local view of the maze

How to efficiently exit from a maze where you know the initial position of the player (1,1), the exit (49,49)? You don't know the maze configuration but you know where your player is, and which ...
1
vote
1answer
38 views

Is the Jacobian matrix calculation process correctly on this energy function?

When I implemented the paper Dynamic Fusion published in 2015 CVPR, I came into the trouble with how to solve the energy function: $$E(W_t, V, D_t, \mathcal{E}) = \text{Data}(W_t, V, D_t) + λ\text{Reg}...
2
votes
1answer
12 views

Scheduling algorithm for a student's study times given assignments, expected time, due dates, and class times

I would like to create an algorithm that advises a student when they should work on certain assignments given the expected time each assignment will take, and the due date of each assignment. Say that ...
0
votes
0answers
10 views

How to use XML format of graphs in Graph neural network?

I have manually labeled directed graphs that I need a GNN to train on and then predict when given a new directed graph, what the labels for the vertexes in the graph should be. My graphs are in the ...

1
2 3 4 5
31