Northwestern Kellogg logo

Take Action

Home | Faculty & Research Overview | Research

Research Details

Separation algorithms for tree partitioning inequalities, Electronic notes in discrete mathematics

Abstract

We consider the tree partition problem to partition the node set of a tree into subsets where the induced subgraph by each subset is connected and the total weight of nodes in a subset cannot exceed the capacity of the subset. We identify exponentially many valid inequalities for an integer programming formulation of the problem and develop a linear time separation algorithm for the valid inequalities.

Type

Article

Author(s)

Sunil Chopra, Sangho Shim, Kangbok Lee

Date Published

2016

Citations

Chopra, Sunil, Sangho Shim, and Kangbok Lee. 2016. Separation algorithms for tree partitioning inequalities. Electronic notes in discrete mathematics.: 109-116.

KELLOGG INSIGHT

Explore leading research and ideas

Find articles, podcast episodes, and videos that spark ideas in lifelong learners, and inspire those looking to advance in their careers.
learn more

COURSE CATALOG

Review Courses & Schedules

Access information about specific courses and their schedules by viewing the interactive course scheduler tool.
LEARN MORE

DEGREE PROGRAMS

Discover the path to your goals

Whether you choose our Full-Time, Part-Time or Executive MBA program, you’ll enjoy the same unparalleled education, exceptional faculty and distinctive culture.
learn more