2022 Developer Survey is open! Take survey.

# Tag Info

Accepted

### Set the parameters of a Erdos-Renyi graph generator to get a specific mean degree

Average degree and mean degree are the same. In the $G(n,m)$ model, the average degree is $2m/n$. In the $G(n,p)$ model, the expected average degree is $np$. The actual average degree has normal ...
Accepted

### Why arrival process of packets at a switch is not a Poisson Process?

"new flow arrivals" means "arrivals of new flows". A flow is a TCP connection (roughly); each individual TCP connection is a separate "flow". So, this is talking about new TCP connections, and the ...
Accepted

### Requiring at least one alldiff constraint to be satisfied converted to SAT

If you want to model an alldiff() constraint in SAT, there are several options. Here are two different options you can try: One way is to expand $\text{alldiff}(x_1,\dots,x_n)$ into $n(n-1)/2$ ...
Accepted

### How to impose Euclidean distance constraint in a constraint satisfaction problem without quadratic constraints?

You can't. You can't express this without using quadratic constraints. Your requirement is about Euclidean distance. The Euclidean distance is inherently quadratic. To be more precise about that: ...
Accepted

### How to represent circles in x-y coordinates

This answer considers two cases: the overlapping relation between two disks, which is a very simple problem. the ovelapping or covering of a disk by a set of other disks, which is somewhat harder in ...

### Converting reality to Petri net

I'm not sure how to approach your particular problem, but here is an attempt. Consider the recipe you are using as a collection of steps, some of which depend on others; for a salad you might have "...

### Matching two people. One has 7% in common with the other. The other has 70% in common. What's a fair match score?

It seems you're looking for a symmetric set similarity measure. (Symmetric since, as you point out, $A$ should match $B$ as much as $B$ matches $A$. Set similarity since each person's preference is ...

### Boat riddle as a combinatorial optimization problem?

The river crossing problem using integer programming is solved by Börndorfer et al. in .  Borndörfer, Ralf, Martin Grötschel, and Andreas Löbel. Alcuin's transportation problems and integer ...
Accepted

### Please explain linear programming as seen for this load balancing problem

How do you physically characterize the load of a processor, is it equivalent to CPU utilization? The program is modelling load like this. Whether you feel it's a good way to model load, and whether ...

### Terminology needed for the computational solution to the Rubik's Cube

Kociemba wrote very nice algorithm, which is the fastest working algorithm returning optimal or almost optimal solution very efficiently. If you want to derive your own system, try in steps: 0) ...
Accepted

### Integer linear programming formulation of formula in DNF

You are looking for a four-dimensional convex polytope that contains all of the points $(x_1,x_2,x_3,x_4)$ that satisfy your condition, and but not any point $(x_1,x_2,x_3,x_4)$ that doesn't satisfy ...
Accepted

### How can union-find algorithm be used with "real" data

Short answer: indirection. For instance, each object could have a field that contains an index into the id array. Or, you could use pointers. Standard union-find ...
Accepted

### How to model references in an ontology

If you want to say something about an RDF triple (i.e., an rdf:Statement), you can use reification: ...

### Are objects appropriate for modeling the real world?

Object-oriented programming languages are designed to support programming. Whether they "properly" model the real world is beside the point and not the primary goal. So, when you ask "...

### Terminology needed for the computational solution to the Rubik's Cube

have not heard of use of abstract languages to model the rubiks cube. however, there is a huge amount of group theory intrinsically associated with it, and there are natural ways to represent group ...

### Terminology needed for the computational solution to the Rubik's Cube

It sounds like you want to compute the intersection of two languages. Depending upon what kind of languages you are looking at and how they're represented, you might look into the "product ...
Accepted

### Modelling a dependency of multiple transitions on data in one place

I do not know if there is a variant of Petri nets that captures your intent exactly -- there probably is, there are so many -- but the feature can be expressed with regular Petri nets. Just add a ...
Accepted

### Matching two people. One has 7% in common with the other. The other has 70% in common. What's a fair match score?

If you want to weight then cosine_similarity is an option. What this does is weight items that are not common in the population higher. Not sure how but I would base uniqueness on the two ...

### Integer linear programming formulation of formula in DNF

I will use a = 1, b = 2, etc... If a is set then c must be false and EITHER b or d must be true: 10a + c <= 10 10a + b + d <= 11 10a - b - d <= 9 ...