Operations Research Asked by fathese on January 8, 2021

I have a min-cut formulation and a bi-partitioning problem.

The two problems focus on finding the minimal cut value separating the two partitions?

So what are really the differences between the problems? what are mainly the considered objectives and constraints?

Roughly speaking, in minimum cut problems, the goal is generally to find a minimum cut (possibly weighted) between two *fixed* sets of vertices, called the sources and the sinks. Given one source and one sink in input, the problem can be solved in polynomial time, a famous theorem in combinatorial optimization.

On the other hand, in graph partitioning problems, the goal is generally to find a partition of the vertices into subsets with a maximum size while minimizing the cut (possibly weighted) between these subsets. For example, the bisection problem consists of finding a partition of the vertices into two subsets of equal size, while the minimum cut between the two subsets is minimum. This problem is known to be NP-hard.

But in the end, this is a matter of precise definition of the problem to be solved. Some cut problems are polynomial; some others are NP-hard (for example, the so-called maximum cut problem). The same holds for graph partitioning problems.

Answered by LocalSolver on January 8, 2021

1 Asked on January 5, 2022

1 Asked on January 1, 2022 by ehsank

1 Asked on January 1, 2022

big m chance constraints mixed integer programming stochastic programming

1 Asked on December 20, 2021 by cesar-canassa

1 Asked on December 18, 2021 by neverletgo

2 Asked on December 9, 2021 by farouk-hammami

combinatorial optimization cplex linearization optimization quadratic programming

3 Asked on November 24, 2021

1 Asked on November 17, 2021

15 Asked on August 19, 2021

3 Asked on August 19, 2021

4 Asked on August 19, 2021 by marco-lbbecke

2 Asked on August 19, 2021 by matheus-digenes-andrade

2 Asked on August 19, 2021

2 Asked on August 19, 2021 by user3831

3 Asked on August 19, 2021 by josh-allen

2 Asked on August 19, 2021 by ehsan

1 Asked on August 19, 2021

Get help from others!

Recent Questions

Recent Answers

- haakon.io on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP