Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [optimization]

general questions about selecting a best element from some set of available alternatives.

453 questions
Filter by
Sorted by
Tagged with
1 vote
337 views

### What is the fastest static comparison sort? What is the proper term for "static"?

In a standard comparison sort, you perform a comparison and your next action is based off of the result of that comparison. What if this was not allowed, and you had to request all the results at the ...
1 vote
86 views

### Non-convex optimization with correlated minima

I am thinking of non-convex optimization problems where the minima are somehow correlated. Maybe there are symmetry relationships among minima or maybe there is regularity in spacing among minima in ...
1 vote
112 views

### How to calculate processor throughput boundary in CSAPP?

In Chapter 5.7 of CSAPP, author list out the throughput boundary of Intel Core i7 Haswell while executing the operation Integer addition and multiplication, floating points addition and multiplication....
69 views

### What work on min max connectivity problems has there been?

For instance has min max spanning/steiner/prize-collecting tree been studied. i.e. each edge $e$ has costs $c_{v,e}$ of each resource $i$. And we wish to find a spanning tree minimizing the maximum ...
64 views

### Has multiobjective prize collecting steiner tree or TSP been studied?

Suppose we have a graph $G$ a root $r$ and each node $v$ has some amount of $c_{v,i}$ of each resource $i$. I connect a set of nodes to the root that maximizes the minimum amount of any resource using ...
1k views

### Knapsack with dependent profits (pairs of items)

I'm working on a problem which MAY be reduced to the following version of Knapsack: Suppose two items $e_i$ and $e_j$ have profit $p_i$ and $p_j$ respectively. However, if both items are present in ...
47 views

### cutting plane method for convex optimization

The cutting plane approach in convex optimization is a general recipe for minimizing a convex function. The argument relies on the fact that using the gradient vector, we can cut the feasible set into ...
52 views

117 views

### Is beta normalization used for program optimization?

Beta normalization reduces a lambda term to its beta normal form, if it exists. The beta normal form is a computationally equivalent term with no "redundant" computation, in a sense; for ...
96 views

### Maximum cardinality disjoint cycle cover in undirected graphs

I call a maximum cardinality disjoint cycle cover of a graph a vertex-disjoint cycle cover containing the maximum possible number of cycles in the graph. What is known about the complexity of this ...
60 views

### Is there an algorithm that finds a minimum vertex cover with an approximation factor of 3/2 for a planar graph?

Is there an algorithm that finds a minimum vertex cover with an approximation factor of 3/2 for a planar graph?
3k views

### Solving semidefinite programs in polynomial time

We know that linear programs (LP) can be solved exactly in polynomial time using the ellipsoid method or an interior point method like Karmarkar's algorithm. Some LPs with super-polynomial (...
1k views

### Clique problem on fixed graphs

As we know, the $k$-clique function $CLIQUE(n,k)$ takes a (spanning) subgraph $G\subseteq K_n$ of a complete $n$-vertex graph $K_n$, and outputs $1$ iff $G$ contains a $k$-clique. Variables in this ...
32 views

### Nonlinear GAP similar to Min-GAP but with minimum quantities and without capacity

I have $m$ items and $n$ bins where each item $i$ and bin $j$ has a value $v_{i,j}$. Each bin $j$ has a value $V_j$. I want to pack the items into the bins such that (1) I minimize the ratio of the ...
133 views

### Linear Programming Sensitivity to Matrix

Consider a linear program in the following standard form: \begin{align*} &\max c^T x &\\ &\mbox{subject to:}\\ &A x \preceq b\\ &x \succeq 0 \end{align*} Its dual is \begin{align*}...
134 views

### Which variant of the ellipsoid method was used for the Santa Claus problem?

As one of the steps in the article The Santa Claus problem (Bansal and Sviridenko, 2006) the following linear problem was considered (at the end of the second page, as the dual): \begin{align*} &\...
185 views

### Solving Grouped Weighted Job Scheduling with Release Times and Deadlines on a Single Machine with Multiple Availability Intervals

I'm working on a scheduling problem where I need to schedule a set of n weighted jobs that are partitioned into m groups, where ...
43 views

### Submodulare welfare maximization: is an additive approximation algorithm known?

Sudmodular welfare maximization is the problem of allocating items among agents with different valuations, represented by submodular set functions, such that the sum of agents' values is as large as ...
74 views

### Find Combinations of fibonacci values to approximate a target value given $F(A,B,C,D) = (A + B + C) / D$

I am able to solve this using brute force but curious if there is a better approach. Given the function $F(A,B,C,D) = (A + B + C) / D$ where each variable is in the first 7 distinct values of the ...
1 vote
25 views

### Optimization: Turning a sparse graph of probabilities into the maximum likelihood DAG

I have a sparse matrix of probabilities that I want to turn into a DAG. If x[m,n] = pr it means that m is a descendent (direct or transitively) of n with probability pr. I want to construct a DAG over ...
1 vote
32 views

### Justification of smoothness of component functions

In stochastic optimization, the common objective is to minimize $f(x) = \frac 1N \sum_{i=1}^N f_i(x)$ (there is a different formulation, but it doesn't matter for this question). For nonconvex ...
135 views

223 views

### What is this graph problem, and how hard is it?

My problem is quite simple to state, so it surely must have a name: Given a graph $G=(V,E)$ with edge weights $w(e) \in \mathbb{Z}$, find a $V' \subseteq V$ that maximizes $\sum_{e \in E' } w(e)$, ...
1 vote
82 views

### A bound that follows from submodularity

I am studying Lemma 1 of this paper: The Adaptive Complexity of Maximizing a Submodular Function. The proof appears on page 11. I got stuck on this inequality: where $f$ is a monotone submodular set ...
1 vote
93 views

59 views

### Uniformly redistributing items across bins. What problem is this?

I'm trying to find reading material on a particular problem I'm interested in, but I don't know the terms to search. Problem assumptions/definitions: We have finite number of items I with weights [0, ...
1 vote