On linear complexity of binary lattices,II

The linear complexity is an important and frequently used measure of unpredictably and pseudorandomness of binary sequences. In Part I of this paper, we extended this notion to two dimensions: we defined and studied the linear complexity of binary and bit lattices. In this paper, first we will estimate the linear complexity of a truly random bit (M,N)-lattice. Next we will extend the notion of k-error linear complexity to bit lattices. Finally, we will present another alternative definition of linear complexity of bit lattices.     

The computational complexity of multi-level linear programs

We show that (L+1)-level linear programs are as difficult as levelL of the polynomial-time hierarchy, even if one only considers problems with unique optimal solutions.Dedicated to Robert Jeroslow (1942–1988)     

On complexity of multistage stochastic programs

In this paper we derive estimates of the sample sizes required to solve a multistage stochastic programming problem with a given accuracy by the (conditional sampling) sample average approximation method. The presented analysis is self-contained and is based on a relatively elementary, one-dimensional, Cramér's Large Deviations Theorem.     

On the complexity of recognizing directed path families

A Directed Path Family is a family of subsets of some finite ground set whose members can be realized as arc sets of simple directed paths in some directed graph. In this paper we show that recognizing whether a given family is a Directed Path family is an NP-Complete problem, even when all members in the family have at most two elements. If instead of a family of subsets, we are given a collection of words from some finite alphabet, then deciding whether there exists a directed graph G such that each word in the language is the set of arcs of some path in G, is a polynomial-time solvable problem.     

FCSR序列的线性复杂度

