A linear time algorithm for a variant of the max cut problem in series parallel graphs [PDF]
, 2017 Given a graph $G=(V, E)$, a connected sides cut $(U, V\backslash U)$ or $\delta (U)$ is the set of edges of E linking all vertices of U to all vertices of $V\backslash U$ such that the induced subgraphs $G[U]$ and $G[V\backslash U]$ are connected.
Chaourar, Brahim
core +3 more sources
A fast branch-and-bound algorithm for non-convex quadratic integer optimization subject to linear constraints using ellipsoidal relaxations [PDF]
, 2015 We propose two exact approaches for non-convex quadratic integer minimization subject to linear constraints where lower bounds are computed by considering ellipsoidal relaxations of the feasible set.
Buchheim, Christoph +2 more
core +1 more source
Cones of closed alternating walks and trails [PDF]
, 2007 Consider a graph whose edges have been colored red and blue. Assign a nonnegative real weight to every edge so that at every vertex, the sum of the weights of the incident red edges equals the sum of the weights of the incident blue edges. The set of all
Bhattacharya, Amitava +2 more
core +2 more sources
Certificates of infeasibility via nonsmooth optimization [PDF]
, 2015 An important aspect in the solution process of constraint satisfaction problems is to identify exclusion boxes which are boxes that do not contain feasible points.
Fendl, Hannes +2 more
core +2 more sources
GENETIC ALGORITHM WITH GREEDY CROSSOVER AND ELITISM FOR CAPACITY PLANNING [PDF]
, 2022 We propose a modification to the genetic algorithm with greedy agglomerative crossover operator for the problem of scheduling product types at the facilities of the metal or plastic production factory where the goal is to minimize the number of ...
Kazakovtsev, Lev +3 more
core +1 more source
Polygons as Sections of Higher-Dimensional Polytopes [PDF]
, 2015 We show that every heptagon is a section of a 3-polytope with 6 vertices. This implies that every n-gon with n≥7 can be obtained as a section of a (2+⌊n7⌋)-dimensional polytope with at most ⌈6n7⌉ vertices; and provides a geometric proof of the fact that ...
Padrol, Arnau, Pfeifle, Julian
core +3 more sources
Polytopes related to interval vectors and incidence matrices [PDF]
, 2011 In this short note we investigate polytopes associated with families of interval vectors, i.e., (0,1)-vectors with consecutive ones. Using a linear transformation we show a connection to “extended” incidence matrices of acyclic directed graphs and the ...
Dahl, Geir
core +1 more source
Symmetric, Hankel-symmetric, and Centrosymmetric Doubly Stochastic Matrices [PDF]
, 2017 We investigate convex polytopes of doubly stochastic matrices having special structures: symmetric, Hankel symmetric, centrosymmetric, and both symmetric and Hankel symmetric.
Brualdi, Richard R., Cao, Lei
core +3 more sources
Integer Polynomial Optimization in Fixed Dimension
, 2004 We classify, according to their computational complexity, integer optimization problems whose constraints and objective functions are polynomials with integer coefficients and the number of variables is fixed.
Barvinok A. I. +9 more
core +4 more sources
Total Dual Integrality in Some Facility Location Problems [PDF]
, 2012 published_or_final_versio
Chen, X, Chen, Z, Zang, W
core +1 more source