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 ...