On the planar integer two-flow problem

We consider the two-commodity flow problem and give a good characterization of the optimum flow if the augmented network (with both source-sink edges added) is planar. We show that max flow ≧ min cut −1, and describe the structure of those networks for which equality holds.     

Fully-Dynamic Min-Cut*

We show that we can maintain up to polylogarithmic edge connectivity for a fully-dynamic graph in worst-case time per edge insertion or deletion. Within logarithmic factors, this matches the best time bound for 1-edge connectivity. Previously, no o(n) bound was known for edge connectivity above 3, and even for 3-edge connectivity, the best update time was O(n^2/3), dating back to FOCS'92. Our algorithm maintains a concrete min-cut in terms of a pointer to a tree spanning one side of the cut plus ability to list the cut edges in O(log n) time per edge. By dealing with polylogarithmic edge connectivity, we immediately get a sampling based expected factor (1+o(1)) approximation to general edge connectivity in time per edge insertion or deletion. This algorithm also maintains a pointer to one side of a near-minimal cut, but if we want to list the cut edges in O(log n) time per edge, the update time increases to . * A preliminary version of this work was presented at the The 33rd ACM Symposium on Theory of Computing( STOC) [22], Crete, Greece, July 2001.     

A new class of superregular matrices and MDP convolutional codes

This paper deals with the problem of constructing superregular matrices that lead to MDP convolutional codes. These matrices are a type of lower block triangular Toeplitz matrices with the property that all the square submatrices that can possibly be nonsingular due to the lower block triangular structure are nonsingular. We present a new class of matrices that are superregular over a sufficiently large finite field F$\mathbb{F}$. Such construction works for any given choice of characteristic of the field F$\mathbb{F}$ and code parameters (n,k,δ)$(n,k,\delta )$ such that (n−k)|δ$(n-k)|\delta$. We also discuss the size of F$\mathbb{F}$ needed so that the proposed matrices are superregular.     

Multicommodity flows in cycle graphs

This paper considers the multicommodity flow problem and the integer multicommodity flow problem on cycle graphs. We present two linear time algorithms for solving each of the two problems.     

The mixed vertex packing problem

We study a generalization of the vertex packing problem having both binary and bounded continuous variables, called the mixed vertex packing problem (MVPP). The well-known vertex packing model arises as a subproblem or relaxation of many 0-1 integer problems, whereas the mixed vertex packing model arises as a natural counterpart of vertex packing in the context of mixed 0-1 integer programming. We describe strong valid inequalities for the convex hull of solutions to the MVPP and separation algorithms for these inequalities. We give a summary of computational results with a branch-and-cut algorithm for solving the MVPP and using it to solve general mixed-integer problems. Received: June 1998 / Accepted: February 2000?Published online September 20, 2000     

On The Span Of A Random Channel Assignment Problem

In the radio channel assignment problems considered here, we must assign a ‘channel’ from the set 1,2,... of positive integers to each of n transmitters, and we wish to minimise the span of channels used, subject to the assignment leading to an acceptable level of interference. A standard form of this problem is the ‘constraint matrix’ model. The simplest case of this model (the 0, 1 case) is essentially graph colouring. We consider here a random model for the next simplest case (with lengths 0, 1 or 2), and determine the asymptotic behaviour of the span of channels needed as n→∞. We find that there is a ‘phase change’ in this behaviour, depending on the probabilities for the different lengths.     

On lower bounds of exponential frames

Lower frame bounds for sequences of exponentials are obtained in a special version of Avdonin's theorem on 1/4 in the mean [1] and in a theorem of Duffin and Schaeffer [4].     

Positive semidefinite quadratic forms on unitary matrices

Let

     

Free multiflows in bidirected and skew-symmetric graphs

A graph (digraph) G=(V,E) with a set T⊆V of terminals is called inner Eulerian if each nonterminal node v has even degree (resp. the numbers of edges entering and leaving v are equal). Cherkassky and Lovász, independently, showed that the maximum number of pairwise edge-disjoint T-paths in an inner Eulerian graph G is equal to , where λ(s) is the minimum number of edges whose removal disconnects s and T-{s}. A similar relation for inner Eulerian digraphs was established by Lomonosov. Considering undirected and directed networks with “inner Eulerian” edge capacities, Ibaraki, Karzanov, and Nagamochi showed that the problem of finding a maximum integer multiflow (where partial flows connect arbitrary pairs of distinct terminals) is reduced to O(logT) maximum flow computations and to a number of flow decompositions.In this paper we extend the above max-min relation to inner Eulerian bidirected graphs and inner Eulerian skew-symmetric graphs and develop an algorithm of complexity for the corresponding capacitated cases. In particular, this improves the best known bound for digraphs. Our algorithm uses a fast procedure for decomposing a flow with O(1) sources and sinks in a digraph into the sum of one-source-one-sink flows.     

A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks

Given a directed edge-weighted graph and k source-sink pairs, the Minimum Directed Multicut Problem is to find an edge subset with minimal weight, that separates each source-sink pair. Determining the minimum multicut in directed or undirected graphs is NP-hard. The fractional version of the minimum multicut problem is dual to the maximum multicommodity flow problem. The integrality gap for an instance of this problem is the ratio of the minimum weight multicut to the minimum weight fractional multicut; trivially this gap is always at least 1 and it is easy to show that it is at most k. In the analogous problem for undirected graphs this upper bound was improved to O(log k).In this paper, for each k an explicit family of examples is presented each with k source-sink pairs for which the integrality gap can be made arbitrarily close to k. This shows that for directed graphs, the trivial upper bound of k can not be improved.* This work was supported in part by NSF grant CCR-9700239 and by DIMACS. This work was done while a postdoctoral fellow at DIMACS.     

