Titlebook: Combinatorial Optimization; 5th International Sy Jon Lee,Giovanni Rinaldi,A. Ridha Mahjoub Conference proceedings 2018 Springer Internation

ORE

Polytope Membership in High Dimension, ANN search. We present a novel data structure for boundary queries based on a Newton-like iterative intersection procedure. We implement our algorithms and compare with brute-force approaches to show that they scale very well as the dimension and number of facets grow larger.

猛击

注意力集中

R. Wäsch,J. Hasskarl,D. Schnerch,M. Lübbertand restrictions presents in mathematical formulations for this problems. The Mathematical formulation was analyzed and computational results shows that operational costs can be reduced and that it is possible to disable unused servers over the network.

持久

Isometric

Cluster Editing with Vertex Splitting,gical Network analysis. We initiate the study of this new problem and show that it is fixed-parameter tractable when parameterized by the total number of vertex splitting and edge editing operations. In particular we obtain a . vertex kernel for the problem.

背带

Maximum Concurrent Flow with Incomplete Data, which is based on a linear programming formulation involving both primal and dual variables, which optimally decides values for the missing data so that they are compatible with a set of scenarios of different incomplete data sets. We prove the correctness of our formulation and benchmark it on many different instances.

休战

A Multigraph Formulation for the Generalized Minimum Spanning Tree Problem, to existing formulations from the literature. The proposed model proves optimality for well-known GMSTP instances. In addition, this work opens new directions for future research to the development of sophisticated cutting plane and decomposition algorithms for related problems.

jabber

宽容

On Bounded Pitch Inequalities for the Min-Knapsack Polytope,We also investigate integrality gaps of linear relaxations for min-knapsack when these inequalities are added. Among other results, we show that, for any fixed ., the .-th CG closure of the natural linear relaxation has the unbounded integrality gap.

纯朴

Efficient Algorithms for Measuring the Funnel-Likeness of DAGs,r main focus is the algorithmic complexity of finding out how funnel-like a given DAG is. To this end, we study the NP-hard problem of computing the arc-deletion distance to a funnel of a given DAG. We develop efficient exact and approximation algorithms for the problem and test them on synthetic random graphs and real-world graphs.