On the subset sum problem for finite fields

Let G be the additive group of a finite field. J. Li and D. Wan determined the exact number of solutions of the subset sum problem over G, by giving an explicit formula for the number of subsets of G of prescribed size whose elements sum up to a given element of G. They also determined a closed-form expression for the case where the subsets are required to contain only nonzero elements. In this paper we give an alternative proof of the two formulas. Our argument is purely combinatorial, as in the original proof by Li and Wan, but follows a different and somehow more “natural” approach. We also indicate some new connections with coding theory and combinatorial designs.     

On the subset sum problem over finite fields

The subset sum problem over finite fields is a well-known NP-complete problem. It arises naturally from decoding generalized Reed–Solomon codes. In this paper, we study the number of solutions of the subset sum problem from a mathematical point of view. In several interesting cases, we obtain explicit or asymptotic formulas for the solution number. As a consequence, we obtain some results on the decoding problem of Reed–Solomon codes.     

On a version of the problem of choosing a vector subset

The NP-completeness is proved of the problem of choosing some subset of “similar” vectors. One of the variants of the a posteriori (off-line) noise-proof detection problem of an unknown repeating vector in a numeric sequence can be reduced to this problem in the case of additive noise. An approximation polynomial algorithm with a guaranteed performance bound is suggested for this problem in the case of a fixed space dimension.     

On maximum length convolutional codes under a trellis complexity constraint

We look at convolutional codes with maximum possible code length for prescribed redundancy, conditioned on constraints on the free distance and on the bit-oriented trellis state complexity. Rate (n−1)/n codes have been studied to some extent in the literature, but more general rates have not been studied much. In this work we consider convolutional codes of rate (n−r)/n, r⩾1. Explicit construction techniques for free distance d_free=3 and 4 codes are described. For codes with r=2, an efficient exhaustive search algorithm is outlined. For the more general case with r⩾2, a heuristic approach is suggested. Several new codes were found for r=1 and in particular for r=2 and 3. Compared to previously known codes of similar free distance and complexity constraints, the new codes have either strictly higher rate, or the same rate but smaller low distance multiplicities.     

ON THE COMPUTATIONAL COMPLEXITY OF THE MAXIMUM TRADE PROBLEM

ＯＮＴＨＥＣＯＭＰＵＴＡＴＩＯＮＡＬＣＯＭＰＬＥＸＩＴＹＯＦＴＨＥＭＡＸＩＭＵＭＴＲＡＤＥＰＲＯＢＬＥＭＺ．－Ｑ．Ｌｕｏ；Ｄ．Ｌ．ＰＡＲＮＡＳ（ＣｏｍｍｕｎｉｃａｔｉｏｎｓＲｅｓｅａｒｃｈＬａｂｏｒａｔｏｃｙＤｅｐａｒｔｍｅｎｔｏｆＥｌｅｃｔｒｉｃａ...     

An exact algorithm for finding a vector subset with the longest sum

We consider the problem: Given a set of n vectors in the d-dimensional Euclidean space, find a subsetmaximizing the length of the sum vector.We propose an algorithm that finds an optimal solution to this problem in time O(n^d?1(d + logn)). In particular, if the input vectors lie in a plane then the problem is solvable in almost linear time.     

The problem of finding a subset of vectors with the maximum total weight

The NP-hardness is proved for the discrete optimization problems connected with maximizing the total weight of a subset of a finite set of vectors in Euclidean space, i.e., the Euclidean norm of the sum of the members. Two approximation algorithms are suggested, and the bounds for the relative error and time complexity are obtained. We give a polynomial approximation scheme in the case of a fixed dimension and distinguished a subclass of problems solvable in pseudopolynomial time. The results obtained are useful for solving the problem of choice of a fixed number of subsequences from a numerical sequence with a given number of quasiperiodical repetitions of the subsequence.     

On the maximum of the minimum of a sum

LetB denote the closure of a bounded open set of points inE ⁿ with Jordan content |B|>0 and letc>0 be constant. Typical of the expressions considered is $$M(N,c) = \max _{\left\{ {x_j } \right\}} \min _{x \in B} \sum\limits_{j = 1}^N {\left| {x - x_j } \right|^{ - c} } ,x_j \in E^n$$ Together with its analogs and extensions, the problem forc has a long history, associated with the names of Fekete, Leja, Pólya, Szegö, Frostman and Carleson, to mention just a few. It involves the notions of generalized capacity, transfinite diameter, and equilibrium potential. Here we consider the casec≧n and its extensions, for which the prior history seems less comprehensive. Illustrative of the results obtained are the three equations $$\mathop {\lim }\limits_{N \to \infty } \frac{{M(N,n)}}{{N\log N}} = \frac{{\omega (n)}}{{\left| B \right|}},\mathop {\lim }\limits_{N \to \infty } \frac{{M(N,c)}}{{N^{{c \mathord{\left/ {\vphantom {c n}} \right. \kern-\nulldelimiterspace} n}} }} = \frac{{L(n,c)}}{{\left| B \right|^{{c \mathord{\left/ {\vphantom {c n}} \right. \kern-\nulldelimiterspace} n}} }},\mathop {\lim }\limits_{c \to \infty } L(n,c)^{{1 \mathord{\left/ {\vphantom {1 c}} \right. \kern-\nulldelimiterspace} c}} = \mathop {\lim }\limits_{N \to \infty } \frac{{\left( {\left| B \right|/N} \right)^{{1 \mathord{\left/ {\vphantom {1 n}} \right. \kern-\nulldelimiterspace} n}} }}{{\varrho (N)}}$$ In the firstc=n and ω (n) is the volume of the unit ball. In the secondc>n and existence of the limit is asserted, 0<L(n,c)<∞. In the third, ? (N) is the smallest value such thatN spheres of radius ? (N) can coverB. The results would be unchanged if we requiredx _j ∈B instead ofx _j ∈E ⁿ in the definition ofM(N, c).     

