Approximation Algorithm for MAX DICUT with Given Sizes of Parts

Given a directed graph G and an edge weight function w : A(G)→ R^ , the maximum directed cut problem (MAX DICUT) is that of finding a directed cut δ(S) with maximum total weight. We consider a version of MAX DICUT -- MAX DICUT with given sizes of parts or MAX DICUT WITH GSP -- whose instance is that of MAX DICUT plus a positive integer k, and it is required to find a directed cut δ(S) having maximum weight over all cuts δ(S) with |S| -- k. We present an approximation algorithm for this problem which is based on semidefinite programming (SDP) relaxation. The algorithm achieves the presently best performance guarantee for a range of k.     

D.C. Versus Copositive Bounds for Standard QP

The standard quadratic program (QPS) is min_xεΔx^TQx, where is the simplex Δ = {x ⩽ 0 ∣ ∑_i=1ⁿ x_i = 1}. QPS can be used to formulate combinatorial problems such as the maximum stable set problem, and also arises in global optimization algorithms for general quadratic programming when the search space is partitioned using simplices. One class of ‘d.c.’ (for ‘difference between convex’) bounds for QPS is based on writing Q=S−T, where S and T are both positive semidefinite, and bounding x^T Sx (convex on Δ) and −x^Tx (concave on Δ) separately. We show that the maximum possible such bound can be obtained by solving a semidefinite programming (SDP) problem. The dual of this SDP problem corresponds to adding a simple constraint to the well-known Shor relaxation of QPS. We show that the max d.c. bound is dominated by another known bound based on a copositive relaxation of QPS, also obtainable via SDP at comparable computational expense. We also discuss extensions of the d.c. bound to more general quadratic programming problems. For the application of QPS to bounding the stability number of a graph, we use a novel formulation of the Lovasz ϑ number to compare ϑ, Schrijver’s ϑ′, and the max d.c. bound.     

Worst-case analyses, linear programming and the bin-packing problem

In this paper we consider the familiar bin-packing problem and its associated set-partitioning formulation. We show that the optimal solution to the bin-packing problem can be no larger than 4/3 ⌈Z _LP⌉, whereZ _LP is the optimal solution value of the linear programming relaxation of the set-partitioning formulation. An example is provided to show that the bound is tight. A by-product of our analysis is a new worst-case bound on the performance of the well studied First Fit Decreasing and Best Fit Decreasing heuristics. This research was supported in part by ONR Contracts N00014-90-J-1649 and N00014-95-1-0232, and NSF Contracts DDM-8922712 and DDM-9322828.     

The Fefferman-Stein-Type Inequality for the Kakeya Maximal Operator II

Let K _δ, 0 < δ≪1, be the Kakeya maximal operator defined as the supremum of averages over tubes of the eccentricity δ. The (so-called) Fefferman-Stein-type inequality: is shown, where C _d and α _d are constants depending only on the dimension d and w is a weight. The result contains the exponent (d−2)/2d which is smaller than the exponent (d−2)(d−1)/d(2d−3) obtained in [7]. Received October 8, 2001, Accepted February 28, 2002     

On the power and limitations of affine policies in two-stage adaptive optimization

We consider a two-stage adaptive linear optimization problem under right hand side uncertainty with a min–max objective and give a sharp characterization of the power and limitations of affine policies (where the second stage solution is an affine function of the right hand side uncertainty). In particular, we show that the worst-case cost of an optimal affine policy can be times the worst-case cost of an optimal fully-adaptable solution for any δ > 0, where m is the number of linear constraints. We also show that the worst-case cost of the best affine policy is times the optimal cost when the first-stage constraint matrix has non-negative coefficients. Moreover, if there are only k ≤ m uncertain parameters, we generalize the performance bound for affine policies to , which is particularly useful if only a few parameters are uncertain. We also provide an -approximation algorithm for the general case without any restriction on the constraint matrix but the solution is not an affine function of the uncertain parameters. We also give a tight characterization of the conditions under which an affine policy is optimal for the above model. In particular, we show that if the uncertainty set, is a simplex, then an affine policy is optimal. However, an affine policy is suboptimal even if is a convex combination of only (m + 3) extreme points (only two more extreme points than a simplex) and the worst-case cost of an optimal affine policy can be a factor (2 − δ) worse than the worst-case cost of an optimal fully-adaptable solution for any δ > 0.     

On two Hamilton cycle problems in random graphs

