Skip to main content
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
4 votes

Total flow using minimum number of edges on a bipartite network

Your problem is NP-hard. Consider a partition problem instance with input $a_1,\ldots,a_n$. We create a complete bipartite graph with $2$ source vertices each with capacity $\frac{1}{2} \sum_{i=1}^n ...
Chao Xu's user avatar
  • 4,479
3 votes

A stronger Flow Decomposition Theorem?

The statement of Ahuja, Magnanti, and Orlin applies to general flows, not only $(s,t)$-flows. During decomposition, when removing a path flow, either one of the two endpoints become balanced or one ...
Kristoffer Arnsfelt Hansen's user avatar
1 vote

Algorithm for Shortest Path in a DAG with Multiple Transportation Modes and Associated Setup Costs

This problem appears to be an NP problem, and here's a proof for it. Considering the presence of fixed setup costs in the problem, it brings to mind the uncapacitated facility location problem. ...
Changxin Cao's user avatar
1 vote

Bipartite graph projections, with threshold

My two cents: The worst case of building $G_\top$ is in $\Omega(n^2)$ time and space: assume $\bot$ contains a single node linked to all nodes in $\top$. Maybe you are not looking for a worst case ...
maxdan94's user avatar
  • 563
1 vote

Does fixed hyperparameters perform well regardless the number of training examples?

No. You're asking about model selection. Larger sample sizes will allow you to choose more complex models. Read up on the keywords overfit/underfit, model selection, Structural Risk Minimization, and ...
Aryeh's user avatar
  • 10.6k

Only top scored, non community-wiki answers of a minimum length are eligible