the proceedings contain 36 papers. the special focus in this conference is on integerprogramming and combinatorialoptimization. the topics include: On scheduling coflows;integrality gaps of integer knapsack problems...
ISBN:
(纸本)9783319592497
the proceedings contain 36 papers. the special focus in this conference is on integerprogramming and combinatorialoptimization. the topics include: On scheduling coflows;integrality gaps of integer knapsack problems;approximation of corner polyhedra with families of intersection cuts;the structure of the infinite models in integerprogramming;mixed-integer linear representability, disjunctions, and variable elimination;cutting planes from wide split disjunctions;the heterogeneous capacitated k-center problem;local guarantees in graph cuts and clustering;verifying integerprogramming results;long term behavior of dynamic equilibria in fluid queuing networks;approximation algorithm for the maximum traveling salesman problem;minimizing multimodular functions and allocating capacity in bike-sharing systems;stochastic online scheduling on unrelated machines;beating half for random arrival;an improved deterministic rescaling for linear programming algorithms;a quasi-polynomial approximation for the restricted assignment problem;adaptive submodular ranking;minimum birkhoff-von Neumann decomposition;maximum matching in the online batch-arrival model;budget feasible mechanisms on matroids;deterministic discrepancy minimization via the multiplicative weight update method;mixed-integer convex representability;high degree sum of squares proofs, bienstock-zuckerberg hierarchy and cg cuts;enumeration of integer points in projections of unbounded polyhedra and equilibrium computation in atomic splittable singleton congestion games.
We obtain optimal lower and upper bounds for the (additive) integrality gaps of integer knapsack problems. In a randomised setting, we show that the integrality gap of a "typical" knapsack problem is drastic...
详细信息
ISBN:
(数字)9783319592503
ISBN:
(纸本)9783319592503;9783319592497
We obtain optimal lower and upper bounds for the (additive) integrality gaps of integer knapsack problems. In a randomised setting, we show that the integrality gap of a "typical" knapsack problem is drastically smaller than the integrality gap that occurs in a worst case scenario.
We extend the Barvinok-Woods algorithm for enumeration of integer points in projections of polytopes to unbounded polyhedra. To achieve this, we employ a new structural result on projections of semilinear subsets of t...
详细信息
ISBN:
(纸本)9783319592503;9783319592497
We extend the Barvinok-Woods algorithm for enumeration of integer points in projections of polytopes to unbounded polyhedra. To achieve this, we employ a new structural result on projections of semilinear subsets of the integer lattice.
the infinite models in integerprogramming can be described as the convex hull of some points or as the intersection of halfspaces derived from valid functions. In this paper we study the relationships between these t...
详细信息
ISBN:
(数字)9783319592503
ISBN:
(纸本)9783319592503;9783319592497
the infinite models in integerprogramming can be described as the convex hull of some points or as the intersection of halfspaces derived from valid functions. In this paper we study the relationships between these two descriptions. Our results have implications for finite dimensional corner polyhedra. One consequence is that nonnegative continuous functions suffice to describe finite dimensional corner polyhedra with rational data. We also discover new facts about corner polyhedra with non-rational data.
We consider the question of which nonconvex sets can be represented exactly as the feasible sets of mixed-integer convex optimization problems. We state the first complete characterization for the case when the number...
详细信息
ISBN:
(纸本)9783319592503;9783319592497
We consider the question of which nonconvex sets can be represented exactly as the feasible sets of mixed-integer convex optimization problems. We state the first complete characterization for the case when the number of possible integer assignments is finite. We develop a characterization for the more general case of unbounded integer variables together with a simple necessary condition for representability which we use to prove the first known negative results. Finally, we study representability of subsets of the natural numbers, developing insight towards a more complete understanding of what modeling power can be gained by using convex sets instead of polyhedral sets;the latter case has been completely characterized in the context of mixed-integer linear optimization.
We derive the first performance guarantees for a combinatorial online algorithm that schedules stochastic, nonpreemptive jobs on unrelated machines to minimize the expectation of the total weighted completion time. Pr...
详细信息
ISBN:
(数字)9783319592503
ISBN:
(纸本)9783319592503;9783319592497
We derive the first performance guarantees for a combinatorial online algorithm that schedules stochastic, nonpreemptive jobs on unrelated machines to minimize the expectation of the total weighted completion time. Prior work on unrelated machine scheduling with stochastic jobs was restricted to the offline case, and required sophisticated linear or convex programming relaxations for the assignment of jobs to machines. Our algorithm is purely combinatorial, and therefore it also works for the online setting. As to the techniques applied, this paper shows how the dual fitting technique can be put to work for stochastic and nonpreemptive scheduling problems.
the perceptron algorithm for linear programming, arising from machine learning, has been around since the 1950s. While not a polynomial-time algorithm, it is useful in practice due to its simplicity and robustness. In...
详细信息
ISBN:
(纸本)9783319592503;9783319592497
the perceptron algorithm for linear programming, arising from machine learning, has been around since the 1950s. While not a polynomial-time algorithm, it is useful in practice due to its simplicity and robustness. In 2004, Dunagan and Vempala showed that a randomized rescaling turns the perceptron method into a polynomial time algorithm, and later Pena and Soheili gave a deterministic rescaling. In this paper, we give a deterministic rescaling for the perceptron algorithm that improves upon the previous rescaling methods by making it possible to rescale much earlier. this results in a faster running time for the rescaled perceptron algorithm. We will also demonstrate that the same rescaling methods yield a polynomial time algorithm based on the multiplicative weights update method. this draws a connection to an area that has received a lot of recent attention in theoretical computer science.
Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from pro...
详细信息
ISBN:
(数字)9783319592503
ISBN:
(纸本)9783319592503;9783319592497
Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of state-of-the-art MIP solution algorithms, the ideal form of such a certificate is not entirely clear. this paper proposes such a certificate format designed with simplicity in mind, which is composed of a list of statements that can be sequentially verified using a limited number of inference rules. We present a supplementary verification tool for compressing and checking these certificates independently of how they were created. We report computational results on a selection of MIP instances from the literature. To this end, we have extended the exact rational version of the MIP solver SCIP to produce such certificates.
this book constitutes the refereed proceedings of the 19th international conference on integer programming and combinatorial optimization, ipco 2017, held in Waterloo, IN, Canada, in June 2017.
ISBN:
(数字)9783319592503
ISBN:
(纸本)9783319592497
this book constitutes the refereed proceedings of the 19th international conference on integer programming and combinatorial optimization, ipco 2017, held in Waterloo, IN, Canada, in June 2017.
暂无评论