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
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
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
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
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
COMPARATIVE STUDY OF MUTATION OPERATORS IN THE GENETIC ALGORITHMS FOR THE K-MEANS PROBLEM [PDF]
, 2021 The k-means problem and the algorithm of the same name are the most commonly used clustering model and algorithm. Being a local search optimization method, the k-means algorithm falls to a local minimum of the objective function (sum of squared errors ...
Kazakovtsev, Lev A., Li, Rui
core +1 more source
Total Dual Integrality in Some Facility Location Problems [PDF]
, 2012 published_or_final_versio
Chen, X, Chen, Z, Zang, W
core +1 more source
A branch-and-cut algorithm for the Time Window Assignment Vehicle Routing Problem [PDF]
, 2016 This paper presents a branch-and-cut algorithm for the Time Window Assignment Vehicle Routing Problem (TWAVRP), the problem of assigning time windows for delivery before demand volume becomes known.
Dalmeijer, K. (Kevin), Spliet, R. (Remy)
core +5 more sources
A polyhedral approach for the Equitable Coloring Problem [PDF]
, 2011 In this work we study the polytope associated with a 0,1-integer programming formulation for the Equitable Coloring Problem. We find several families of valid inequalities and derive sufficient conditions in order to be facet-defining inequalities.
Bahiense +15 more
core +2 more sources