2
$\begingroup$

From what I've seen in the majority of algorithms publications, the focus of research is mainly towards improving the solutions to algorithmic problems in terms of efficiency or optimality in the case of approximation algorithms. My interest and hence my question is towards the generalization rather than improvement of algorithms, that is finding common ideas,techniques,optimization tricks that underlie the design or analysis process of algorithms and data structures. Examples of such patterns would be: lazy propagation in data structures, sqrt decomposition, incremental (sweep like) algorithms, smaller to larger merging (as in union by rank)...etc.

I am aware that these techniques would be explained when used in a specific instance of an algorithm, but the focus would still be on the algorithm rather than the design technique.

I appreciate if someone can provide guidance on where to look for such research and whether design techniques are valid as a research point.

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ I found your question a bit off topic, but I thought answers to question are maybe useful and I provided an answer. But the question is not well suited here, and you may ask such question at cs.se. $\endgroup$ – Saeed Jul 6 '16 at 21:35
  • $\begingroup$ I'd like to second Saeed's comment -- while clearly research on algorithm engineering is useful, it doesn't quite fit the "CS theory" mind set, which aims for results that can be rigorously proven. Results such as "this concept can be applied in a variety of applications, such as (1) and (2)" that would be outcomes of research on algorithmic design patterns don't fit this scheme, and hence does not fit to the self-understanding of the community. $\endgroup$ – DCTLib Jul 7 '16 at 8:36
  • $\begingroup$ Well, all of the examples i've mentioned in the question have their provable (maybe trivially) results. I don't see how the generalization or formalization of a technique or an algorithm be on the engineering side with the algorithm analysis/design belonging to the theory mindset. How is the reduction of a problem to another different from say observing the similarity in the structure of 2 algorithms and generalizing the idea. Just different forms of abstraction, aren't they? $\endgroup$ – Amir Nasr Jul 7 '16 at 22:35
  • $\begingroup$ @DCTLib forgive my ignorance, is there research on algorithm engineering even out of the theory community? $\endgroup$ – Amir Nasr Jul 7 '16 at 22:38
2
$\begingroup$

There are many general techniques and meta-theorems. Unlike software engineering, in TCS we don't want to repeat things similar to what the others did, we want to create something new or solve an unsolved problem, so it's not as easy as using lazy propagation in software development. Here I provide some examples but it's surely way far from the complete list.

  1. Parametrised complexity: kernelization, iterative compression, bidimentionality, ...

  2. Approximation algorithms: randomised rounding, scaling, ...

  3. In graph theory, based on structural hierarchies of graphs like bounded tree width graphs/excluded minor graphs/ bounded expansion graphs / nowhere dens graphs, there are different tools (like decompositions) and meta theorems (like Courcelle theorem).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ yikes, didn't know we had that level of control over the space of graph properties, as Courcelle's theorem $\endgroup$ – frogeyedpeas Jul 7 '16 at 22:01
  • $\begingroup$ Thanks for your answer. However, I would argue that meta-theorems or generalization of a technique isn't just mere repetition. Having a formalization of a pattern or idea would turn it into a reproducible idea that can be used in novel situations instead of reinventing it for every scenario. I believe every new idea in some way or another borrows from some old idea. $\endgroup$ – Amir Nasr Jul 7 '16 at 22:06
  • $\begingroup$ @AmirNasr, without doubt meta-theorems are important even for creating new ideas. My point was that in theory, IMO, it's interesting to build up over those meta theorems, unlike in engineering where it's more important to use patterns. $\endgroup$ – Saeed Jul 11 '16 at 21:32
0
$\begingroup$

In the context of heuristic search and optimization, I suggest reviewing the article "The metaphore exposed" by Kenneth Sörensen, where he deals with this generalization problem, that resulted in some limits that journals had to add in order to filter out proposals of algorithms that just exchange one metaphore (or lexicon) by another, without significant changes to the underlying method. There is also a Prezi that he made, here on this topic.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.