Tagged Questions

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.

39 views

Are there any heuristics that works solely on graphs?

I'm exploring heuristics in A* and apparently all heuristics require coordinates of all the locations to calculate a h-cost. This is fine if you are working on grids, but what if you need to work ...
161 views

Packing $n$ objects into $m$ bins whose size is variable

Assume we have $n$ fixed size objects with sizes $O_1$ to $O_n$. Also, assume we have $m$ bins with size $a \times B_1$ to $a \times B_m$ in which $a$ is a real number and $a\ge1$. We want to put ...
118 views

127 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 ...
320 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 (...
181 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 ...
330 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 ...
253 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 ...
82 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 ...
526 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 ...
147 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 ...
932 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 ...
2k 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$ ...
592 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 ...
323 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 ...
301 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 (...
131 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 ...
2k 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 ...
239 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 ...
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 ...