# Questions tagged [optimization]

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

1,790 questions
Filter by
Sorted by
Tagged with
9 views

### Placement of Tasks from Dataflow Graph on a Physical Graph

I have a dataflow graph where a set of different types of tasks are placed in its nodes. For example, I have tasks of types A, B, and C. A-type tasks are placed in all the leaf nodes of the dataflow ...
364 views

### Find Minimum Transformation Between Multisets of Lists of Cards

Brief: I have two configurations, a and b, of the same set of Rummikub tiles (a may not be a ...
22 views

### Backpack assigment

Can you help me solve this problem. Names of items NAME, sizes SIZE and values VALUE are given. Using dynamic programming, find the optimal filling of backpacks of size M. NAME = {A, B, C, D, E}, SIZE ...
1 vote
19 views

### Computing the centroid of an "ellipsoid slice"

I want to compute the centroid of a body of the following form: $$E\cap H_1\cap \cdots \cap H_T$$ where: $E$ is an ellipsoid in $\mathbb{R}^d$: $E = \{x = c + Bu | u^T u \leq 1\}$, where $c$ is the ...
13 views

1 vote
16 views

### Given a group of people with timings for 2 events, find the shortest total time for X and Y given that events are mutually exclusive

Your classmates elected you to be in charge of the creation of the short and long distance running teams for the upcoming Sports Day event in your school. They have kindly given you their timings for ...
32 views

### Lookup Using Path Matrix in Floyd Warshall Algorithm

How is the path matrix created by the Floyd Warshall algorithm used for path lookup? The 2 images show the graph (b) and the path matrix (c). Both are taken from the book: Foundations of Algorithms by ...
27 views

### Minimizing the number of distinct elements by picking one set from each set of sets

I have a problem as follows. Given a set of sets $U = \{S_1, S_2, … S_N\}$ where $S_i = \{s_1, s_2, ... s_m\}$. Each $s_j \in S_i$ contains a set of distinct elements. I need to pick one $s_j \in S_i$ ...
28 views

### State of the art in register allocation for straight-line programs

TL;DR: I'm looking for the fastest known algorithm to perform optimal register allocation (optimal in the sense of minimizing the number of spills and reloads) for straight-line programs. Context I am ...
28 views

### Finding the minimum window where each input array has at least one active element [duplicate]

Given an $m\times n$ matrix $M_{ij}$ where $M_{ij}\in\{0,1\}$, find the minimal range $[a,b]$ for $1 \leq a \leq b \leq m$ such that each column has at least one value set to $1$ within that window, i....
31 views

### Probabilistic Pathfinding

Here an interesting graph problem I've recently saw: After a heist in New York City, a group must reach Miami within a set timeframe to catch an escape boat. Their vehicle's GPS shows U.S. routes with ...
29 views

### Proof of The Optimality Of Greedy Algorithm for The Interval Scheduling Problem

I have this proof for the optimality of the greedy algorithm for the interval scheduling problem in my algorithms class, but I'm struggling to understand it fully, especially starting from the second ...
9 views

### Parametrized threshold for LP Approximation in Vertex Cover Problem

I would like to have a formal description on how parametrizing the threshold in the approximation of vertex cover using LP would impact the approximation factor of the problem. The linear programming ...
26 views

### Optimal algorithm to select unique values from a daily-growing list

Suppose I have a list of numbers, say $L$, that grows every day when a new batch of numbers get added to it every night. Right now, say the list is of size $M$, with the daily batch size is of the ...
8 views

### Q-learning table efficiency

So I am trying to create a Q-learning algorithm to solve simple games, starting with tic-tac-toe. I would like to do so without completely eating away my memory, but all the examples online create a 2 ...
31 views

### Should I use linear programming for my timetable generator?

I am creating a timetabling software for a school, which given parameters for teachers/class sizes will output a timetable. There will be a list of classrooms per subject and a list of teachers per ...
1 vote
44 views

### In a directed graph, efficiently determine node reached after traveling k edges from the starting node

I am trying to solve a problem where I am given a directed graph with $n$ nodes where, from any given node, I can reach one and exactly one node. Nodes contain integers from $1$ to $n$. Starting at ...
31 views

### Minimum time inpainting a polygon with constraints

Given are the coordinates of a convex polygonal area ("field"), a moving circle of radius r ("crayon") and a home location for the crayon ("home") well outside the field. ...
38 views

### Minimize overlap in class schedule

At our school, we have a schedule that looks like the following (simplified): Remarks: One course can be taught multiple times a week (to different class-groups, like 1A, 1B and 2A) Multiple lessons ...
25 views

### Max flow with a minimal in-degree objective on certain nodes (for edges with non-zero flow)

The following a small-scale example meant to illustrate the general problem Suppose we have $n = 60$ marbles that we want to distribute into 3 bowls, $B = \{bowl_1, bowl_2, bowl_3\}$ The marbles can ...
31 views

### optimization problem in CV

hopefully I'm writing this post in the adequate place if not please move my post I'm reading this paper about L-shaping fitting for vehicles. and ran into this optimization in the photo attached. in ...
1 vote
106 views

### Computing an initial ellipsoid for solving a convex program

Suppose we want to find a vector $x\in R^n$ that satisfies the constraints $g_i(x)\leq 0$, for $i\in 1,\ldots, m$, where all $g_i$ are convex functions. The functions can be given by an oracle access: ...
88 views

### Finding the optimal trading route with output amount based on previous trades

I am trying to solve the following problem: Suppose there are traders who can exchange one good for another. Each trader $i$ defines two functions $y = f_{i1}(x)$ and $x = f_{i2}(y)$, with which we ...
18 views

### What are some applications of gerrymandering for Electronic Design Automation/Very large-scale integration?

There are many algorithms used for Very large-scale integration design (VLSI) or EDA (Electronic Design Automation). Most of them are challenges that imply some combinatorial/mathematical optimization....
1 vote
15 views

27 views

### Minimum set cover problem and dual, the maximum set packing

Just like in This thread that was posted here before, I came upon the same issue where I do not understand how are the relaxed maximum set packing problem and the minimum set cover problem are dual to ...
18 views

### Minimizing a sum of trigonometric functions

I would like to minimize the term where J_l and h_l are random numbers and L=10. Can somebody help me to solve the problem?
88 views

34 views

### How to capture the update-delay of observable variable in a model?

I have a problem that I am trying to model, but I am unable to capture one particularity of the system that seems to be crucial. I will try to give an abstract description first and then the toy model ...
20 views

### NP-HARD optimization problem and instance correlation

If an optimization problem A is NP-hard and P≠NP, then does there exist an instance x of A such that no polynomial algorithm provides an optimal solution for x?
1 vote
74 views

### NP-Complete Proof - Using CFLP

I have formulated the below optimization problem. \begin{align}\nonumber \hspace{-3mm}&\text{(P) minimize}\!\sum_{i}\!\alpha_{i}w_{i}\!+\!\sum_{i}\sum_{j}\!c_{ij} p_{ij}\!\\ \text{s.t.} & \...