Polynomial-time interior-point algorithm based on a local self-concordant finite barrier function

The choice of self-concordant functions is the key to efficient algorithms for linear and quadratic convex optimizations, which provide a method with polynomial-time iterations to solve linear and quadratic convex optimization problems. The parameters of a self-concordant barrier function can be used to compute the complexity bound of the proposed algorithm. In this paper, it is proved that the finite barrier function is a local self-concordant barrier function. By deriving the local values of parameters of this barrier function, the desired complexity bound of an interior-point algorithm based on this local self-concordant function for linear optimization problem is obtained. The bound matches the best known bound for small-update methods.

Polynomial-time algorithm for the legal firing sequences problem of a type of synchronous composition Petri nets

As far as we know, the testing problem of legal firing sequence is NP-complete for general Petri net, the related results of this problem on the polynomial-time solvability are limited only to some special net classes, such as persistent Petri nets, conflict-free Petri nets and state machine Petri nets. In this paper, the language properties of synchronous composition net are discussed. Based on these results, the testing algorithm polynomial-time complexity for legal firing sequence is proposed. Therefore, net classification of polynomial-time solvability for testing legal firing sequence is extended.

Polynomial-time Hierarchies on Some Classes of Functions (Ⅱ)

This paper continues to study these hierarchies, the probably impossible relationships within and between them, and gives some complete functions for the classes.

Polynomial-Time Hierarchies on Some Classes of Functions (Ⅰ)

Four polynomial-time hierarchies on functions are introduced, which are considered to be generalizations of Valiant’s counting function class #P, class Span-P introduced by Kobler et al., Krentel’s optimization function class Opt-P, and F2p. It is shown that our polynomial hierarchies of optimization functions are the same as that defined by Krentel. The relationships within every hierarchy and between them are studied.

THE POLYNOMIAL-TIME HIERARCHY AND ORACLE SET A∈PH/poly

Ⅰ. INTRODUCTIONA central problem in computational complexity is whether or not the polynomial-time hierarchy is proper. Balcázar, Book and Schning have studied this problem by considering relativization with respect to sparse sets and proved the following results:

On Fixed-Parameter Solvability of the Minimax Path Location Problem

The minimax path location problem is to find a path P in a graph G such that the maximum distance d_(G)(v,P)from every vertex v∈V(G)to the path P is minimized.It is a well-known NP-hard problem in network optimization.This paper studies the fixed-parameter solvability,that is,for a given graph G and an integer k,to decide whether there exists a path P in G such that max v∈V(G)d_(G)(v,P)≤k.If the answer is affirmative,then graph G is called k-path-eccentric.We show that this decision problem is NP-complete even for k=1.On the other hand,we characterize the family of 1-path-eccentric graphs,including the traceable,interval,split,permutation graphs and others.Furthermore,some polynomially solvable special graphs are discussed.

DISCUSSION ON KARMARKAR'S METHOD FOR SOLVING UNSTANDARD MODEL.

In this paper,a discussion on the new polynomial-time algorithm for linearprogramming as proposed by Karmarkar.N.is presented.The problem is solved when aninitial feasible solution is unknown.For the case where the optimum value of the objectivefunction is unknown,the reasonableness and feasibility of the sliding objective functionmethod are proved.And a method of modifying the parameters is put forward.

AN EFFICIENT BIT COMMITMENT SCHEME BASED ON FACTORING ASSUMPTION

Recently, many bit commitment schemes have been presented. This paper presents a new practical bit commitment scheme based on Schnorr's one-time knowledge proof scheme,where the use of cut-and-choose method and many random exam candidates in the protocols are replaced by a single challenge number. Therefore the proposed bit commitment scheme is more efficient and practical than the previous schemes In addition, the security of the proposed scheme under factoring assumption is proved, thus the cryptographic basis of the proposed scheme is clarified.

SAT in P Does Not Imply Chaos in the Security System

There are a large number of papers that claim that there are problems that once solved lead to an efficient solution of a wide range of problems, classified as NP. In this paper we will not only question the existence of this class of NP-co problems, but we will also explain their limitations in engineering and give a polynomial-time solution to SAT, one of these emblematic problems. The resolution will be so trivial that it will even be possible to practice it on paper.

Primal-dual Interior-point Algorithms for Second-order Cone Optimization Based on a New Parametric Kernel Function

A class of polynomial primal-dual interior-point algorithms for second-order cone optimization based on a new parametric kernel function, with parameters p and q, is presented. Its growth term is between linear and quadratic. Some new tools for the analysis of the algorithms are proposed. The complexity bounds of O（√Nlog N log N/ε） for large-update methods and O（√Nlog N/ε） for smallupdate methods match the best known complexity bounds obtained for these methods. Numerical tests demonstrate the behavior of the algorithms for different results of the parameters p and q.

Comparison of Semantics of Disjunctive Logic Programs Based on Model-Equivalent Reduction

