The Experts below are selected from a list of 8262 Experts worldwide ranked by ideXlab platform
Daniel Marx - One of the best experts on this subject based on the ideXlab platform.
-
parameterized intractability of even set and shortest Vector problem
arXiv: Computational Complexity, 2019Co-Authors: Arnab Bhattacharyya, Edouard Bonnet, Laszlo Egri, Suprovat Ghoshal, C S Karthik, Bingkai Lin, Pasin Manurangsi, Daniel MarxAbstract:The $k$-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over $\mathbb F_2$, which can be stated as follows: given a generator matrix $\mathbf A$ and an integer $k$, determine whether the code generated by $\mathbf A$ has distance at most $k$, or in other words, whether there is a Nonzero Vector $\mathbf{x}$ such that $\mathbf A \mathbf{x}$ has at most $k$ Nonzero coordinates. The question of whether $k$-Even Set is fixed parameter tractable (FPT) parameterized by the distance $k$ has been repeatedly raised in literature; in fact, it is one of the few remaining open questions from the seminal book of Downey and Fellows (1999). In this work, we show that $k$-Even Set is W[1]-hard under randomized reductions. We also consider the parameterized $k$-Shortest Vector Problem (SVP), in which we are given a lattice whose basis Vectors are integral and an integer $k$, and the goal is to determine whether the norm of the shortest Vector (in the $\ell_p$ norm for some fixed $p$) is at most $k$. Similar to $k$-Even Set, understanding the complexity of this problem is also a long-standing open question in the field of Parameterized Complexity. We show that, for any $p > 1$, $k$-SVP is W[1]-hard to approximate (under randomized reductions) to some constant factor.
Haitao Yang - One of the best experts on this subject based on the ideXlab platform.
-
relationship between finite control set model predictive control and direct current control with duty ratio optimization for power converters
International Conference on Electrical Machines and Systems, 2019Co-Authors: Yongchang Zhang, Xiang Liu, Haitao YangAbstract:Among various predictive control methods, finite control set model predictive control (FCSMPC) is famous for its accurate calculating model. Direct current control (DCC) calculates less and thus shortens the processing time. In conventional FCSMPC and DCC, only one voltage Vector is applied during one control period, which presents relatively high power ripples. Introducing a zero Vector in combination with Nonzero Vector during one control period can improve the steady-state performance of both approaches. This paper investigates the advantages and limitations of each method with optimal duty cycle control, furthermore, discussing deeply the relationship between two approaches which in some cases they are totally the same. Both simulation and experimental results from a two-level voltage source PWM rectifier (VSR) are confirming the theoretical analysis.
-
Predictive Duty Cycle Control With Reversible Vector Selection for Three-Phase AC/DC Converters
IEEE Transactions on Power Electronics, 2019Co-Authors: Xiaolong Shi, Jianguo Zhu, Jianwei Zhang, Haitao YangAbstract:The conventional predictive duty cycle control (CPDCC) of three-phase full-bridge ac/dc converters selects adjacent Nonzero Vector pair based on the grid-voltage Vector location, then the duration for each Vector is calculated. Though the Vector selection method is quite simple, it has a significant disadvantage that the values of calculated durations could be frequently less than zero due to nonoptimal Vector selection, which results in high current harmonics and power notches. It could be improved with improved predictive duty cycle control (IPDCC) by reselecting the Nonzero Vector pair when negative duration exists; however, the whole Vector selection and calculation procedure are repeated. By theoretical verification that the power variation rates of reversible Vector pair are symmetrical with respect to that of zero Vector, this paper proposes the reversible predictive duty cycle control (RPDCC) simply by replacing the original Vector with its opposite Vector and the recalculation of Vector duration is eliminated compared with IPDCC. Thus, the calculation effort is almost not increased compared with CPDCC while system performance is significantly improved. The proposed control is theoretically derived and verified with the simulation and experimental results showing that RPDCC has better steady and dynamic performance than CPDCC and IPDCC methods.
-
performance improvement of two Vectors based model predictive control of pwm rectifier
IEEE Transactions on Power Electronics, 2016Co-Authors: Yongchang Zhang, Yubin Peng, Haitao YangAbstract:Finite-control-set model predictive control (FCSMPC) has been proposed as a powerful control strategy for the power control of the pulse-width modulation rectifier. However, conventional FCSMPC applies only one voltage Vector during one control period, which still presents relatively high power ripples. Introducing a zero Vector in combination with a Nonzero Vector during one control period can improve the steady-state performance of the conventional FCSMPC, but the fixed Vector combination is not an optimal solution in minimizing power errors. This paper proposes an improved two-Vectors-based MPC, which relaxes the Vector combination to two arbitrary voltage Vectors. Compared to prior improved MPC with fixed Vector combinations, the proposed method achieves better steady-state performance without affecting the dynamic response. Furthermore, the average switching frequency is reduced by up to 29.5% in average. The principles of Vector selection and optimal Vector duration are introduced in detail. The results obtained from two kinds of three-Vectors-based predictive control methods are also presented for the aim of comparison. Both simulation and experimental results confirm the theoretical study and the effectiveness of the proposed method.
Yongchang Zhang - One of the best experts on this subject based on the ideXlab platform.
-
relationship between finite control set model predictive control and direct current control with duty ratio optimization for power converters
International Conference on Electrical Machines and Systems, 2019Co-Authors: Yongchang Zhang, Xiang Liu, Haitao YangAbstract:Among various predictive control methods, finite control set model predictive control (FCSMPC) is famous for its accurate calculating model. Direct current control (DCC) calculates less and thus shortens the processing time. In conventional FCSMPC and DCC, only one voltage Vector is applied during one control period, which presents relatively high power ripples. Introducing a zero Vector in combination with Nonzero Vector during one control period can improve the steady-state performance of both approaches. This paper investigates the advantages and limitations of each method with optimal duty cycle control, furthermore, discussing deeply the relationship between two approaches which in some cases they are totally the same. Both simulation and experimental results from a two-level voltage source PWM rectifier (VSR) are confirming the theoretical analysis.
-
performance improvement of two Vectors based model predictive control of pwm rectifier
IEEE Transactions on Power Electronics, 2016Co-Authors: Yongchang Zhang, Yubin Peng, Haitao YangAbstract:Finite-control-set model predictive control (FCSMPC) has been proposed as a powerful control strategy for the power control of the pulse-width modulation rectifier. However, conventional FCSMPC applies only one voltage Vector during one control period, which still presents relatively high power ripples. Introducing a zero Vector in combination with a Nonzero Vector during one control period can improve the steady-state performance of the conventional FCSMPC, but the fixed Vector combination is not an optimal solution in minimizing power errors. This paper proposes an improved two-Vectors-based MPC, which relaxes the Vector combination to two arbitrary voltage Vectors. Compared to prior improved MPC with fixed Vector combinations, the proposed method achieves better steady-state performance without affecting the dynamic response. Furthermore, the average switching frequency is reduced by up to 29.5% in average. The principles of Vector selection and optimal Vector duration are introduced in detail. The results obtained from two kinds of three-Vectors-based predictive control methods are also presented for the aim of comparison. Both simulation and experimental results confirm the theoretical study and the effectiveness of the proposed method.
-
model predictive direct power control of a pwm rectifier with duty cycle optimization
IEEE Transactions on Power Electronics, 2013Co-Authors: Yongchang Zhang, Wei Xie, Yingchao ZhangAbstract:This paper proposes an improved model predictive direct power control (MPDPC) for a pulse width modulation (PWM) rectifier by using a duty cycle control. The conventional MPDPC achieves good steady-state performance and quick dynamic response by selecting the best voltage Vector, which minimizes the errors between the reference power and the real power. However, due to the limited number of voltage Vectors in a two-level converter, the sampling frequency has to be high to achieve satisfactory performance. This paper introduces the concept of a duty cycle control in the MPDPC by allocating a fraction of control period for a Nonzero voltage Vector and the rest time for a zero Vector. The Nonzero Vector is selected by evaluating the effects of each Nonzero Vector and its duration is obtained based on the principle of power errors minimization. Simulation and experimental results prove that, compared to the conventional MPDPC, the proposed MPDPC with duty cycle achieves further steady-state performance improvement without affecting the dynamic response at a small cost of control complexity increase.
Arnab Bhattacharyya - One of the best experts on this subject based on the ideXlab platform.
-
parameterized intractability of even set and shortest Vector problem
arXiv: Computational Complexity, 2019Co-Authors: Arnab Bhattacharyya, Edouard Bonnet, Laszlo Egri, Suprovat Ghoshal, C S Karthik, Bingkai Lin, Pasin Manurangsi, Daniel MarxAbstract:The $k$-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over $\mathbb F_2$, which can be stated as follows: given a generator matrix $\mathbf A$ and an integer $k$, determine whether the code generated by $\mathbf A$ has distance at most $k$, or in other words, whether there is a Nonzero Vector $\mathbf{x}$ such that $\mathbf A \mathbf{x}$ has at most $k$ Nonzero coordinates. The question of whether $k$-Even Set is fixed parameter tractable (FPT) parameterized by the distance $k$ has been repeatedly raised in literature; in fact, it is one of the few remaining open questions from the seminal book of Downey and Fellows (1999). In this work, we show that $k$-Even Set is W[1]-hard under randomized reductions. We also consider the parameterized $k$-Shortest Vector Problem (SVP), in which we are given a lattice whose basis Vectors are integral and an integer $k$, and the goal is to determine whether the norm of the shortest Vector (in the $\ell_p$ norm for some fixed $p$) is at most $k$. Similar to $k$-Even Set, understanding the complexity of this problem is also a long-standing open question in the field of Parameterized Complexity. We show that, for any $p > 1$, $k$-SVP is W[1]-hard to approximate (under randomized reductions) to some constant factor.
Chiheon Kim - One of the best experts on this subject based on the ideXlab platform.
-
New classes of set-sequential trees
Discrete Mathematics, 2020Co-Authors: Louis Golowich, Chiheon KimAbstract:Abstract A graph is called set-sequential if its vertices can be labeled with distinct Nonzero Vectors in F 2 n such that when each edge is labeled with the sum ( mod 2 ) of its vertices, every Nonzero Vector in F 2 n is the label for either a single vertex or a single edge. We resolve certain cases of a conjecture of Balister, Győri, and Schelp in order to show many new classes of trees to be set-sequential. We show that all caterpillars T of diameter k such that k ≤ 18 or | V ( T ) | ≥ 2 k − 1 are set-sequential, where T has only odd-degree vertices and | V ( T ) | = 2 n − 1 for some positive integer n . We also present a new method of recursively constructing set-sequential trees.
-
New Classes of Set-Sequential Trees
arXiv: Combinatorics, 2017Co-Authors: Louis Golowich, Chiheon KimAbstract:A graph is called set-sequential if its vertices can be labeled with distinct Nonzero Vectors in $\mathbb{F}_2^n$ such that when each edge is labeled with the sum$\pmod{2}$ of its vertices, every Nonzero Vector in $\mathbb{F}_2^n$ is the label for either a single vertex or a single edge. We resolve certain cases of a conjecture of Balister, Gyori, and Schelp in order to show many new classes of trees to be set-sequential. We show that all caterpillars $T$ of diameter $k$ such that $k \leq 18$ or $|V(T)| \geq 2^{k-1}$ are set-sequential, where $T$ has only odd-degree vertices and $|T| = 2^{n-1}$ for some positive integer $n$. We also present a new method of recursively constructing set-sequential trees.
