the proceedings contain 34 papers. the topics discussed include: solving LP relaxations of large-scale precedence constrained problems;computing minimum multiway cuts in hypergraphs from hypertree packings;eigenvalue ...
ISBN:
(纸本)3642130356
the proceedings contain 34 papers. the topics discussed include: solving LP relaxations of large-scale precedence constrained problems;computing minimum multiway cuts in hypergraphs from hypertree packings;eigenvalue techniques for convex objective, nonconvex optimization problems;restricted b-matchings in degree-bounded graphs;zero-coefficient cuts;prize-collecting steiner network problems;on lifting integer variables in minimal inequalities;efficient edge splitting-off algorithms maintaining all-pairs edge-connectivities;on generalizations of network design problems with degree bounds;a polyhedral study of the mixed integer cut;symmetry matters for the sizes of extended formulations;a 3-approximation for facility location with uniform capacities;and approximability of 3- and 4-hop bounded disjoint paths problems.
the proceedings contain 32 papers. the special focus in this conference is on integerprogramming and combinatorialoptimization. the topics include: Strongly polynomial algorithms for the unsplittable flow problem;ed...
ISBN:
(纸本)3540422250
the proceedings contain 32 papers. the special focus in this conference is on integerprogramming and combinatorialoptimization. the topics include: Strongly polynomial algorithms for the unsplittable flow problem;edge covers of set pairs and the iterative rounding method;the asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates;fast 2-variable integerprogramming;a matroid generalization of the stable matching polytope;combined connectivity augmentation and orientation problems;an extension of a theorem of henneberg and Laman;on the integrality gap of a natural formulation of the single-sink buy-at-bulk network design problem;integral polyhedra related to even cycle and even cut matroids;a unified framework for obtaining improved approximation algorithms for maximum graph bisection problems;bounds for deterministic periodic routing sequences;independence free graphs and vertex connectivity augmentation;pruning by isomorphism in branch-and-cut;facets, algorithms, and polyhedral characterizations for a multi-item production planning model with setup times;on relaxations for the linear ordering problem;performance guarantees of local search for multiprocessor scheduling;two NP-hardness results for preemptive minsum scheduling of unrelated parallel machines and approximation algorithms for the minimum bends traveling salesman problem.
the proceedings contain 33 papers. the special focus in this conference is on integerprogramming and combinatorialoptimization. the topics include: A General Framework for Handling Commitment in Online throughput Ma...
ISBN:
(纸本)9783030179526
the proceedings contain 33 papers. the special focus in this conference is on integerprogramming and combinatorialoptimization. the topics include: A General Framework for Handling Commitment in Online throughput Maximization;lower Bounds and a New Exact Approach for the Bilevel Knapsack with Interdiction Constraints;on Friedmann’s Subexponential Lower Bound for Zadeh’s Pivot Rule;tight Approximation Ratio for Minimum Maximal Matching;integerprogramming and Incidence Treedepth;A Bundle Approach for SDPs with Exact Subgraph Constraints;dynamic Flows with Adaptive Route Choice;the Markovian Price of Information;on Perturbation Spaces of Minimal Valid Functions: Inverse Semigroup theory and Equivariant Decomposition theorem;min-Max Correlation Clustering via MultiCut;on Compact Representations of Voronoi Cells of Lattices;an Efficient Characterization of Submodular Spanning Tree Games;the Asymmetric Traveling Salesman Path LP Has Constant Integrality Ratio;approximate Multi-matroid Intersection via Iterative Refinement;an Exact Algorithm for Robust Influence Maximization;a New Contraction Technique with Applications to Congruency-Constrained Cuts;sparsity of integer Solutions in the Average Case;a Generic Exact Solver for Vehicle Routing and Related Problems;earliest Arrival Transshipments in Networks with Multiple Sinks;Intersection Cuts for Factorable MINLP;strong Mixed-integerprogramming Formulations for Trained Neural Networks;linear programming Using Limited-Precision Oracles;computing the Nucleolus of Weighted Cooperative Matching Games in Polynomial Time;breaking Symmetries to Rescue Sum of Squares: the Case of Makespan Scheduling;random Projections for Quadratic Programs over a Euclidean Ball;extended Formulations from Communication Protocols in Output-Efficient Time;Sub-Symmetry-Breaking Inequalities for ILP with Structured Symmetry;intersection Cuts for Polynomial optimization.
the proceedings contain 33 papers. the topics discussed include: on the structure of reduced kernel lattice bases;all-or-nothing generalized assignment with application to scheduling advertising campaigns;intersection...
ISBN:
(纸本)9783642366932
the proceedings contain 33 papers. the topics discussed include: on the structure of reduced kernel lattice bases;all-or-nothing generalized assignment with application to scheduling advertising campaigns;intersection cuts for mixed integer conic quadratic sets;content placement via the exponential potential function method;a complexity and approximability study of the bilevel knapsack problem;matroid and knapsack center problems;cut-generating functions;on some generalizations of the split closure;packing interdiction and partial covering problems;on valid inequalities for quadratic programming with continuous variables and binary indicators;single commodity-flow algorithms for lifts of graphic and co-graphic matroids;a stochastic probing problem with applications;thrifty algorithms for multistage robust optimization;and two dimensional optimal mechanism design for a sequencing problem.
the proceedings contain 32 papers. the special focus in this conference is on Session 1 and Session 2. the topics include: Robust branch-and-cut-and-price for the capacitated vehicle routing problem;metric inequalitie...
ISBN:
(纸本)3540221131
the proceedings contain 32 papers. the special focus in this conference is on Session 1 and Session 2. the topics include: Robust branch-and-cut-and-price for the capacitated vehicle routing problem;metric inequalities and the network loading problem;valid inequalities based on simple mixed-integer sets;the price of anarchy when costs are non-separable and asymmetric;computational complexity, fairness, and the price of anarchy of the maximum latency problem;polynomial time algorithm for determining optimal strategies in cyclic games;a robust optimization approach to supply chain management;approximation algorithms for stochastic optimization problems;scheduling an industrial production facility;three min-max theorems concerning cyclic orders of strong digraphs;a TDI description of restricted 2-matching polytopes;enumerating minimal dicuts and strongly connected subgraphs and related geometric problems;semi-continuous cuts for mixed-integerprogramming;combinatorial benders’ cuts;a faster exact separation algorithm for blossom inequalities;LP-based approximation algorithms for capacitated facility location;a multiexchange local search algorithm for the capacitated facility location problem;separable concave optimization approximately equals piecewise linear optimization;three kinds of integerprogramming algorithms based on barvinok’s rational functions;the path-packing structure of graphs;more on a binary-encoded coloring formulation;single machine scheduling with precedence constraints;the constrained minimum weighted sum of job completion times problem;near-optimum global routing with coupling, delay bounds, and power consumption;a flow-based method for improving the expansion or conductance of graph cuts;all rational polytopes are transportation polytopes and all polytopal integer sets are contingency tables;a capacity scaling algorithm for M-convex submodular flow and integer concave cocirculations and honeycombs.
the proceedings contain 33 papers. the special focus in this conference is on integerprogramming and combinatorialoptimization. the topics include: An Update-and-Stabilize Framework for the Minimum-Norm-Po...
ISBN:
(纸本)9783031327254
the proceedings contain 33 papers. the special focus in this conference is on integerprogramming and combinatorialoptimization. the topics include: An Update-and-Stabilize Framework for the Minimum-Norm-Point Problem;stabilization of Capacitated Matching Games;designing optimization Problems with Diverse Solutions;ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation;on the Correlation Gap of Matroids;A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP;the Polyhedral Geometry of Truthful Auctions;competitive Kill-and-Restart and Preemptive Strategies for Non-clairvoyant Scheduling;A Deterministic Better-than-3/2 Approximation Algorithm for Metric TSP;Efficient Separation of RLT Cuts for Implicit and Explicit Bilinear Products;monoidal Strengthening of Simple V -Polyhedral Disjunctive Cuts;optimal General Factor Problem and Jump System Intersection;decomposition of Probability Marginals for Security Games in Abstract Networks;set Selection Under Explorable Stochastic Uncertainty via Covering Techniques;towards a Characterization of Maximal Quadratic-Free Sets;compressing Branch-and-Bound Trees;exploiting the Polyhedral Geometry of Stochastic Linear Bilevel programming;towards an Optimal Contention Resolution Scheme for Matchings;Advances on Strictly Δ -Modular IPs;cut-Sufficient Directed 2-Commodity Multiflow Topologies;a Nearly Optimal Randomized Algorithm for Explorable Heap Selection;constant-Competitiveness for Random Assignment Matroid Secretary Without Knowing the Matroid;a Fast combinatorial Algorithm for the Bilevel Knapsack Problem with Interdiction Constraints;multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching;a Linear Time Algorithm for Linearizing Quadratic and Higher-Order Shortest Path Problems;sparse Approximation over the Cube;recycling Inequalities for Robust combinatorialoptimization with Budget Uncertainty;inapproximability of Shortest Paths on Perfect Matching Polyt
the proceedings contain 33 papers. the special focus in this conference is on integerprogramming and combinatorialoptimization. the topics include: A faster scaling algorithm for minimizing submodular functions;a co...
ISBN:
(纸本)9783540478676
the proceedings contain 33 papers. the special focus in this conference is on integerprogramming and combinatorialoptimization. the topics include: A faster scaling algorithm for minimizing submodular functions;a coordinatewise domain scaling algorithm for m-convex function minimization;the quickest multicommodity flow problem;a new min-cut max-flow ratio for multicommodity flows;improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems;finding the exact integrality gap for small traveling salesman problems;polynomial-time separation of simple comb inequalities;a new approach to cactus construction applied to TSP support graphs;split closure and intersection cuts;an exponential lower bound on the length of some classes of branch-and-cut proofs;basic theory and algorithms;on a lemma of scarf;integerprogramming and arrovian social welfare functions;approximation algorithms combining facility location and network design;the minimum latency problem is NP-hard for weighted trees;an improved approximation algorithm for the metric uncapacitated facility location problem;a polyhedral approach to surface reconstruction from planar contours;the semidefinite relaxation of the k-partition polytope is strong;a PTAS for minimizing total completion time of bounded batch scheduling;an approximation scheme for the two-stage, two-dimensional bin packing problem;polynomial-time approximation schemes;hard equality constrained integer knapsacks;the distribution of values in the quadratic assignment problem;a new subadditive approach to integerprogramming;improved approximation algorithms for resource allocation;approximating the advertisement placement problem and algorithms for minimizing response time in broadcast scheduling.
the proceedings contain 33 papers. the topics discussed include: a faster scaling algorithm for minimizing submodular functions;a generalization of Edmonds' matching and matroid intersection algorithms;a coordinat...
the proceedings contain 33 papers. the topics discussed include: a faster scaling algorithm for minimizing submodular functions;a generalization of Edmonds' matching and matroid intersection algorithms;a coordinate-wise domain scaling algorithm for m-convex function minimization;a new min-cut max-flow ratio for multicommodity flows;improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems;finding the exact integrality gap for small traveling salesman problems;polynomial-time separation of simple comb inequalities;a new approach to cactus construction applied to tsp support graphs;an exponential lower bound on the length of some classes of branch-and-cut proofs;lifted inequalities for 0-1 mixed integerprogramming: basic theory and algorithms;a short proof of Seymour's characterization of the matroids withthe max-flow min-cut property;and integrated logistics: approximation algorithms combining facility location and network design.
the proceedings contain 32 papers. the special focus in this conference is on Edge Connectivity and Algorithms. the topics include: A characterization of weakly bipartite graphs;bipartite designs;characterizing nonint...
ISBN:
(纸本)354064590X
the proceedings contain 32 papers. the special focus in this conference is on Edge Connectivity and Algorithms. the topics include: A characterization of weakly bipartite graphs;bipartite designs;characterizing noninteger polyhedra with 0-1 constraints;a theorem of truemper;the generalized stable set problem for claw-free bidirected graphs;on a min-max theorem of cacti;edge-splitting and edge-connectivity augmentation in planar graphs;a new bound for the 2-edge connected subgraph problem;an approximation algorithm for 2-edge connected spanning subgraphs;multicuts in unweighted graphs with bounded degree and bounded tree-width;approximating disjoint-path problems using greedy algorithms and packing integer programs;approximation algorithms for the mixed postman problem;improved approximation algorithms for uncapacitated facility location;the maximum traveling salesman problem under polyhedral norms;polyhedral combinatorics of benzenoid problems;consecutive ones and a betweenness problem in computational biology;solving a linear diophantine equation with lower and upper bounds on the variables;the intersection of knapsack polyhedra and extensions;new classes of lower bounds for bin packing problems;solving integer and disjunctive programs by lift and project;a class of hard small 0-1 programs;building chain and cactus representations of all minimum cuts from hao-orlin in the same asymptotic run time;simple generalized maximum flow algorithms;the pseudoflow algorithm and the pseudoflow-based simplex for the maximum flow problem;an implementation of a combinatorial approximation algorithm for minimum-cost multicommodity flow and non-approximability results for scheduling problems with minsum criteria.
暂无评论