A heuristic is a procedure that can apply generically to many problems (for example gradient descent, alternating optimization, simulated annealing) but will typically not have formal guarantees associated with its use.
4
votes
0answers
42 views
Find index set partition that has large projections
I have a multiset $S$ of $n$-bit strings. Let $1_S(s)$ denote the number of times that string $s$ appears in $S$, i.e., the multiplicity of $s$ in $S$. I want to find a partition of ...
3
votes
1answer
85 views
Balanced partitioning of a set of axis-parallel 2D rectangles
Fix a constant $0<\alpha<1/2$. The problem is the following. Suppose there are $N$ axis-parallel rectangles on the 2D plane with weights $w_1, w_2,\ldots, w_N$ and with coordinates all in the ...
5
votes
0answers
94 views
Generating interesting combinatorial optimization problems
I'm teaching a course on meta-heuristics and need to generate interesting instances of classic combinatorial problems for the term project. Let's focus on TSP. We are tackling graphs of dimension ...
7
votes
3answers
265 views
Find the nearest $d+1$ corners of a cube in $\mathbb{R}^d$
How can one find the $d+1$ corners of the unit cube in $\mathbb{R}^d$
nearest a point $x$ in the cube ?
Use the L1 metric, so that in 4d
|$x$ - 0000| = $\sum {x_i}$,
|$x$ - 0001| = $x_3 + x_2 + x_1 + ...
0
votes
0answers
98 views
Tractability of mutual information-augmented ensemble classification algorithms
I am seeking to augment random forest classification using Shannon-Weaver mutual information as a metaheuristic to partition candidate datasets. Specifically, I am trying to determine if such an ...
6
votes
0answers
139 views
Cheapest dissection of a grid polygon into rectangles with cost
My problem:
Dissect a grid polygon into rectangles. (A grid polygon is a rectilinear polygon all of whose vertices have integer coordinates.)
The rectangles must be taken from a predefined set ...
8
votes
0answers
167 views
what is the best heuristic to solve 3AP with Euclidean costs?
As is well known, assignment problems for $n$-partite graphs, with $n$>2 are NP-hard, where as assignment problems on bipartite graphs can be solved in polynomial time using the Kuhn's Hungarian ...
7
votes
1answer
243 views
Does this bin packing problem have a name?
My problem is related to the standard bin packing problem (where you have bins of capacity $1$, items of capacity $(0,1]$, and want to pack the items into as few bins as possible), but there are a ...
5
votes
2answers
201 views
Self-organizing Sequential Search Heuristics
I've read the paper by Jon L. Bentley "Amortized analyses of self-organizing sequential search heuristics". It deals with different schemes for improving linear search. (such as after every access to ...
1
vote
0answers
76 views
Resources to get started on fractional graph coloring algorithms
I'm interested in using fractional graph coloring algorithms/solvers to solve a problem, where is a good place to start? I'm looking to find basic/introductory to state-of-the-art algorithms more ...
11
votes
2answers
415 views
Decentralized algorithm for determining influential nodes in social networks
In this paper by Kempe-Kleinberg-Tardos, the Authors propose a greedy algorithms based on submodular functions to determine the $k$ most influential nodes in a graph, with applications to social ...
5
votes
1answer
134 views
Local Smoothness vs optimisation in combinatorial problems
Local smoothness is often mentioned in literature analysing different heuristics and meta-heuristics for combinatorial optimisation. What is meant precisely by local smoothness is often left out, but ...
12
votes
3answers
412 views
Successful application of branch-and-bound methods for NP-hard problems
Branch and bound is an effective heuristic for search problems, and Wikipedia lists a number of hard problems where branch-and-bound has been used. However, I haven't been able to find references to ...
10
votes
3answers
610 views
Theoretical study of coordinate descent methods
I'm preparing some course material on heuristics for optimization, and have been looking at coordinate descent methods. The setting is here a multivariate function $f$ that you wish to optimize. $f$ ...
4
votes
3answers
424 views
A search problem and no algorithm for it
I would like to learn about the following search problem, in particular, which kind of algorithms exist for it.
Suppose we have a huge search space $S$. For each element $s \in S$, we have the weight ...
2
votes
2answers
274 views
Heuristics for graph bisection
i'm trying to find an algorithm
that will divide my graph in 2 parts by telling me what connections should be broken
but the 2 parts should contain about the same number of nodes
its for a practical ...
9
votes
1answer
266 views
Heuristics for Optimization
Since it's Friday, it's time for a CW question. I'm looking for heuristics that have wide use in optimization problems. To limit the scope to more 'theory-friendly' heuristics, here are the rules ...
6
votes
0answers
118 views
Does the cohomological approach to Boolean complexity nicely model any BDD heuristics?
In this question, I learned that complexity theorists had considered using Grothendieck topologies to model Boolean circuits. This has not, apparently, led to any new lower bounds yet, but I'm not so ...
19
votes
4answers
857 views
What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?
Stable Marriage Problem: http://en.wikipedia.org/wiki/Stable_marriage_problem
I am aware that for an instance of a SMP, many other stable marriages are possible apart from the one returned by the ...
6
votes
0answers
150 views
Good MCMC methods for exploring the space of independent sets
Let $G$ be an edge-weighted graph, and let (S, V-S) be a feasible pair if S is a maximal independent set. The weight of a feasible pair is computed by finding for each element of V-S the lightest edge ...
2
votes
1answer
569 views
Ant colony optimization for traveling salesman problem with changing graph-nodes/vertices
Are there any publications focusing on solving TSP with ant colony optimization that consider small changes in the graph's nodes or vertices?
So what I have is:
a traveling salesman problem (TSP)
...
2
votes
1answer
308 views
Heuristics for the minimum-weight $k$-clique problem
Hello
Does someone have an idea for heuristics for the problem:
Given undirected weighted(weights on edges) complete
graph $G(V,E)[|V|=n,|E| = m]$, find a clique of size $k < n$(k is number ...