We study two problems related to the existence of Hamilton cycles in random graphs. The first question relates to the number of edge disjoint Hamilton cycles that the random graph G _n,p contains. δ(G)/2 is an upper bound and we show that if p ≤ (1 + o(1)) ln n/n then this upper bound is tight whp. The second question relates to how many edges can be adversarially removed from G _n,p without destroying Hamiltonicity. We show that if p ≥ K ln n/n then there exists a constant α > 0 such that whp G − H is Hamiltonian for all choices of H as an n-vertex graph with maximum degree Δ(H) ≤ αK ln n. Research supported in part by NSF grant CCR-0200945. Research supported in part by USA-Israel BSF Grant 2002-133 and by grant 526/05 from the Israel Science Foundation.     

Extensions to online delay management on a single train line: new bounds for delay minimization and profit maximization

We present extensions to the Online Delay Management Problem on a Single Train Line. While a train travels along the line, it learns at each station how many of the passengers wanting to board the train have a delay of δ. If the train does not wait for them, they get delayed even more since they have to wait for the next train. Otherwise, the train waits and those passengers who were on time are delayed by δ. The problem consists in deciding when to wait in order to minimize the total delay of all passengers on the train line. We provide an improved lower bound on the competitive ratio of any deterministic online algorithm solving the problem using game tree evaluation. For the extension of the original model to two possible passenger delays δ ₁ and δ ₂, we present a 3-competitive deterministic online algorithm. Moreover, we study an objective function modeling the refund system of the German national railway company, which pays passengers with a delay of at least Δ a part of their ticket price back. In this setting, the aim is to maximize the profit. We show that there cannot be a deterministic competitive online algorithm for this problem and present a 2-competitive randomized algorithm.     

Not collapsing cardinals ≤<Emphasis Type="Italic">κ</Emphasis> in (<<Emphasis Type="Italic">κ</Emphasis>)-support iterations

We deal with the problem of preserving various versions of completeness in (<κ)-support iterations of forcing notions, generalizing the case “S-complete proper is preserved by CS iterations for a stationary costationaryS⊆ω ₁”. We give applications to Uniformization and the Whitehead problem. In particular, for a strongly inaccessible cardinalκ and a stationary setS⊆κ with fat complement we can have uniformization for every (A _δ :δ ∈S′),A _δ ⊆δ = supA _δ , cf (δ) = otp(A _δ ) and a stationary non-reflecting setS′⊆S (see B.8.2). Research supported by The German-Israeli Foundation for Scientific Research & Development Grant No. G-294.081.06/93 and by The National Science Foundation Grant No. 144-EF67. Publication No. 587.     

Dimension spectra of self-affine sets

The dimension spectrumH(δ) is a function characterizing the distribution of dimension of sections. Using the multifractal formula for sofic measures, we show that the dimension spectra of irreducible self-affine sets (McMullen’s Carpet) coincide with the modified Legendre transform of the free energy Ψ_d(β). This variational relation leads to the formula of Hausdorff dimension of self-affine sets, max(δ +H(δ)) = Ψ_d(η), whereη is the logarithmic ratio of the contraction rates of the affine maps.     

MAX k‐CUT and approximating the chromatic number of random graphs

We consider the MAX k‐CUT problem on random graphs G_n,p. First, we bound the probable weight of a MAX k‐CUT using probabilistic counting arguments and by analyzing a simple greedy heuristic. Then, we give an algorithm that approximates MAX k‐CUT in expected polynomial time, with approximation ratio 1 + O((np)^‐1/2). Our main technical tool is a new bound on the probable value of Frieze and Jerrum's semidefinite programming (SDP)‐relaxation of MAX k‐CUT on random graphs. To obtain this bound, we show that the value of the SDP is tightly concentrated. As a further application of our bound on the probable value of the SDP, we obtain an algorithm for approximating the chromatic number of G_n,p, 1/n ≤ p ≤ 0.99, within a factor of O((np)^1/2) in polynomial expected time, thereby answering a question of Krivelevich and Vu. We give similar algorithms for random regular graphs. The techniques for studying the SDP apply to a variety of SDP relaxations of further NP‐hard problems on random structures and may therefore be of independent interest. For instance, to bound the SDP we estimate the eigenvalues of random graphs with given degree sequences. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

ON NUMBER OF LEAVES ANDBANDWIDTH OF TREES