An FPTAS for a vector subset search problem

Under study is a strongly NP-hard problem of finding a subset of a given size of a finite set of vectors in Euclidean space which minimizes the sum of squared distances from the elements of this subset to its center. The center of the subset is defined as the average vector calculated with all subset elements. It is proved that, unless P=NP, in the general case of the problem there is no fully polynomial time approximation scheme (FPTAS). Such a scheme is provided in the case when the dimension of the space is fixed.     

A BRANCH BOUND METHOD FOR SUBSET SUM PROBLEM

ＡＢＲＡＮＣＨＢＯＵＮＤＭＥＴＨＯＤＦＯＲＳＵＢＳＥＴＳＵＭＰＲＯＢＬＥＭＷＵＳＨＩＱＵＡＮ（吴士泉）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ，ｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ１０００８０，Ｃ...     

Polynomial algorithms for solving the vector sum problem

The problem is investigated of weighted sum maximization of a given finite set of vectors from the finite-dimensional vector space ? ^k . Polynomial algorithms solving it are presented and analyzed in the case when a finite polyhedral norm or the l ₂ norm is defined on ? ^k .     

On complexity of subset interconnection designs

Given a setX and subsetsX ₁,...,X _m, we consider the problem of finding a graphG with vertex setX and the minimum number of edges such that fori=1,...,m, the subgraphG _i; induced byX _i is connected. Suppose that for any pointsx ₁,...,x X, there are at mostX _i 's containing the set {x₁,...,x }. In the paper, we show that the problem is polynomial-time solvable for ( 2, 2) and is NP-hard for (3,=1), (=l,6), and (2,3).Support in part by the NSF under grant CCR-9208913 and CCR-8920505.Part work was done while this author was visiting at DIMACS and on leave from Institute of Applied Mathematics, Chinese Academy of Sciences, Beijing.     

On polynomial solvability of some problems of a vector subset choice in a Euclidean space of fixed dimension

The problems under study are connected with the choice of a vector subset from a given finite set of vectors in the Euclidean space ℝ ^k . The sum norm and averaged square of the sumnorm are considered as the target functions (to be maximized). The optimal combinatorial algorithms with time complexity O(k ² n ^2k ) are developed for these problems. Thus, the polynomial solvability of these problems is proved for k fixed.     

A note on the complexity of the transportation problem with a permutable demand vector

In this note we investigate the computational complexity of the transportation problem with a permutable demand vector, TP-PD for short. In the TP-PD, the goal is to permute the elements of the given integer demand vector b=(b₁,…,b_n) in order to minimize the overall transportation costs. Meusel and Burkard [6] recently proved that the TP-PD is strongly NP-hard. In their NP-hardness reduction, the used demand values b_j, j=1,…,n, are large integers. In this note we show that the TP-PD remains strongly NP-hard even for the case where b_j]{0,3} for j=1,…,n. As a positive result, we show that the TP-PD becomes strongly polynomial time solvable if b_j] {0,1,2} holds for j=1,…,n. This result can be extended to the case where b_j]{3,3+1,3+2} for an integer 3.     

Minimizing the sum of maximum earliness and maximum tardiness in the single-machine scheduling problem with sequence-dependent setup time

This paper considers the problem of scheduling a given number of jobs on a single machine to minimize the sum of maximum earliness and maximum tardiness when sequence-dependent setup times exist (1∣ST _sd ∣ET_max). In this paper, an optimal branch-and-bound algorithm is developed that involves the implementation of lower and upper bounding procedures as well as three dominance rules. For solving problems containing large numbers of jobs, a polynomial time-bounded heuristic algorithm is also proposed. Computational experiments demonstrate the effectiveness of the bounding and dominance rules in achieving optimal solutions in more than 97% of the instances.     

An approximation scheme for a problem of search for a vector subset

We consider the following clustering problem: Given a vector set, find a subset of cardinality k and minimum square deviation from its mean. The distance between the vectors is defined by the Euclideanmetric. We present an approximation scheme (PTAS) that allows us to solve this problem with an arbitrary relative error ? in time O(n ^2/?+1(9/?)^3/? d), where n is the number of vectors of the input set and d denotes the dimension of the space.     

On the complexity of a bundle pricing problem

We consider the problem of pricing items in order to maximize the revenue obtainable from a set of single minded customers. We relate the tractability of the problem to structural properties of customers’ valuations: the problem admits an efficient approximation algorithm, parameterized along the inhomogeneity of the valuations.