Questions tagged [heuristics]

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.

Filter by
Sorted by
Tagged with
2 votes
1 answer
152 views

Efficient tools for checking SMT formulas with two quantifiers ($\exists\forall$)

I would like to check a sort of SMT formulas with two quantifiers where universal variables range over finite/bounded integer domains. An example formula is $$\exists x \forall y ((y \ge 1 \land y \le ...
Giang Trinh's user avatar
0 votes
0 answers
134 views

Matching of two weighted graphs allowing one-to-many mapping

I am looking for a heuristic for a graph matching problem as follows. Given two graphs: $A$ (consisting of nodes $a_i$) and $B$ (consisting of nodes $b_i$). Typically the size of $B$ is larger than ...
Trung's user avatar
  • 1
0 votes
1 answer
161 views

Is it possible to prove that a general purpose integer factorization algorithm must contain a loop?

1) Let $A$ be a (general purpose) algorithm that factors $n$. Suppose $A$ contains a loop (which is hard to imagine if not impossible that it does not.) If $A$ contains nested loops then these loops ...
user avatar
1 vote
0 answers
36 views

Pass ordering for greedy local search algorithms

Apologies in advance for the slightly general question - I'm really looking for pointers to research / good keywords to look for. I have a problem with the following setup: I have a (finite) totally ...
DRMacIver's user avatar
  • 434
2 votes
0 answers
104 views

On the goal of learned clause database reduction in CDCL SAT solvers

Modern SAT solvers frequently reduce the size of their learned clause database in order to keep its size as manageable as possible. This has as effect not to slow down the speed of unit propagations. ...
RTK's user avatar
  • 311
9 votes
1 answer
552 views

Understanding performance of QFBV SMT solvers

SMT solvers such as Z3 or Boolector use a complex set of heuristics to solve problems. However, this also makes predicting the performance of such a solver for a given problem very hard. My question ...
bennofs's user avatar
  • 193
9 votes
2 answers
944 views

List of NP-hard problems, where there is active research in practical heuristics

I am looking for list of NP-hard optimization problems, where there is active research in practical heuristic for solving them and there are common benchmarks, which people try to beat. Examples ...
1 vote
1 answer
155 views

Practical/heuristic algorithm for multi set-cover

Consider a universe $N$ containing $n$ elements, and a collection of sets $\mathcal{C}$, over $N$. The $k$-multiset multicover (MSMC) problem is to cover all elements of the universe $N$ at least $k$ ...
Vivek Bagaria's user avatar
59 votes
6 answers
3k views

Theoretical explanations for practical success of SAT solvers?

What theoretical explanations are there for the practical success of SAT solvers, and can someone give a "wikipedia-style" overview and explanation tying them all together? By analogy, the smoothed ...
Joshua Grochow's user avatar
18 votes
2 answers
2k views

Are there any heuristic-free NP complete problems?

Are there any NP complete problems with no infinite subset of instances $\Phi$ such that membership in $\Phi$ can be decided in polynomial time, and for all $x \in \Phi$, $x$ can be solved in ...
Phylliida's user avatar
  • 1,132
6 votes
2 answers
385 views

Finding smallest context free grammar that generates a set of sets

Are there any results known about the size of smallest context free grammar that generates a set of sets? That is, I am given an alphabet $\Sigma$ as well as a set $S \subseteq \mathbb{P}(\Sigma)$ ...
Shahab's user avatar
  • 338
1 vote
1 answer
230 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 ...
Bora M. Alper's user avatar
0 votes
2 answers
858 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 ...
mnmp's user avatar
  • 175
3 votes
0 answers
141 views

Complexity of minimizing monotone arithmetical formulas

Let's say that I have a multi-variate arithmetical expression $A(x_1, \ldots, x_n)$ that uses addition and multiplication operations and is also in a very simple form of sums of products, e.g., $A_1(...
Shahab's user avatar
  • 338
1 vote
0 answers
73 views

Looking for reference proving polynomial-time bounds for A* search under specific conditions

In the textbook "Artificial Intelligence - A Modern Approach" (Russel, Norvig), it mentions that a sufficient criteria for the A* search algorithm to complete in polynomial time is for the heuristic ...
Bill Province's user avatar
4 votes
1 answer
207 views

Pathfinding search over a space with known changing costs

I'm working on a research project which involves iterative pathfinding over a space whose cells have danger values that change over time. More specifically, the danger values represent bad weather, ...
Arek Sredzki's user avatar
1 vote
1 answer
108 views

Approximations for the Stable Fixtures Problem

I have a set of N items, each with a subset of those items they can be paired with; each pair has a weight. I'd like to choose pairs to maximize the total weight, subject to each item being in at ...
Doctor J's user avatar
  • 113
2 votes
3 answers
324 views

Heuristic with worst-case exponential complexity

I have been working with some colleagues on a metaheuristic for an NP-Hard optimization problem. It is a genetic algorithm using a steady-state population replacement strategy (at each iteration a ...
drew's user avatar
  • 52
0 votes
1 answer
154 views

TSP heuristics for limited distance information

this is my first question on Theoretical CS. :) I've posted a similiar question on Mathoverflow and a friendly user advised me to post my question on this site. Problem: I'm looking for TSP ...
aGer's user avatar
  • 103
2 votes
0 answers
54 views

Hardness of Covering Arrays with $v=t=6$

A covering array is an $N \times k$ array with each entry as one of $v$ symbols, where for every $t$ columns all possible $v^t$ tuples appears at least once. The covering array number (CAN) is the ...
Ryan Dougherty's user avatar
5 votes
2 answers
2k views

Good algorithms to solve ATSP

What are some good neighborhood-based local search algorithms or strategies to solve the Asymmetric TSP ? I see many 2-OPT and K-opt based algorithms (e.g. Lin-Kernighan implementations), but I think ...
yafrani's user avatar
  • 171
-3 votes
1 answer
96 views

Is this NP-Hard or does a known optimal polynomial time solution exist? [closed]

Suppose we have 10 items, each of a different cost Items: {1,2,3,4,5,6,7,8,9,10} Cost: {2,5,1,1,5,1,1,3,4,10} and 3 customers {A,B,C}. Each customer has a requirement for a set ...
Hoxeni's user avatar
  • 1
2 votes
1 answer
252 views

Literature for Generalized Load Balancing

i am looking for literature on this kind of problem. $$ \begin{align} \min_x \max_k &\quad \sum_{i,j} x_{ij}c_{ijk}\\ \text{subject to}&\\ &\sum_j x_{ij}=1,&& \forall i\in\mathcal ...
AppleTree's user avatar
4 votes
1 answer
1k views

Heuristics for tsp without triangle inequality

Every heuristic for the traveling salesman problem that I know of (Nearest-Neighbour, Christofides, Held-Karp, ...) assumes that the triangle inequality holds. Are there heuristics to solve the tsp ...
Aerus's user avatar
  • 227
5 votes
0 answers
202 views

Exploring a DFA, with no feedback

Let $M=(\Sigma,S,s_0,\delta)$ be an (unknown) deterministic finite-state automaton (DFA), with alphabet $\Sigma$, statespace $S$, start state $s_0 \in S$, and transition relation $\delta$. I want to ...
D.W.'s user avatar
  • 12.1k
19 votes
5 answers
2k views

Fast treewidth algorithms

I would like to compute the treewidth of a graph. There are really good heuristics for other NP-hard graph problems such as VF2 for subgraph isomorphism, with code available in igraph for example. I ...
Simd's user avatar
  • 3,902
5 votes
1 answer
2k views

Approximation for metric TSP: Worst case using nearest neighbor heuristic?

I'm looking at different heuristics that approximate solutions for a metric Traveling Salesman Problem. I was wondering if there is a worst case ratio of tours calculated by the nearest neighbor ...
Johannes's user avatar
  • 153
6 votes
3 answers
577 views

Simplification of weighted NFA

What options does one have for the simplification (meaning reduction in the number of states) of weighted NFA over the probability semiring? From my understanding one can determinize, and then ...
hr0nix's user avatar
  • 81
4 votes
0 answers
160 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 $\{1,2,\dots,n\}$...
D.W.'s user avatar
  • 12.1k
4 votes
1 answer
133 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 ...
T. Huynh's user avatar
9 votes
2 answers
1k 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 $200$...
Alejandro Piad's user avatar
8 votes
3 answers
396 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 + ...
Denis's user avatar
  • 323
0 votes
0 answers
135 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 ...
MrGomez's user avatar
  • 163
6 votes
0 answers
476 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 (which ...
Kallikantzaros's user avatar
8 votes
0 answers
196 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 ...
luksen's user avatar
  • 81
7 votes
1 answer
499 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 ...
Magnus Lie Hetland's user avatar
5 votes
2 answers
284 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 ...
user197284's user avatar
1 vote
0 answers
91 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 ...
dj1's user avatar
  • 11
13 votes
2 answers
585 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 ...
zzzbbx's user avatar
  • 203
5 votes
1 answer
168 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 ...
zenna's user avatar
  • 835
13 votes
3 answers
1k 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 ...
Suresh Venkat's user avatar
14 votes
4 answers
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$ ...
Suresh Venkat's user avatar
4 votes
4 answers
650 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 ...
shuhalo's user avatar
  • 1,165
2 votes
3 answers
394 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 ...
Berty's user avatar
  • 169
9 votes
1 answer
345 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 (...
7 votes
0 answers
161 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 ...
Neel Krishnaswami's user avatar
25 votes
5 answers
10k 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 ...
asc's user avatar
  • 353
7 votes
0 answers
355 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 ...
Suresh Venkat's user avatar
2 votes
2 answers
912 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) ...
Fabian Schuh's user avatar
2 votes
1 answer
897 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 of ...
YAKOVM's user avatar
  • 189