Main Page

From himtp
Jump to: navigation, search

HIM Trimester Program on Combinatorial Optimization

Every participant of the program is invited to edit these pages. Please create a new subpage for every new problem.

Collection of Open Problems

Discrete Time-Cost Tradeoff Problem (Jens Vygen)

Is a given graph a k-trail? (András Sebő)

Uniform covers by tours (András Sebő)

High connectivity keeping spanning trees (Matthias Kriesell)

Unbalanced Point-to-Point Connectivity Problem (Chandra Chekuri)

Bipartition-constrained edge-connectivity augmentation avoiding a prescribed perfect matching (Jørgen Bang-Jensen)

Long Cycles in Euclidean 2-Factors (William Cook)

Popular matchings in non-bipartite graphs (Ágnes Cseh)

Open problems on element-connectivity (Chandra Chekuri)

Approximability of the Tree Augmentation Problem (Zeev Nutov)

Sparsest Cut by Random Contraction (Jens Vygen)

Minimum Intersection of a Spanning Tree and a Perfect Matching (Alantha Newman)

The 4/3-Conjecture for Euclidean TSP (Stefan Hougardy)

Poly-time algorithm for L-convex fn minimization (Akiyoshi Shioura)

Representation of M^\natural-convex set function (Kazuo Murota)

Deterministic algorithm for maximizing a monotone submodular function over a matroid (Yuval Filmus)

Partitioning a matroid into independent sets (Kristóf Bérczi)

Coverage Maximization with Uniform Query Sizes in Stochastic Settings (Morteza Zadimoghaddam)

Status of Minimum Bisection on Planar Graphs (Marek Karpinski)

Volume of the BQP (Jon Lee)


Getting started

You don't have an account? Please contact Christian Wegner.

If you want to create a new page for an open problem and are not familiar with wikis, you can email your text to Christian Wegner.

Consult the User's Guide for information on using the wiki software.