On deviation measures in stochastic integer programming

We propose extensions of traditional expectation-based stochastic integer programs to mean-risk models. Risk is measured by expected deviations of suitable random variables from their means or from preselected targets. We derive structural properties of the resulting stochastic programs and present first algorithmic ideas to achieve problem decomposition.     

THE FFD ALGORITHM FOR THE BIN PACKING PROBLEM WITH KERNEL ITEMS

The FFD algorithm is one of the most famous algorithms for the classical bin packing problem. In this paper,some versions of the FFD algorithm are considered in several bin packing problems. Especially,two of them applied to the bin packing problem with kernel items are analyzed. Tight worst-case performance ratios are obtained.     

On coloring graphs with locally small chromatic number

In 1973, P. Erdös conjectured that for eachkε2, there exists a constantc _k so that ifG is a graph onn vertices andG has no odd cycle with length less thanc _k n ^1/k , then the chromatic number ofG is at mostk+1. Constructions due to Lovász and Schriver show thatc _k , if it exists, must be at least 1. In this paper we settle Erdös’ conjecture in the affirmative. We actually prove a stronger result which provides an upper bound on the chromatic number of a graph in which we have a bound on the chromatic number of subgraphs with small diameter.     

Imperfect and Nonideal Clutters: A Common Approach

We prove three theorems. First, Lovászs theorem about minimal imperfect clutters, including also Padbergs corollaries. Second, Lehmans result on minimal nonideal clutters. Third, a common generalization of these two. The endeavor of working out a common denominator for Lovászs and Lehmans theorems leads, besides the common generalization, to a better understanding and simple polyhedral proofs of both.* Visiting of the French Ministry of Research and Technology, laboratoire LEIBNIZ, Grenoble, November 1995—April 1996.     

On fiber products of elementary maps

The following characterization of fully closed maps is proved: a quotient map between regular spaces is fully closed if and only if it coincides with the fiber product of elementary maps between regular spaces.     

On a stochastic differential equation arising in a price impact model

We provide sufficient conditions for the existence and uniqueness of solutions to a stochastic differential equation which arises in the price impact model developed by Bank and Kramkov (2011)  and . These conditions are stated as smoothness and boundedness requirements on utility functions or Malliavin differentiability of payoffs and endowments.     

Geometric graph properties of the spatial preferred attachment model

The spatial preferred attachment (SPA) model is a model for networked information spaces such as domains of the World Wide Web, citation graphs, and on-line social networks. It uses a metric space to model the hidden attributes of the vertices. Thus, vertices are elements of a metric space, and link formation depends on the metric distance between vertices. We show, through theoretical analysis and simulation, that for graphs formed according to the SPA model it is possible to infer the metric distance between vertices from the link structure of the graph. Precisely, the estimate is based on the number of common neighbours of a pair of vertices, a measure known as co-citation. To be able to calculate this estimate, we derive a precise relation between the number of common neighbours and metric distance. We also analyse the distribution of edge lengths, where the length of an edge is the metric distance between its end points. We show that this distribution has three different regimes, and that the tail of this distribution follows a power law.     

Two-edge connected subgraphs with bounded rings: Polyhedral results and Branch-and-Cut

We consider the network design problem which consists in determining at minimum cost a 2-edge connected network such that the shortest cycle (a “ring”) to which each edge belongs, does not exceed a given length K. We identify a class of inequalities, called cycle inequalities, valid for the problem and show that these inequalities together with the so-called cut inequalities yield an integer programming formulation of the problem in the space of the natural design variables. We then study the polytope associated with that problem and describe further classes of valid inequalities. We give necessary and sufficient conditions for these inequalities to be facet defining. We study the separation problem associated with these inequalities. In particular, we show that the cycle inequalities can be separated in polynomial time when K≤4. We develop a Branch-and-Cut algorithm based on these results and present extensive computational results.     

A network flow-based method to solve performance cost and makespan open-shop scheduling problems with time-windows

This paper deals with several bicriteria open-shop scheduling problems where jobs are pre-emptable and their corresponding time-windows must be strictly respected. The criteria are a performance cost and the makespan. Network flow approaches are used in a lexmin procedure with a bounded makespan and the considered bicriteria problems are solved. Finally, the computational complexity of the algorithm and a numerical example are reported.     

Computing Minimal Forecast Horizons:An Integer Programming Approach

In this paper, we use integer programming (IP) to compute minimal forecast horizons for the classical dynamic lot-sizing problem (DLS). As a solution approach for computing forecast horizons, integer programming has been largely ignored by the research community. It is our belief that the modelling and structural advantages of the IP approach coupled with the recent significant developments in computational integer programming make for a strong case for its use in practice. We formulate some well-known sufficient conditions, and necessary and sufficient conditions (characterizations) for forecast horizons as feasibility/optimality questions in 0–1 mixed integer programs. An extensive computational study establishes the effectiveness of the proposed approach.