# All Questions

12,796 questions
Filter by
Sorted by
Tagged with
5k views

### LP formulation for if-conditions

I have the following LP: /* Objective function */ min: 1 w + 2 x + 0.5 y + z; /* Variable bounds */ w + x <= T1; w + y = U1; x + z = U2; T1 = 50; U1 = 70; U2 = 25; In this case U1 + U2 > T1 and ...
• 211
2k views

### Meaning of P=NP? depends on space-time geometry ?

This question is about Page 125 of the book "Cellular automata in hyperbolic spaces: Volume 2" By Maurice Margenstern, Publisher Archives contemporaines, 2008. http://books.google.com/books?id=...
• 273
237 views

### Approach to implementing an STM for a student [closed]

A student has implemented a scheme interpreter in scheme and then in C, and a scheme compiler in scheme. That student is now interested in implementing a STM (Software Transactional Memory) system ...
• 2,581
2k views

### Complexity of edge coloring in planar graphs

3-edge coloring of cubic graphs is $NP$-complete. Four Color Theorem is equivalent to "Every cubic planar bridgeless graphs is 3-edge colorable". What is the complexity of 3-edge coloring of cubic ...
265 views

### What algorithms/reading matter would you recommend on resolving transactions / read-write locks?

A simplified classical database transaction can be viewed as: reading M items performing some calculation based on those reads writing some N results based on these calculations, which may include ...
767 views

### How to know if X and Y have coauthored?

Is there any tool where one can figure out if two people have coauthored or not? Like the tool where one can figure out somebody's Erdos _number_ .
21k views

### What kind of mathematical background is needed for complexity theory?

I am currently an undergraduate student, bound to graduate this year. After graduation, I am considering to work towards a TCS master/PhD. I have begun wondering what fields of mathematics are ...
• 3,786
463 views

### Graph decompositions for combining "local" functions of vertex labelings

Suppose we want to find $$\sum_x \prod_{ij \in E} f(x_i,x_j)$$ or $$\max_x \prod_{ij \in E} f(x_i,x_j)$$ Where max or sum is taken over all labelings of $V$, product is taken over all edges $E$ for a ...
• 4,701
166 views

### Finding the set of paths of smallest cumulated length that cover a given set of patterns

First of all, sorry for this long and maybe not very informative title... Context: Let $G=(V,E)$ be a directed graph, let $v_0 \in V$ be the initial node of paths that I will consider in the graph. ...
• 3,063
12k views

### One Stack, Two Queues

background Several years ago, when I was an undergraduate, we were given a homework on amortized analysis. I was unable to solve one of the problems. I had asked it in comp.theory, but no ...
• 16.5k