Saeed Amiri

@domotorp, let fix one thing, you really want nn to discover dijekstra (or so), not just solving the shortest path, am I right? If this is the case, as I said earlier, it seems it is hard to train it. Maybe we get sth very close to optimal but not the optimal. I don't know what would be the input to the network. I almost don't know anything about nn, but I don't know what could be the formulation of the input (if we do not concentrate on datasets).

For chess, despite the fact all possible positions are theoretically restricted, we cannot reach that theory restriction in practice. So the engines (like stockfish) are just a benchmark, they are not perfect (unlike the Dijkstra). I didn't watch Kaveh's video but I guess it is again a comparison with non-perfect algorithms/machines etc. P.S: Maybe the problem is that I took those words very series and interpret them literally into a perfect algorithm. If we want a reasonable algorithm nn might be fine, for perfection I doubt, at least I think they aren't perfect right now, even for chess.

@domotorp, if we apply the restriction the problem could be easier, e.g. I remember a colleague of mine did his bachelor thesis on shortest paths in grid graphs by nn and genetic algorithms (it was for robotic purposes). He got reasonable results while he didn't train the network by all possible grid graphs. The main issue is that those algorithms are not optimal. So expecting an excellent algorithm like Dijkstra really is something hard.

Or maybe it was this comment (all of them have same spirits): "why playing chess should be easier than Dijkstra.". I said either you missed the point that for chess we have one very simple input but for shortest paths we have infinitely many possible inputs, or you know this but you are looking for an algorithm not solving just a specific instance

@domotorp, maybe I missinterpreted your discussions in comments. I guess this was that comment: "I wonder how AlphaGo would play Go on a different board size ...." that said, my feeling was that you want it to provide a self adjusting algorithm (infinite many inputs). So I thought for the case of shortest path you want ask nn to give an algorithm that solves any input instance. E.g. the nn suggested in the above link, as my understanding is biased by a data set, but the chess example that you discussed is not biased by any dataset (I guess similarly goes for go).

@Sasho, yes I also think the nn outputs some evaluation function. I say nn doesn't generate an algorithm itself.

@domotorp, are you looking for solving problems by nn or you want to design algorithms by nn (and those algorithms solve the problems). As I understand you want nn to generate sth like dijekstra algorithm not solving a particular instance. If this is the case, the above paper doesn't seem to help.

@SashoNikolov, as I understand from page 3 of that paper, it doesn't use nn to provide an algorithm for those problems. It directly solves those problems by nn. I think domotrop asked for designing algorithms by nn not solving problems by (generic) nn algorithm. So the output of the network should be an algorithm not a min vertex cover for particular instance.

Chess is very simple to describe, few possible moves and the final outcome has 3 possibilities. Now consider the case of the shortest path, what are possible outputs? Given a weighted graph and two vertices, how do we describe an output as a good output? Comparing it to another output? then to which output? I don't say designing an NN algorithm for the shortest path is too hard, as I don't know much about NN, but when you talk about a generic algorithm for a specific problem you should note that maybe the proper definition of the problem is not that easy in the first place.

Thanks :-)

Thanks for enlightening about touristic and yes the latter looks ok (city of) and I don't think it's a part of city name

They really want to put city after it just because it's small

No it's just e.g X

But only "welcome to X city" is also strange and if we write "Welcome to X" then it's not clear if X is a city or village

I think so

Welcome to Touristic X City

Hi all I have a question, suppose we want to write a welcome sign for a small city, is this sounds good?

@iheap

if costs are same then that max flow is also a min cost, but I don't know how to modify it to solve arbitrary costs in range O(1), if I have time I'll give a thought about it, but meanwhile maybe it's not bad if you try understand the hopcraft algorithm which is not very complicated and think about its modification to see if it works with min cost or not.

also to ping someone use @iheap, I saw this randomly.

if both costs and capacities are 1,sure modified version of dinic works. that modified dinic algorithm known as hopcroft algorithm, take a look if you want. One may improve that algorithm till now. en.m.wikipedia.org/wiki/Hopcroft–Karp_algorithm

yeah, I think I'm right in general but I'm not pretty sure about those flow algorithms. e.g in ford falkerson algorithm they are same. I think even in dinic's algorithm they are almost same while we are using real capacities.

OK I understand that they are not related but still note that weight 1 and weight in {1,2} are not simply convertible. e.g TSP is trivial if all weights are 1 but npc if weights are {1,2}, this is an strange example but it says it's not easy to say that if for capacity c we have solution then for capacity in {1,...,c} we have solution with same running time.p.s: anyhow ford falkerson is even older, I see that you didn't notice your conditions carefully.

@iheap, I think maybe it's better to read my answer then teach me. not all algorithms are relying on c. but if all capacities are c then there are free to use algorithms which I mentioned one of them in my answer (modified dinic algorithm), but if you want to use them e.g with capacities in {1,2} then you have to modify those algorithms and I don't know if modification is trivial. But why I asked this? 1. because of ur previous question that I commented and answer and that needs flow on unit capacity graph. 2. Your choice of algorithm as you wrote in your question it's a little bit strange.

O(1) or exactly 1? for example if all of them are 2 we can assume all are one and this is differ from O(1).

@FranMota, The trivial thing you considered as you said is trivial and it's possible to resolve it, but the thing that I mentioned is not clear if it's possible to resolve it by any deterministic algorithm (it seems it's not possible).

As I understand the question the algorithm just gets L,U and the subarray.

aabaabaa -> aaba/abaa

e.g first appearance? then we need to have some information about the sequences placement.

I'll give you aabaa, how do you determine the boundary?

Consider "aabaabaa", L=4

partitions*

then there can be two same subsequences such that they have different partition.

Yes

Also to provide a counter example, we may assume that the alphabet has size 2 ({a,b}), and we may assume that L=U. then partition is fixed, but there can be two different sequences that we cannot distinguish them.

Well I agree that you can argue this, but my main argument was just change a question a little bit and ask whether there exists such a deterministic algorithm (currently it's in some sense that one thinks there exists such an algorithm and should just find it, no other option is open).

I see, and somehow I can imagine if there were no $L$ or $U$ it was possible to solve it (sounds natural), but exactly because your U,L are just input, I think we need some relaxation, that means e.g we partition with size between L and U with probability $p$, ... I provided another randomized case in my first comment, but if you are looking for exact proof that is not possible to do this (or it's possible), maybe it's better to change a question a little bit and ask if there is such an algorithm (I think, it should not be so hard to provide a concrete counterexample).

I mean actually it's somehow not deterministic, e.g attach the subarray that you selected to the end of input, and suppose that the partition in the end is not same as the before, then what shall we guess? the first partition or the second partition?

If that given subarray is just a random input without any extra information, then it's not possible to provide such an algorithm, but is it a randomized algorithm fine? Then what is the definition of randomized algorithm for this problem? e.g a randomized algorithm that partitions and then finds the corresponding partition in a given subarray with probability $p$ and with shift distance $d$, where $p=f(U,L,n),d=g(U,L,n)$.

I'll be back later, and I'll read it, but if you found your answer it's not bad to share it in cstheory.

Sorry I'm late, but deadlines are close, I

yes

I'll read the original paper and will talk later.

I think still their argument is same and does not violate anything

About your edit to the question

This seems to be typo

I'm actually stressing on " Each cycle cover in G ". Not about gadget or weights or permanent.

I mean in the lecture note not in your question.

Yes, but then the last sentence is totally nonsense, what's a relation of a cycle cover between G and G'? What does this implies? Nothing.