Questions requesting papers in the literature on specific, narrow issues.

learn more… | top users | synonyms

1
vote
0answers
18 views

Universal algorithm testing framework

Currently I'm working on my thesis. I'm writing about subgraph isomorphism problem and various algorithms, solving this problem. One of my task is to integrate that problem in a testing framework, ...
0
votes
1answer
14 views

What is MongeElkan distance between words?

i used CosineSimilarity, EuclideanSimilarity, LevenshteinSimilarity and known about how it ...
5
votes
0answers
16 views

Determining the minimum number of edges to add in order to be 3-connected

A graph $G$ is said to be $3$-connected if there exists no cutting-pairs in our graph. As far as I know, it is possible to determine if a simple graph is $3$-connected in $O(n)$ time (example: ...
0
votes
1answer
28 views

How to enumerate minimal covers of a set

I have a set $S$ and a set $P = \{P_{1},...,P_{n}\}$ with $\bigcup P_{i} = S$. I want to find all the inclusion-minimal subsets of $P$ that are covers of $S$. What is the best algorithm for ...
3
votes
0answers
20 views

Name of a type of code similar to block codes

I've encountered a system where I need to construct a sort of quasi block code: We want to communicate a symbol $s$ from a finite-sized alphabet $\mathcal{S}$ using $N$ segments of information. ...
9
votes
3answers
856 views

Has the graph isomorphism problem been solved?

Wikipedia's graph isomorphism problem page would seem to indicate that, no, it has not been solved. However, a friend of mine pointed out A Polynomial Time Algorithm for Graph Isomorphism . I am not ...
2
votes
2answers
72 views

What is a conventional format for presenting algorithms?

I'm writing a technical paper and the review committee wants my methodology to be represented in a conventional algorithm format. I've been searching all over the web for the conventional structure ...
4
votes
4answers
647 views

Is there a method for automatic runtime analysis of algorithms?

I am wondering, is there a method for automatic runtime analysis that works at least on a relevant subset of algorithms? I googled "Automatic algorithm analysis" which gave me this but it is too ...
2
votes
1answer
45 views

NP completeness of closest vector problem

Let $\mathcal{B} = \{v_1,v_2,\ldots,v_k\} \in \mathbb{R}^n$ be linearly independent vectors. Recall that the integer lattice of $\mathcal{B}$ is the set $L(\mathcal{B})$ of all linear combinations ...
5
votes
0answers
34 views

Are there Some Pairs Shortest Paths Algorithms?

I know that there are All Pairs Shortest Paths algorithms. But I am not sure if they are effective if I am trying to solve the Pairs-Shortest-Path problem for a subset of my vertexes. The properties ...
2
votes
1answer
47 views

Natural Language Parser that can handle syntactic and lexical errors

I have some background in natural language processing and I know that all parsers (top down or bottom up, or mix), at least when I studied just about a few years ago, cannot handle any error. A small ...
5
votes
1answer
51 views

What is the practical relevance of textbook mutual exclusion algorithms?

There's been a fair amount of research on mutual exclusion algorithms - e.g. a lot of it is presented in classic textbooks such as The Art of Multiprocessor Programming, where an entire chapter is ...
0
votes
0answers
4 views

Hierarchical reinforcement learning exploration methods

One of the extensions to hierarchical reinforcement learning is change the degree of randomness that is applied while choosing an action. It is possible to increase the randomness to encourage ...
0
votes
0answers
9 views

Reference for Motivation of WSN Localization in 3D

I need references to motivate the reader about 3D Wireless Sensor Network Localization problem. I have found many references about 2D WSN localization, however, there is a lack of 3D WSN Localization ...
2
votes
1answer
72 views

Algorithms online problems

I'm trying in vain to find some online (classical) algorithms problems to deeply exercise "complexity" and maybe see (even try) mathematical demonstrations. As far as I can see, the sites that I ...
2
votes
2answers
51 views

Is single-source single-destination shortest path problem easier than its single-source all-destination counterpart?

Dijkstra's algorithm (wiki) and Bellman-Ford (wiki) algorithm are two typical algorithms for the single-source shortest path problem. Both of them compute distances for all nodes from source $s$. ...
0
votes
0answers
53 views

Logic and Functional programming

I have a subject Introduction to logic and functional programming but the course is not provided in detail. This is the provided course. Introduction to declarative programming paradigms. The ...
3
votes
1answer
49 views

Where does the terminology of open addressing resp. closed hashing come from?

One of the basic methods of hashing is called "Open addressing, or closed hashing" according to wikipadia (and several books). Why the names "open" and "closed", and why these seemingly contradictory ...
1
vote
0answers
39 views

References for wearable e-health systems for biosignal based health monitoring [closed]

Ubiquitous computing refers to "information technology and computer power, which in principle pervade all everyday objects" (see Friedewald and Raabe, 2010). A similar form is wearable computing, ...
2
votes
1answer
79 views

Which algorithms have runtime recurrences like $T(n) = \sqrt{n}\,T(\sqrt{n}) + O(n)$?

The algorithms using the "divide and conquer" (wiki) design strategy often have the time complexity of the form $T(n) = aT(n/b) + f(n)$, where $n$ is the problem size. Classic examples are binary ...
1
vote
1answer
22 views

Semantic information collections on the web. (Semantic Wikipedia)

There are lots of technologies supporting semantic information markup even as wiki software. I am wondering if there is any kind of broad information collection project like Wikipedia which features ...
2
votes
1answer
55 views

What is the lower bound for finding the third largest in a set of $n$ elements?

The problem is easy to describe: What is the lower bound for finding the third largest in a set of $n$ elements? Particularly, do we have to know both the largest and the second largest for ...
1
vote
1answer
35 views

A reference for pseudocode for Monge-Elkan algorithm?

Does anyone have a good reference to pseudocode for Monge-Elkan string comparison algorithm or a single class Java/C implementation? I have access to original two papers, but they do not show the ...
0
votes
1answer
68 views

Reference request for coding Knight's Tour

Could someone give an easily accessible reference containing an algorithm that could be conveniently implemented into a code for computing Knight's Tour (preferably also with fairly good efficiency)?
5
votes
3answers
112 views

Complexity of natural language processing problems [closed]

Which natural language processing problems are NP-Complete or NP-Hard? I've searched the natural-lang-processing and complexity-theory tags (and related complexity tags), but have not turned up any ...
0
votes
0answers
23 views

Patent-free algorithm for labeling a MRF/CRF

At the moment I'm implementing a video segmentation algorithm for moved foreground / background. In the literature often a graph-cut algorithm is used, which is patented by US6973212. Are there any ...
0
votes
0answers
13 views

Is there an application area that sensors are on planes and we know the local positions of the sensors, but not the global positions?

I am currently writing the motivation of my thesis. And the answer to this question is very crucial for me: I am working on wireless sensor networks. Say that, there are a number of planes, for ...
9
votes
3answers
94 views

Recipe book for SAT encodings?

SAT solvers are getting more and more efficient in solving large instances and are being used as back-ends in various contexts. Every time one wants to use them to solve a problem in a specific ...
1
vote
0answers
17 views

Equivalence of data-flow analysis, abstract interpretation and type inference?

@Babou's answer to a recent question reminds me that at one time I think I read a paper about the equivalence (in terms both of the facts that can be inferred or proved and the time complexity of ...
1
vote
0answers
20 views

Given a set of sets and a storage area, find an order that minimizes the sum of the differences between each set and the storage area

This problem is based on an order picking problem with a forward area. The problem description is as follows. We have a warehouse with a set of items $I$ and a forward area $F$ of size $k$. Each ...
3
votes
1answer
53 views

Maximum minimal set coverage

Suppose we are given a universal set $U$ and a family of subsets of $U$, denoted by $F$ (elements in $F$ are subsets of $U$). We assume that all elements in $F$ can cover $U$, i.e., $U\subseteq ...
2
votes
0answers
45 views

Recent Garbage collection survey paper

Many years ago I read a GC survey paper that was updated every few years with advances; I tried to find such a paper today to point a questioner on Stackoverflow at. However all I can find is very ...
4
votes
0answers
34 views

Languages recognized by finite state automata of polynomially growing size

In the course of my research (condensed matter physics stuff), I stumbled over the following concept: The class of regular languages can be defined via finite state machines (FSM): A language $L$ ...
7
votes
0answers
52 views

Exponential analogue of NC?

Nick's Class (NC) is the class of problems that can be decided in poly-log time using a polynomial number of processors. I want to know about the exponential analogue, which would cover problems that ...
3
votes
0answers
28 views

Term for index-like data structures

There's a class of data structures where you preprocess some other data structure in order to answer queries about it more efficiently. That includes trivial things like sorting/hashing, less trivial ...
2
votes
0answers
27 views

Difficulty of Integer Linear Programming vs. Mixed Integer Linear Programming

I have recently been working on an applied project where I have to solve optimization problems. I have found that it is much easier to solve an integer linear program (ILP) as opposed to a ...
3
votes
0answers
38 views

Status of Research Problems in Motwani and Raghavan

One nice aspect of Motwani and Raghavan's classic textbook, Randomized Algorithms, is that the notes for many chapters include open questions marked as "research problems." However, the textbook is ...
1
vote
0answers
40 views

Teaching computer science in developing countries - any literature?

I've been teaching computer science in a developing country and I've seen how the everyday challenges are very different from what I was used to. The students are different. The teachers are ...
1
vote
1answer
23 views

Reference proof for Second-Order Logic captures Polynomial-Time Hierarchy

I'm looking for a complete proof of $\mathrm{PH=SO}$. The (admittedly few) textbooks and papers i've looked at all either state that it's a corollary from Fagin's Theorem, or leave it as an exercise ...
1
vote
1answer
31 views

Feasibility of linear inequalities with binomial variables

I have a system of linear inequalities of the form $A^t x <= b$ where each of the $x_i$'s is a binary variable in $\{0, 1\}$. Are there any known fast and practical algorithms that can find a ...
2
votes
2answers
43 views

Method for measuring the 'similarity' between FSA grammars?

I'm working with a pattern matching algorithm that generates an acyclic finite state automaton that accepts a given text string and all its substrings. The FSA algorithm is being run on a symbolic ...
0
votes
0answers
8 views

Hierarchical learning in a non-static environment

I've been reading about hierarchical reinforcement learning (HRL), in particular it's application to a simple delivery task as show here. While reading the paper, I noticed that the environment ...
8
votes
2answers
200 views

Are there established complexity classes with real numbers?

A student recently asked me to check an NP-hardness proof for them. They performed a reduction along the lines of: I reduce this problem $P'$ that is known to be NP-complete to my problem $P$ ...
5
votes
2answers
218 views

Direct NP-Complete proofs

I'm just starting to learn about NP-completeness. While I understand that reducibility plays a key role in this, I'm astonished how few problems I've been able to find who's proof that they are ...
0
votes
0answers
29 views

A bound for the minimum vertex cover of scale-free graphs

For a complete graph, the size of minimum vertex cover is $n-1$. I was wondering whether there exist an upper bound (or an expected value or upper bound) for the size of minimum vertex cover for ...
3
votes
0answers
61 views

What kind of scheduling problem is this?

I'm working on a problem and would like to do some research on similar problems to help refine my approach. Can anyone help me identify what kind of problem this is or, at least, what kind of ...
5
votes
1answer
52 views

Base conversion puzzle

Here's an old puzzle: Let $s$ be a string of decimal digits ($s[i] \in \{0,\dotsc, 9\}$). Define a function $f(s)$ as follows: Interpret $s$ as a decimal number, $n_{10}$, and convert $n$ to its ...
4
votes
3answers
106 views

Most time-optimal parallel algorithms to calculate the determinant and inverse of a matrix

I am writing a numeric library to exploit GPU massive parallelism and one of the implemented primitives is a matrix class. Naturally I require a determinant and inverse function for this class and I ...
4
votes
1answer
26 views

Probabilistic hardness of approximation or solution of NP-hard optimization problems under a probabilistic generative model for input data

So in biology (DNA sequences), sequence alignment is a generalization of longest common subsequence where an alignment of two sequences is scored typically with a linear function of how many spaces ...
3
votes
0answers
65 views

Algorithms that are similar to Dynamic TIme Warping

Dynamic time warping (DTW) is an algorithm in time series analysis for measuring similarity between two temporal sequences which may vary in time or speed. Here are some explanations of DTW: Dynamic ...