§ 1　 IntroductionFeedback with carry shift register(FCSR) was first introduced by Klapper andGoresky in1 994[1 ] .The main idea of FCSR is to add a memory to linearfeedback shiftreg-ister(LFSR) .The structure is depicted in Fig.1 ,Fig.1where mn- 1 ∈Z,ai,qi∈ { 0 ,1 } and qr=1 .We refer to mn- 1 as memory,(mn- 1 ,an- 1 ,...,an- r)as state,r=log(q+ 1 ) as length,and q=-1 + q1 · 2 + ...+ qr· 2 ras connection integerof FCSR.The operation of the shiftregister is defined as follows:(1 …     

On the linear complexity of binary lattices

Linear complexity is an important and frequently used measure of unpredictability and pseudorandomness of binary sequences. In this paper our goal is to extend this notion to two dimensions. We will define and study the linear complexity of binary lattices. The linear complexity of a truly random binary lattice will be estimated. Finally, we will analyze the connection between linear complexity and correlation measures, and we will utilize the inequalities obtained in this way for estimating the linear complexity of an important special binary lattice. Finally, we will study the connection between the linear complexity of binary lattices and of the associated binary sequences.     

On linear programs with linear complementarity constraints

The paper is a manifestation of the fundamental importance of the linear program with linear complementarity constraints (LPCC) in disjunctive and hierarchical programming as well as in some novel paradigms of mathematical programming. In addition to providing a unified framework for bilevel and inverse linear optimization, nonconvex piecewise linear programming, indefinite quadratic programs, quantile minimization, and ℓ ₀ minimization, the LPCC provides a gateway to a mathematical program with equilibrium constraints, which itself is an important class of constrained optimization problems that has broad applications. We describe several approaches for the global resolution of the LPCC, including a logical Benders approach that can be applied to problems that may be infeasible or unbounded.     

Volumetric path following algorithms for linear programming

We consider the construction of small step path following algorithms using volumetric, and mixed volumetric-logarithmic, barriers. We establish quadratic convergence of a volumetric centering measure using pure Newton steps, enabling us to use relatively standard proof techniques for several subsequently needed results. Using a mixed volumetric-logarithmic barrier we obtain an O(n ^1/4 m ^1/4 L) iteration algorithm for linear programs withn variables andm inequality constraints, providing an alternative derivation for results first obtained by Vaidya and Atkinson. In addition, we show that the same iteration complexity can be attained while holding the work per iteration to O(n ² m), as opposed to O(nm ²), operations, by avoiding use of the true Hessian of the volumetric barrier. Our analysis also provides a simplified proof of self-concordancy of the volumetric and mixed volumetric-logarithmic barriers, originally due to Nesterov and Nemirovskii. This paper was first presented at the 1994 Faculty Research Seminar “Optimization in Theory and Practice”, at the University of Iowa Center for Advanced Studies.     

Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals

In this paper we study a particular class of primal-dual path-following methods which try to follow a trajectory of interior feasible solutions in primal-dual space toward an optimal solution to the primal and dual problem. The methods investigated are so-called first-order methods: each iteration consists of a long step along the tangent of the trajectory, followed by explicit recentering steps to get close to the trajectory again. It is shown that the complexity of these methods, which can be measured by the number of points close to the trajectory which have to be computed in order to achieve a desired gain in accuracy, is bounded by an integral along the trajectory. The integrand is a suitably weighted measure of the second derivative of the trajectory with respect to a distinguished path parameter, so the integral may be loosely called a curvature integral.     

On the complexity of minmax regret linear programming

We consider linear programming problems with uncertain objective function coefficients. For each coefficient of the objective function, an interval of uncertainty is known, and it is assumed that any coefficient can take on any value from the corresponding interval of uncertainty, regardless of the values taken by other coefficients. It is required to find a minmax regret solution. This problem received considerable attention in the recent literature, but its computational complexity status remained unknown. We prove that the problem is strongly NP-hard. This gives the first known example of a minmax regret optimization problem that is NP-hard in the case of interval-data representation of uncertainty but is polynomially solvable in the case of discrete-scenario representation of uncertainty.     

On the nucleolus of NTU-games defined by multiple objective linear programs

In this article we derive a class of cooperative games with non-transferable utility from multiple objective linear programs. This is done in order to introduce the nucleolus, a solution concept from cooperative game theory, as a solution to multiple objective linear problems.We show that the nucleolus of such a game is a singleton, which is characterized by inclusion in the least core and the reduced game property. Furthermore the nucleolus satisfies efficiency, anonymity and strategic equivalence.We also present a polynomially bounded algorithm for computation of the nucleolus. Letn be the number of objective functions. The nucleolus is obtained by solving at most2n linear programs. Initially the ideal point is computed by solvingn linear programs. Then a sequence of at mostn linear programs is solved, and the nucleolus is obtained as the unique solution of the last program.Financial support from Nordic Academy for Advanced Study (NorFA) is gratefully acknowledged. Part of this work was done during autumn 1993 at Institute of Finance and Management Science, Norwegian School of Economics and Business Administration.     

On the adjustment problem for linear programs

We propose a generalization of the inverse problem which we will call the adjustment problem. For an optimization problem with linear objective function and its restriction defined by a given subset of feasible solutions, the adjustment problem consists in finding the least costly perturbations of the original objective function coefficients, which guarantee that an optimal solution of the perturbed problem is also feasible for the considered restriction. We describe a method of solving the adjustment problem for continuous linear programming problems when variables in the restriction are required to be binary.     

On the uniqueness of solutions to linear programs

We provide a constructive method of checking whether a linear programming problem (LPP) has a unique feasible or a unique optimal solution. Our method requires the solution of only one extra LPP such that the original problem has alternative solutions if and only if the optimal value of the new LPP is positive. If the original solution is not unique, an alternative solution is displayed. Possible applications are discussed.     

On linear programs with random costs

We consider linear programs in which the objective function (cost) coefficients are independent non-negative random variables, and give upper bounds for the random minimum cost. One application shows that for quadratic assignment problems with such costs certain branch-and-bound algorithms usually take more than exponential time.     

On the complexity of locating linear facilities in the plane

We consider the computational complexity of linear facility location problems in the plane, i.e., given n demand points, one wishes to find r lines so as to minimize a certain objective-function reflecting the need of the points to be close to the lines. It is shown that it is NP-hard to find r lines so as to minimize any isotone function of the distances between given points and their respective nearest lines. The proofs establish NP-hardness in the strong sense. The results also apply to the situation where the demand is represented by r lines and the facilities by n single points.     

On explicit solutions of interval linear programs

An interval linear program is the problem of maximizing {(c, x):a≦A x≦b} for given matrixA and vectorsa, b andc. The explicit (noniterative) solutions of interval programs given here, extend earlier results of Ben-Israel and Charnes. The contribution of Sanjo Zlobec is part of his Ph.D. dissertation in Applied Mathematics at Northwestern University (in preparation). Part of the research underlying this report was undertaken for the Office of Nava Research, Contract NONR-1228(10), Project NR 047-021, for the U.S. Army Research Office — Durham, Contract No. DA-31-124-ARO-D-322, and for the National Science Foundation, Project GP 7550 at Northwestern University. Reproduction of this paper in whole or in part i^S permitted for any purpose of the United States Government.     

Analytical properties of the central path at boundary point in linear programming

Received October 15, 1996 / Revised version received January 28, 1998 Published online October 21, 1998