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 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 linear programming duality is well understood and the reduced cost of a column is frequently used in various algorithms. On the other hand, for integer programs it is not clear how to define a dual function even t...
详细信息
Branch-and-cut methods are among the more successful techniques for solving integerprogramming problems. they can also be used to prove that all solutions of an integer program satisfy a given linear inequality. We e...
详细信息
the independent path-matching problem is a common generalization of the matching problem and the matroid intersection problem. Cunningham and Geelen proved that this problem is solvable in polynomial time via the elli...
详细信息
We present a polynomial time domain scaling algorithm for the minimization of an M-convex function. M-convex functions are nonlinear discrete functions with (poly)matroid structures, which are being recognized to play...
详细信息
In the seventies, Balas introduced intersection cuts for a Mixed integer Linear Program (MILP), and showed that these cuts can be obtained by a closed form formula from a basis of the standard linear programming relax...
详细信息
We formulate the problem of deciding which preference domains admit a non-dictatorial Arrovian Social Welfare Function as one of verifying the feasibility of an integer linear program. Many of the known results about ...
详细信息
We consider the following integer feasibility problem: "Given positive integer numbers a0, a1,…, an, with gcd(a1,…, an) = 1 and a = (a1,…, an), does there exist a nonnegative integer vector x satisfying ax = a...
详细信息
Seymour proved that the set of odd circuits of a signed binary matroid (M,Σ) has the Max-Flow Min-Cut property if and only if it does not contain a minor isomorphic to (M(K4),E(K4)). We give a shorter proof of this r...
详细信息
暂无评论