An exact algorithm for MAX-CUT in sparse graphs

We study exact algorithms for the MAX-CUT problem. Introducing a new technique, we present an algorithmic scheme that computes a maximum cut in graphs with bounded maximum degree. Our algorithm runs in time O^*(2^(1-(2/Δ))n). We also describe a MAX-CUT algorithm for general graphs. Its time complexity is O^*(2^mn/(m+n)). Both algorithms use polynomial space.     

A New Efficient Heuristic for the Minimum Set Covering Problem

We solve approximately the minimum set covering problem by developing a new heuristic, which is essentially based on the flow algorithm originally developed by Ford and Fulkerson. We perform a comparative study of the performances (concerning solution qualities and execution times) of the flow algorithm as well as of the natural greedy heuristic for set covering originally studied by Johnson and Lovász.     

Charged current couplings in the six-quark model

New values for the V_cd and V_cs couplings are determined from opposite sign dimuon data. These results together with the V_ud and V_us couplings give restrictive bounds for other elements of the Kobayashi-Maskawa matrix.     

Weighted completion time minimization on a single-machine with a fixed non-availability interval: Differential approximability

This paper is the first successful attempt on differential approximability study for a scheduling problem. Such a study considers the weighted completion time minimization on a single machine with a fixed non-availability interval. The analysis shows that the Weighted Shortest Processing Time (WSPT) rule cannot yield a differential approximation for the problem under consideration in the general case. Nevertheless, a slight modification of this rule provides an approximation with a differential ratio of $\frac{3?\sqrt{5}}{2}\approx 0.38$.     

Electromagnetic background in the search for neutral weak currents via e+e− → μ+μ−

We estimate the radiative corrections to e⁺e^? → μ⁺μ^? for several experimental situations. In particular, we discuss the asymmetry about 90° of the muon differential cross section and compare this to weak neutral current asymmetry predictions. The differences between this work and precious estimates lie in the inclusion of 1) polarized beam effects, 2) an exact calculation of the two-photon channel, and 3) and improved soft-photon treatment.     

Confronting experiments with numerical analysis of the Fritzsch-type mass matrices

In this work the Fritzsch ansatz for the mass matrices is compared with experimental data. To achieve the best possible agreement between the quantities which are derived from the Fritzsch ansatz and the corresponding experimental ones, all parameters of the ansatz are varied so to find the best parameter set that gives the minimal ² value. The physical observables which are taken as inputs are the experimental flavor mixing elements, the quark masses, the CP parameter _K and the mixing parameter fromB ⁰ mixing. The numerical analysis shows that the Fritzsch ansatz can be consistent with experiments but the strange quark mass must be around 99 MeV which is somewhat lower than commonly quoted values and the top quark mass is predicted to be about 109 GeV. Also the results show that it may be possible to eliminate one of the two CP phase parameters of the ansatz.Work supported in part by Department of Energy contract DE-AC02-76ER 03130.A031. Report No. Brown-HET-843 (USA)     

Corrections to the mixing angle in the grand unified theories

The contribution of the two-loop corrections to the mixing angle and the lifetime of the proton are studied in grand unified theories. The corrections to the mixing angle are small giving numerical values that are uncomfortably smaller than the average Weinberg angle. When the mixing angle is chosen closest to the measured value, then the predicted lifetime is in the range of the experimental bounds.