Questions tagged [minimization]
The minimization tag has no usage guidance.
11
questions with no upvoted or accepted answers
8
votes
0answers
125 views
Determining if transducer automaton has two states with intersecting images, without minimizing?
I work (in implementation!) with deterministic finite state automata with input and output; i.e. there are transitions (start state,input letter)$\to$(new state,output letter). Thus every state gives ...
4
votes
0answers
620 views
Minimizing a monotone submodular function under a cardinality constraint
I would like to know what the status of the following question is:
Given query access to a non-decreasing, non-negative submodular function $f\colon 2^{[n]} \to \mathbb{R}$ and a parameter $0 \leq ...
3
votes
0answers
115 views
minimal languages that “cover” grammar productions
this question is based on generalizing two somewhat similar questions that recently appeared on the "sister" beta site cs.se (now with more questions than this one!) and which seems theoretically ...
3
votes
0answers
915 views
Christofides algorithm for directed graph
Is it possible to implement the Christofides algorithm for an directed Graph?
Suppose you have an undirected Graph, in which every vertex has an edges in both ways to every other in the graph (not to ...
1
vote
0answers
134 views
QUBO formulation of a discrete-variable optimization problem
I am facing a non-linear, discrete optimization problem, which I can formulate in this abstract manner: I have a certain non-analytic non-linear real-valued function $f:S \to \mathbb{R}$ which takes ...
1
vote
0answers
120 views
Minimize L2 norm by circular permutation
Imagine two lists $L$, $M$ of the same length $n$. How to find $j$ such that
$\sum_{i=1}^n(L[i]-M[i+j])^2$ is minimal, where the index $i+j$ is taken modulo $n$?
Of course one can take all the ...
1
vote
0answers
147 views
3D Bin Packing with one bin with infinite/unknown size
Hi I'm looking for a variation of the Orthogonal 3D-BinPacking algorithm with only one bin of unknown size.
I have a set $S$ of $n$ cuboids items $i_j$ with $j=1...n$.
The dimensions of the items are ...
1
vote
0answers
517 views
Splitting a graph into size constrained clusters
I ran across a problem while working on an algorithm for a game I'm making on the side. It's basically a clustering problem where we have a graph G and want to split it into clusters of equal size ...
1
vote
0answers
38 views
Determine whether a categorical grammar is minimal concerning lexical entries
In order to compare the descriptional complexity of context-free and (combinatoric) categorical I need a way to check if a categorical grammar of a formal language is minimal concerning lexical ...
0
votes
0answers
26 views
Searchable finite field
Let $F$ be a large finite field, where the elements are strings of length $n$. We require, addition, multiplication, and division to be efficient (polynomial in $n$).
We say that $F$ is searchable if ...
0
votes
0answers
463 views
Hardness of Minimizing Submodular Functions with Cardinality Constraints
I am new to submodular functions and I am reading the introductions to submodular functions and applications ( https://www.ima.umn.edu/optimization/seminar/queyranne.pdf ).
In this introduction, it ...
