Skip to main content

New answers tagged

2 votes

Applicability of approximation algorithms vs meta-heuristics in practice

I find it weird that none of the previous answers mention the obvious trivial approach that anyone can take in practice, which is to run both a heuristic (or meta-heuristic) and an approximation ...
user21820's user avatar
  • 727
3 votes

Applicability of approximation algorithms vs meta-heuristics in practice

In academia, theorists are interested in what they can prove to work on all inputs. In industry, practitioners are interested in what works well enough on most of the cases they have to deal with in ...
D.W.'s user avatar
  • 161k
5 votes
Accepted

Applicability of approximation algorithms vs meta-heuristics in practice

Well, practitioners, as far as I have noticed, do not show a very stark difference between heuristics and approximation algorithms. The upside that the approximation algorithms community provides with ...
Sriram's user avatar
  • 275
3 votes
Accepted

Maximum distance between two points of a polyhedron

The maximum distance between points in the polytope is called diameter (terminology note: ^1), or inner 1-radii (times two) [2] of the polytope $P$. A closely related problem is the norm maximization ...
pcpthm's user avatar
  • 2,652
-1 votes

Approximation algorithms for integer convex quadratic programs over a linear subspace

There are numerous research papers on solving (mixed) integer quadratic programs (MIQP) such as paper #1, paper #2 and paper #3. These papers also give you pointers to various existing approaches for ...
codeR's user avatar
  • 1,157
4 votes
Accepted

Approximation algorithms for integer convex quadratic programs over a linear subspace

The problems is equivalent to the closest vector problem (CVP). This is because $Ax=b, x\in \mathbb{Z}^n$ is a lattice. And the quadratic $\frac{1}{2} x^\top Q x + c^\top x$ can be written as $\frac{1}...
Sriram's user avatar
  • 275

Top 50 recent answers are included