In this paper, it is shown that stable model semantics, perfect model semantics, and partial stable model semantics of disjunctive logic programs have the same expressive power with respect to the polynomial-time model-equivalent reduction. That is, taking perfect model semantics and stable model semantic as an example, any logic program P can be transformed in polynomial time to another logic program P＇ such that perfect models （resp. stable models） of P i-i correspond to stable models （resp. perfect models） of P＇, and the correspondence can be computed also in polynomial time. However, the minimal model semantics has weaker expressiveness than other mentioned semantics, otherwise, the polynomial hierarchy would collapse to NP.

Risk Models for the Prize Collecting Steiner Tree Problems with Interval Data

Given a connected graph G=（V,E）with a nonnegative cost on each edge in E,a nonnegative prize at each vertex in V,and a target set V′V,the Prize Collecting Steiner Tree（PCST）problem is to find a tree T in G interconnecting all vertices of V′such that the total cost on edges in T minus the total prize at vertices in T is minimized.The PCST problem appears frequently in practice of operations research.While the problem is NP-hard in general,it is polynomial-time solvable when graphs G are restricted to series-parallel graphs.In this paper,we study the PCST problem with interval costs and prizes,where edge e could be included in T by paying cost xe∈[c e,c＋e]while taking risk（c＋e xe）/（c＋e c e）of malfunction at e,and vertex v could be asked for giving a prize yv∈[p v,p＋v]for its inclusion in T while taking risk（yv p v）/（p＋v p v）of refusal by v.We establish two risk models for the PCST problem with interval data.Under given budget upper bound on constructing tree T,one model aims at minimizing the maximum risk over edges and vertices in T and the other aims at minimizing the sum of risks over edges and vertices in T.We propose strongly polynomial-time algorithms solving these problems on series-parallel graphs to optimality.Our study shows that the risk models proposed have advantages over the existing robust optimization model,which often yields NP-hard problems even if the original optimization problems are polynomial-time solvable.

Approximation Algorithms for Vertex Happiness

We investigate the maximum happy vertices(MHV)problem and its complement,the minimum unhappy vertices(MUHV)problem.In order to design better approximation algorithms,we introduce the supermodular and submodular multi-labeling(SUP-ML and SUB-ML)problems and show that MHV and MUHV are special cases of SUP-ML and SUB-ML,respectively,by rewriting the objective functions as set functions.The convex relaxation on the I ovasz extension,originally presented for the submodular multi-partitioning problem,can be extended for the SUB-ML problem,thereby proving that SUB-ML(SUP-ML,respectively)can be approximated within a factorof2-2/k(2/k,respectively),where k is the number of labels.These general results imply that MHV and MUHV can also be approximated within factors of 2/k and 2-2/k,respectively,using the same approximation algorithms.For the MUHV problem,we also show that it is approximation-equivalent to the hypergraph multiway cut problem;thus,MUHV is Unique Games-hard to achieve a(2-2/k-e)-approximation,for anyε>0.For the MHV problem,the 2/k-approximation improves the previous best approximation ratio max{1/k,1/(△+1/g(△)},where△is the maximum vertex degree of the input graph and g(△)=(√△+√△+1)2△>4△2.We also show that an existing LP relaxation for MHV is the same as the concave relaxation on the Lovasz extension for SUP-ML;we then prove an upper bound of 2/k on the integrality gap of this LP relaxation,which suggests that the 2/k-approximation is the best possible based on this LP relaxation.Lastly,we prove that it is Unique Games-hard to approximate the MHV problem within a factor of S2(log2 k/k).

Linear Arboricity of Outer-1-Planar Graphs

A graph is outer-1-planar if it can be drawn in the plane so that all vertices are on the outer face and each edge is crossed at most once.Zhang et al.(Edge covering pseudo-outerplanar graphs with forests,Discrete Math 312:2788-2799,2012;MR2945171)proved that the linear arboricity of every outer-1-planar graph with maximum degree△is exactly[△/2] provided that△=3or△≥5 and claimed that there are outer-1-planar graphs with maximum degree △=4 and linear arboricity[[(O+1)/2]=3.It is shown in this paper that the linear arboricity of every outer-1-planar graph with maximum degree 4 is exactly 2 provided that it admits an outer-1-planar drawing with crossing distance at least 1 and crossing width at least 2,and moreover,none of the above constraints on the crossing distance and Crossing width can be removed..Besides,a polynomial-time algorithm for constructing a path-2-coloring(i.e.,an edge 2-coloring such that each color class induces a linear forest,a disjoint union of paths)of such an outer-1-planar drawing is given.

Approximation Algorithm for MAX DICUT with Given Sizes of Parts

Abstract Given a directed graph G and an edge weight function w : A(G) M 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.

Nonuniform Lowness and Strong Nonuniform Lowness

The concepts of the nonuniform and strong nonuniform lownesss are in-troduced. Those notions provide a uniform framework to study connectionsbetween the polynomiaLtime hierarchy and sparse sets.

GENERAL CENTRAL PATH AND THE LARGEST STEP GENERAL CENTRAL PATH FOLLOWING ALGORITHM FOR LINEAR PROGRAMMING

In this paper, we propose a general path following method, in which the starting point can be any feasible interior pair and each iteration uses a step with the largest possible reduction in duality gap. The algorithm maintains the O (nL) ineration complexity It enjoys quadratic convergence if the optimal vertex is nondegenerate.