# All Questions

42,773 questions
Filter by
Sorted by
Tagged with
11 views

16 views

### Is this variant of Subset Product NP-hard?

Given a set $Y$ with whole number positive divisors of $N$, is there a combination of divisors that have a product equal to $N$? Does Subset Product remain NP-hard when whole number divisors are only ...
11 views

### How many code alphabets do we need in order for a Huffman Code and a Shannon-Fano Code to be the same for the same source symbols probability

For example, If we have a source with alphabet $\{x, y, z\}$ with probabilities $\{0.5, 0.3, 0.2\}$ , What is the smallest integer $\mathbf{D}$ such that the expected length of a D-ary Shannon-Fano ...
39 views

### Is the right quotient of a regular language respect to another regular language a regular language?

Will the language $\{w\in L_1\mid \exists v, wv\in L_2\}$ be regular if $L_1$ and $L_2$ regular languages?
10 views

### How to maintain consistency in replica in distributed system

In a distributed system using transactions between the databases of different sites, how do we control reads and writes so that the replicas remain “consistent”? What different levels of consistency ...
27 views

### Hoeffding's inequality applicability for sample complexity

I am trying to determine some bounds for sample complexity. Suppose we have a bounded loss function $\ell$ and target function $f:\mathcal{X}\to\mathcal{Y}$. Hypothesis $h$ is learned, then the ...
21 views

### Cluster 3d points with constraints

I have some 3d point cloud I wish to cluster into some number of clusters. I have the probability of two points being in the same cluster given as some function of their relative locations, with the ...
20 views

### Getting rid of "FG" in a LTL equation

i am currently struggling with a Linear temporal logic equation: $$\phi=FG( \lnot a\lor X \lnot a )$$ For my understanding, it means that starting at a certain point in the future, proposition a can ...
14 views

### Is integer multicommodity flow problem is NP-hard?

As Wikipedia states the time complexity of Integer Linear programming(ILP) is NP-hard, so this means integer multicommodity flow problem is also NP-hard?
712 views

### How exactly is the process of showing a problem to be NP-Complete a proof by contradiction?

The steps involved in proving that a problem is NP-Complete are fairly straightforward to follow, it's the logic behind why the proof is valid that's really throwing me for a loop. Okay so an easy one:...
28 views

### Is this set covering problem NP-Hard?

Consider this variant of set covering problem. Input: a collection of sets S = {s$_1$, s$_2$, ... s$_n$} and an universal set U, in which s$_k$ $\subseteq$ U. (1<=$k$<=n) The problem is, divide ...
23 views

### chromatic number is np-hard

I'm referring to a question in this book: Algorithms by Jeff Erickson, link:http://jeffe.cs.illinois.edu/teaching/algorithms/notes/J-approx.pdf, in particular, pg.21, Q11. The author mentioned that ...
29 views

### single machine job scheduling problem maximizing the profit

So I have a single machine job scheduling problem as detailed below. I've been using multiple greedy algorithm approaches and computing the maximum profit among them to come up with the best schedule, ...
3k views

### Real life examples of *zero* weight edges in graphs

The meaning of edges with zero weight in a weighted graph questions me for a long time, and I even asked a related question previously. Yet, when I recently read here a question on real life example ...
21 views

### Primal and Dual problem of SVM

The primal problem of SVM is about maximizing the Lagrangian function with respect to w while the dual problem is about maximizing the Lagrangian function with respect to α Is this statement correct?
### Proof that every vertex in the same strongly connected component of a graph $G$ happen to appear in the same DFS tree
My Professor proved that every vertex in the same strongly connected component of a graph $G$ happen to appear in the same DFS tree (which is also called tree of predecessors). He proved it by ...