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
0 answers
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 ...
bsha's user avatar
  • 1
3 votes
2 answers
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 ...
xdaimon's user avatar
  • 53
-1 votes
0 answers
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 ...
mmartiss's user avatar
1 vote
0 answers
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 ...
Erel Segal-Halevi's user avatar
0 votes
0 answers
13 views

Given objective value for ILP find parameter is NP hard?

For an integer linear program: Given a matrix $A \in \mathbb{Z}^{n\times d}$ and two vectors $b \in \mathbb{Z}^{n}$, $c \in \mathbb{Z}^{d}$, compute $max\{ c^{\top}x|Ax \leq b, x\geq 0, x\in \mathbb{Z}...
wsz_fantasy's user avatar
1 vote
1 answer
47 views

Maximum reachable checkers on a checkerboard

This is a problem inspired by a video game that I've been thinking about for a long while, and I haven't convinced myself that I can do any better than brute force + pruning techniques, which would ...
crs's user avatar
  • 13
0 votes
1 answer
52 views

Optimizing Delivery Routes in a Graph-Based Network to Minimize Maximum Delivery Time

In a graph with N nodes, where each node represents a house and is labeled from 0 to N-1, an ...
maplemaple's user avatar
2 votes
1 answer
93 views

Optimal torch placement in voxel games

Problem definition The world consists of an infinite three-dimensional cartesian grid, i.e. every position is in $P = \mathbb{Z}^3$. Neighbours of a position $p \in P$ are defined by $N(p) = \{p + e_1,...
user13062187's user avatar
1 vote
0 answers
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 ...
Crash Bandit's user avatar
0 votes
0 answers
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 ...
Labeeb Basil's user avatar
0 votes
1 answer
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$ ...
calveeen's user avatar
  • 141
0 votes
0 answers
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 ...
swineone's user avatar
  • 161
0 votes
0 answers
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....
fekr's user avatar
  • 1
0 votes
0 answers
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 ...
Kumar A.'s user avatar
0 votes
0 answers
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 ...
Mohamed Hendy's user avatar
0 votes
0 answers
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 ...
Dar954826's user avatar
0 votes
0 answers
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 ...
dezdichado's user avatar
0 votes
0 answers
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 ...
Clement Genninasca's user avatar
0 votes
1 answer
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 ...
Freddie's user avatar
1 vote
1 answer
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 ...
Falls2879's user avatar
2 votes
0 answers
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. ...
Gabe's user avatar
  • 121
0 votes
0 answers
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 ...
Sam's user avatar
  • 11
0 votes
0 answers
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 ...
silass0's user avatar
0 votes
1 answer
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 ...
shay ariza's user avatar
1 vote
1 answer
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: ...
Erel Segal-Halevi's user avatar
0 votes
0 answers
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 ...
Alex D.'s user avatar
0 votes
0 answers
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....
isimo00's user avatar
1 vote
0 answers
15 views

Optimal top-k column subset

Let $V$ be a set of vectors over $\mathbb{R}^l$, $l\ge 1$, $\pi_i(V)$ be the permutation of vectors in $V$ such that they are ordered by their $i$th component (descending) in order for $\pi_i(V)(\...
Eli Bixby's user avatar
  • 141
0 votes
0 answers
55 views

Solving the Double-Choco Puzzle: Matching Sub-Matrices with Rotation and Mirroring

I'm working on implementing a solver for Double-Choco puzzle which published by Nikoli magazine. starting by representing the board cells as matrix containing cells with values 1 or 0, where 1 ...
Muhammad Z's user avatar
1 vote
0 answers
31 views

Maximize sum of matrix after deleting K rows and K columns

You're given a m by n matrix filled with positive integers, as well as some integer k (0 <...
jeffkmeng's user avatar
  • 111
0 votes
0 answers
18 views

Implementation of algorithm to enumerate all vertices of a convex polyhedron defined as linear inequalities?

I am looking for an implementation for any of the methods to enumerate all vertices of a convex polyhedron defined by $Ax \leq b$ I have found some papers that talk about the problem, for example this ...
Makogan's user avatar
  • 331
0 votes
0 answers
17 views

Transductive Information Maximization vs classification with feature embedding in higher dimensional spaces?

Recent research work has shown that transductive learning/inference outperforms standard methods that were used before, where people embed features in a high dimensional space and then use the ...
Sandra's user avatar
  • 63
1 vote
0 answers
25 views

Graph partitioning in 2 clusters minimizing between cluster edges

I've been looking for an algorithm which divides an undirected graph into 2 subgraphs. However, unlike most existing work on graph partitioning out there (like METIS), I don't intend to obtain ...
koch_kir's user avatar
0 votes
1 answer
36 views

Efficient algorithm to find the outflow of a lake

Consider a raster image representing a elevation map $$ z = f(x, y) $$ An "extended lake" $L$ is the largest domain such that the elevation of every point $\partial L$ is greater than the ...
user877329's user avatar
0 votes
0 answers
14 views

How to choose cells from a table to maximize their sum, with selection constraints?

I have a table of fixed positive integer values of anything up to several dozen. There are six columns and several hundred rows. I must choose exactly two values from each column, and zero or one ...
Atario's user avatar
  • 101
0 votes
0 answers
19 views

Minimum number of swaps to achieve prefix constraint

(An isogram is a word in which no letters repeat.) I'd like to know if there's a standard name for this problem, and/or any standard algorithms. If not, I'm interested in whether anyone has any ideas ...
SocraticMathTutor's user avatar
0 votes
1 answer
54 views

Optimizing findMissingNumber algorithm to O(N)

This problem is from Cracking the Code Interview: An array A contains all the integers from Oto n, except for one number which is missing. In this problem, we cannot access an entire integer in A ...
veron's user avatar
  • 1
0 votes
0 answers
19 views

Are there free/paid DISTRIBUTED solvers for a large system pf linear equations?

I've been doings some research into distributed solutions for a large system of linear equations (reading papers such as Wang et al.'s "Solving a system of linear equations: From centralized to ...
Karla's user avatar
  • 1
1 vote
0 answers
62 views

Proving the algorithm gives an optimal solution

Very often I see solutions to optimization problems that describe an algorithm but do not prove why the algorithm leads to an optimal answer. For example, the following problem showed up in an online ...
Ivan's user avatar
  • 111
4 votes
2 answers
77 views

Looking for efficient algorithm to pick out a unique equivalence class representative for 2D arrays with lots of symmetries

Given 2D arrays (number of rows between 0 and 10, number of columns between 0 and 10, elements are integers between 0 and 31) Two arrays $A,B$ are equivalent $A\sim B$ if $A$ can be transformed into $...
Todd Sierens's user avatar
0 votes
0 answers
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 ...
Zig302's user avatar
  • 1
0 votes
0 answers
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?
Csaba Király's user avatar
4 votes
2 answers
88 views

Finding a vector of maximum Hamming distance from a subspace of $(\mathbb{Z}/2\mathbb{Z})^n$

Let $W$ be a linear subspace of the vector space $V = (\mathbb{Z}/2\mathbb{Z})^n$. Let $k = \dim(W)$. For $v \in V$, define the distance from $v$ to $W$ to be $d(v,W):=\min_{w\in W} d(v,w)$ where $d(...
Ben's user avatar
  • 141
1 vote
1 answer
99 views

Reduction from MAX-3-CUT to MAX-CUT

Both MAX-CUT and MAX-3-CUT are known to be NP-complete. This post shows a reduction from MAX-CUT to MAX-3-CUT. I am curious if there is a way to reduce MAX-3-CUT to MAX-CUT? MAX-CUT: Given an ...
Phasivio's user avatar
  • 113
4 votes
1 answer
166 views

Finding Shift-Invariant "Interesting" Elements In Words

I want to find "interesting" elements in a sequence of symbols that are independent of their absolute position in that sequence. Formally, I have a window size $s \in \mathbb{N}$ and a ...
Henning's user avatar
  • 61
0 votes
0 answers
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 ...
a_confused_engineer's user avatar
0 votes
1 answer
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?
PatrickBateman's user avatar
1 vote
1 answer
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.} & \...
Ramon's user avatar
  • 15
0 votes
0 answers
46 views

How hard is it to find a spring network configuration with the lowest energy?

Given a spring system: where the total tension between the nodes should be minimized, it seems possible that a physics simulation of this graph does not arrive at the lowest energy state, getting ...
2080's user avatar
  • 191
0 votes
0 answers
24 views

Solving the constraint portion of the input-encoding problem

The "input-encoding problem" is where the binary representations of symbolic input variables to a Boolean function are chosen to minimize the decode logic complexity. The "Espresso-MV&...
MattyZ's user avatar
  • 101

1
2 3 4 5
36