1.IntroductionFOragraphG=(V,E)oforderp,aonetoonemappingfromVinto{l,2,',p}iscalledanumberingofG.Definition1.1.SupposefisanumberingofG.LetBj(G)=(u57teif(u)--f(v)l.ThebandwidthofG,denotedbyB(G),isdefinedbyB(G)=min{Bf(G)IfisanumberingofG}.Thebandwidthproblemofgraphshasbecomeveryimportantsincethemid-sixties(see[21or[4]).Itisverydifficulttodeterminethebandwidthofagraph.GareyetallllshowedthatthebandwidthproblemisNP-completeevenifitisrestrictedtotreeswithmaximumdegree3.Soitisinterestingtoe…     

Properties of Distortion Risk Measures

The current literature does not reach a consensus on which risk measures should be used in practice. Our objective is to give at least a partial solution to this problem. We study properties that a risk measure must satisfy to avoid inadequate portfolio selections. The properties that we propose for risk measures can help avoid the problems observed with popular measures, like Value at Risk (VaR _α ) or Conditional VaR _α (CVaR _α ). This leads to the definition of two new families: complete and adapted risk measures. Our focus is on risk measures generated by distortion functions. Two new properties are put forward for these: completeness, ensuring that the distortion risk measure uses all the information of the loss distribution, and adaptability, forcing the measure to use this information adequately. This research was partially funded by ^1,3 Welzia Management, SGIIC SA, RD Sistemas SA, Comunidad Autónoma de Madrid Grant s-0505/tic/000230, and MEyC Grant BEC2000-1388-C04-03 and by ² the Natural Sciences and Engineering Research Council of Canada (NSERC) Grant 36860-06.     

Asymptotic bound on binary self-orthogonal codes

We present two constructions for binary self-orthogonal codes. It turns out that our constructions yield a constructive bound on binary self-orthogonal codes. In particular, when the information rate R = 1/2, by our constructive lower bound, the relative minimum distance δ ≈ 0.0595 (for GV bound, δ ≈ 0.110). Moreover, we have proved that the binary self-orthogonal codes asymptotically achieve the Gilbert-Varshamov bound. This work was supported by the China Scholarship Council, National Natural Science Foundation of China (Grant No.10571026), the Cultivation Fund of the Key Scientific and Technical Innovation Project of Ministry of Education of China, and the Specialized Research Fund for the Doctoral Program of Higher Education (Grant No. 20060286006)     

Improving Rogers' Upper Bound for the Density of Unit Ball Packings via Estimating the Surface Area of Voronoi Cells from Below in Euclidean \sl d -Space for All \sl d ≥ \bf 8

   Abstract. The sphere packing problem asks for the densest packing of unit balls in E ^d . This problem has its roots in geometry, number theory and information theory and it is part of Hilbert's 18th problem. One of the most attractive results on the sphere packing problem was proved by Rogers in 1958. It can be phrased as follows. Take a regular d -dimensional simplex of edge length 2 in E ^d and then draw a d -dimensional unit ball around each vertex of the simplex. Let σ _d denote the ratio of the volume of the portion of the simplex covered by balls to the volume of the simplex. Then the volume of any Voronoi cell in a packing of unit balls in E ^d is at least ω _d /σ _d , where ω _d denotes the volume of a d -dimensional unit ball. This has the immediate corollary that the density of any unit ball packing in E ^d is at most σ _d . In 1978 Kabatjanskii and Levenštein improved this bound for large d . In fact, Rogers' bound is the presently known best bound for 4≤ d≤ 42 , and above that the Kabatjanskii—Levenštein bound takes over. In this paper we improve Rogers' upper bound for the density of unit ball packings in Euclidean d -space for all d≥ 8 and improve the Kabatjanskii—Levenštein upper bound in small dimensions. Namely, we show that the volume of any Voronoi cell in a packing of unit balls in E ^d , d≥ 8 , is at least ω _d /

On the number of Galois points for a plane curve in positive characteristic,III

We consider the following problem: For a smooth plane curve C of degree d ≥ 4 in characteristic p > 0, determine the number δ(C) of inner Galois points with respect to C. This problem seems to be open in the case where d ≡ 1 mod p and C is not a Fermat curve F(p ^e  + 1) of degree p ^e  + 1. When p ≠ 2, we completely determine δ(C). If p = 2 (and C is in the open case), then we prove that δ(C) = 0, 1 or d and δ(C) = d only if d−1 is a power of 2, and give an example with δ(C) = d when d = 5. As an application, we characterize a smooth plane curve having both inner and outer Galois points. On the other hand, for Klein quartic curve with suitable coordinates in characteristic two, we prove that the set of outer Galois points coincides with the one of \mathbbF₂{\mathbb{F}_{2}} -rational points in \mathbbP²{\mathbb{P}^{2}}.     

Rank procedures for testing subhypotheses in linear regression

Summary In the linear regression modelX _i=α+βc_i+Z_i, we consider the problem of testing the subhypothesis that some (but not all) components of β are equal to 0. A class of asymptotically distribution-free tests based on a quadratic form in aligned rank statistic is studied and the asymptotic relative efficiencies of the proposed tests with respect to the general likelihood ratio test and the test based on least-squares estimates of regression parameters are derived. Asymptotic optimality (à la Wald) is also discussed. Work done under the National Science Foundation Grant MCS 8301409 and NATO Grant 1465.     

Nonconvex quadratically constrained quadratic programming: best D.C. decompositions and their SDP representations

We propose in this paper a general D.C. decomposition scheme for constructing SDP relaxation formulations for a class of nonconvex quadratic programs with a nonconvex quadratic objective function and convex quadratic constraints. More specifically, we use rank-one matrices and constraint matrices to decompose the indefinite quadratic objective into a D.C. form and underestimate the concave terms in the D.C. decomposition formulation in order to get a convex relaxation of the original problem. We show that the best D.C. decomposition can be identified by solving an SDP problem. By suitably choosing the rank-one matrices and the linear underestimation, we are able to construct convex relaxations that dominate Shor’s SDP relaxation and the strengthened SDP relaxation. We then propose an extension of the D.C. decomposition to generate an SDP bound that is tighter than the SDP+RLT bound when additional box constraints are present. We demonstrate via computational results that the optimal D.C. decomposition schemes can generate both tight SDP bounds and feasible solutions with good approximation ratio for nonconvex quadratically constrained quadratic problems.     

On Minimum Stars and Maximum Matchings

We discuss worst-case bounds on the ratio of maximum matching and minimum median values for finite point sets. In particular, we consider ``minimum stars,' which are defined by a center chosen from the given point set, such that the total geometric distance L <sub>S</sub> to all the points in the set is minimized. If the center point is not required to be an element of the set (i.e., the center may be a Steiner point), we get a ``minimum Steiner star' of total length L _SS . As a consequence of triangle inequality, the total length L _M of a maximum matching is a lower bound for the length L _SS of a minimum Steiner star, which makes the worst-case value ρ(SS,M) of the value L _SS /L _M interesting in the context of optimal communication networks. The ratio also appears as the duality gap in an integer programming formulation of a location problem by Tamir and Mitchell. In this paper we show that for a finite set that consists of an even number of points in the plane and Euclidean distances, the worst-case ratio ρ(S,M) cannot exceed . This proves a conjecture of Suri, who gave an example where this bound is achieved. For the case of Euclidean distances in two and three dimensions, we also prove upper and lower bounds for the worst-case value ρ(S,SS) of the ratio L _S /L _SS , and for the worst-case value ρ(S,M) of the ratio L _S /L _M . We give tight upper bounds for the case where distances are measured according to the Manhattan metric: we show that in three-dimensional space, ρ(SS,M) is bounded by 3/2, while in two-dimensional space L _SS =L _M , extending some independent observations by Tamir and Mitchell. Finally, we show that ρ(S,SS) is 3/2 in the two-dimensional case, and 5/3 in the three-dimensional case. Received January 1, 1999, and in revised form July 15, 1999.     

The Vehicle Routing Problem with Demand Range

We propose and formulate the vehicle routing problem with demand range (VRPDR), a new variation on the traditional vehicle routing problem. In the VRPDR, the delivery quantity for each customer i is allowed to vary from its original size d _i by an amount α d _i where 0 ≤ α < 1. In adding this limited flexibility to the problem, there is potential to generate significant savings in the total distance traveled. We address issues such as bounding the impact of a given α on total distance and provide empirical results to illustrate “typical” behavior.     

A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees

Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, the problem of computing a low-weight spanning tree such that the degree of each vertex is at most its specified bound is considered. In particular, modifying a given spanning treeTusingadoptionsto meet the degree constraints is considered. A novel network-flow-based algorithm for finding a good sequence of adoptions is introduced. The method yields a better performance guarantee than any previous algorithm. If the degree constraintd(v) for eachvis at least 2, the algorithm is guaranteed to find a tree whose weight is at most the weight of the given tree times 2 − min{(d(v) − 2)/(deg_T(v) − 2) : deg_T(v) > 2}, where deg_T(v) is the initial degree ofv. Equally importantly, it takes this approach to the limit in the following sense: if any performance guarantee that is solely a function of the topology and edge weights of a given tree holds foranyalgorithm at all, then it also holds for the given algorithm. Examples are provided in which no lighter tree meeting the degree constraint exists. Linear-time algorithms are provided with the same worst-case performance guarantee. ChoosingTto be a minimum spanning tree yields approximation algorithms with factors less than 2 for the general problem on geometric graphs with distances induced by variousL_pnorms. Finally, examples of Euclidean graphs are provided in which the ratio of the lengths of an optimal Traveling Salesman path and a minimum spanning tree can be arbitrarily close to 2.