检索结果-内蒙古大学图书馆

linear programming-Based Converses for Finite Blocklength Lossy Joint Source-Channel Coding

IEEE TRANSACTIONS ON INFORMATION THEORY 2017年第11期63卷 7066-7094页

作者： Jose, Sharu Theresa Kulkarni, Ankur A. Indian Inst Technol Syst & Control Engn Grp Bombay 400076 Maharashtra India

A linear programming (LP)-based framework is presented for obtaining converses for finite blocklength lossy joint source-channel coding problems. The framework applies for any loss criterion, generalizes certain previously known converses, and also extends to multi-terminal settings. The finite blocklength problem is posed equivalently as a nonconvex optimization problem and using a lift-and-project-like method, a close but tractable LP relaxation of this problem is derived. Lower bounds on the original problem are obtained by the construction of feasible points for the dual of the LP relaxation. A particular application of this approach leads to new converses, which recover and improve on the converses of Kostina and Verdi' for finite blocklength lossy joint source-channel coding and lossy source coding. For finite blocklength channel coding, the LP relaxation recovers the converse of Polyanskiy, Poor and Verdi' and leads to a new improvement on the converse of Wolfowitz, showing thereby that our LP relaxation is asymptotically tight with increasing blocklengths for channel coding, lossless source coding, and joint source-channel coding with the excess distortion probability as the loss criterion. Using a duality-based argument, a new converse is derived for finite blocklength joint source channel coding for a class of source-channel pairs. Employing this converse, the LP relaxation is also shown to be tight for all blocklengths fir the minimization of the expected average symbolwise Hamming distortion of a q-ary uniform source over a q-ary symmetric memoryless channel for any q is an element of N. The optimization formulation and the lift-and-project method are extended to networked settings and demonstrated by obtaining an improvement on a converse of Zhou et al. for the successive refinement problem for successively refinable source-distortion measure triplets.

关键词： Converses lossy joint source-channel coding finite blocklength regime linear programming relaxation lift-and-project strong duality

来源：评论

学校读者我要写书评

暂无评论

k-median: exact recovery in the extended stochastic ball model

引用

MATHEMATICAL programming 2023年第1期200卷 357-423页

作者： Del Pia, Alberto Ma, Mingchen Univ Wisconsin Dept Ind & Syst Engn Wisconsin Inst Discovery Madison WI USA Univ Wisconsin Dept Comp Sci 1210 W Dayton St Madison WI 53706 USA

We study exact recovery conditions for the linear programming relaxation of the k-median problem in the stochastic ball model (SBM). In Awasthi et al. (Relax, no need to round: integrality of clustering formulations. arXiv:1408.4045, 2015;in: Proceedings of the 2015 conference on innovations in theoretical computer science, pp 191-200, 2015), the authors give a tight result for the k-median LP in the SBM, saying that exact recovery can be achieved as long as the balls are pairwise disjoint. We give a counterexample to their result, thereby showing that the k-median LP is not tight in low dimension. Instead, we give a near optimal result showing that the k-median LP in the SBM is tight in high dimension. We also show that, if the probability measure satisfies some concentration assumptions, then the k-median LP in the SBM is tight in every dimension. Furthermore, we propose a new model of data called extended stochastic ball model (ESBM), which significantly generalizes the well-known SBM. We then show that exact recovery can still be achieved in the ESBM.

关键词： k-median Stochastic ball model linear programming relaxation Recovery guarantee

来源：评论

学校读者我要写书评

暂无评论

LP relaxation of the Potts Labeling Problem Is as Hard as Any linear Program

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2017年第7期39卷 1469-1475页

作者： Prusa, Daniel Werner, Tomas Czech Tech Univ Fac Elect Engn Dept Cybernet Karlovo Namesti 13 Prague 12135 Czech Republic

In our recent work, we showed that solving the LP relaxation of the pairwise min-sum labeling problem (also known as MAP inference in graphical models or discrete energy minimization) is not much easier than solving any linear program. Precisely, the general linear program reduces in linear time (assuming the Turing model of computation) to the LP relaxation of the min-sum labeling problem. The reduction is possible, though in quadratic time, even to the min-sum labeling problem with planar structure. Here we prove similar results for the pairwise min-sum labeling problem with attractive Potts interactions (also known as the uniform metric labeling problem).

关键词： Markov random field graphical model MAP inference discrete energy minimization valued constraint satisfaction linear programming relaxation uniform metric labeling problem Potts model

来源：评论

学校读者我要写书评

暂无评论

A note on the max-min 0-1 knapsack problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 1999年第1期3卷 89-94页

作者： Iida, H Otaru Univ Commerce Dept Informat & Management Sci Otaru Hokkaido 0478501 Japan

In this paper we propose new lower and upper bounds for the max-min 0-1 knapsack problem, employing a mixture of two relaxations. In addition, in order to expose whether the bounds are practical or not, we implement a... 详细信息

关键词： knapsack problem surrogate relaxation linear programming relaxation branch-and-bound

来源：评论

学校读者我要写书评

暂无评论

Statistical mechanics analysis of the continuous number partitioning problem

引用

PHYSICA A 1999年第1期269卷 54-60页

作者： Ferreira, FF Fontanari, JF Univ Sao Paulo Inst Fis Sao Carlos BR-13560970 Sao Carlos SP Brazil

The number partitioning problem consists of partitioning a sequence of positive numbers {a(1),a(2),...,a(N)} into two disjoint sets, A and B, such that the absolute value of the difference of the sums of ai over the two sets is minimized. We use statistical mechanics tools to study analytically the linear programming relaxation of this NP-complete integer programming. In particular, we calculate the probability distribution of the difference between the cardinalities of A and B and shaw that this difference is not self-averaging. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： number partitioning linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for the minimum-cost k-vertex connected subgraph

引用

SIAM JOURNAL ON COMPUTING 2003年第4期32卷 1050-1055页

作者： Cheriyan, J Vempala, S Vetta, A Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada MIT Dept Math Cambridge MA 02139 USA McGill Univ Dept Comp Sci Montreal PQ H3A 2A7 Canada

We present an approximation algorithm for the problem of finding a minimum-cost k-vertex connected spanning subgraph, assuming that the number of vertices is at least 6k(2). The approximation guarantee is six times the kth harmonic number (which is O(log k)), and this is also an upper bound on the integrality ratio for a standard linear programming relaxation.

关键词： approximation algorithm l-critically k-connected graph linear programming relaxation network design k-outconnected graph vertex connectivity

来源：评论

学校读者我要写书评

暂无评论

A tight approximation algorithm for the cluster vertex deletion problem

引用

MATHEMATICAL programming 2023年第2期197卷 1069-1091页

作者： Aprile, Manuel Drescher, Matthew Fiorini, Samuel Huynh, Tony Univ Padua Dipartimento Matemat Padua Italy Univ Libre Bruxelles Dept Math Brussels Belgium Monash Univ Sch Math Melbourne Vic Australia

We give the first 2-approximation algorithm for the cluster vertex deletion problem. This approximation factor is tight, since approximating the problem within any constant factor smaller than 2 is UGC-hard. Our algorithm combines previous approaches, based on the local ratio technique and the management of twins, with a novel construction of a "good" cost function on the vertices at distance at most 2 from any vertex of the input graph. As an additional contribution, we also study cluster vertex deletion from the polyhedral perspective, where we prove almost matching upper and lower bounds on how well linear programming relaxations can approximate the problem.

关键词： Approximation algorithm Cluster vertex deletion linear programming relaxation Sherali-Adams hierarchy

来源：评论

学校读者我要写书评

暂无评论

The multi-weighted Steiner tree problem: A reformulation by intersection

引用

COMPUTERS & OPERATIONS RESEARCH 2008年第11期35卷 3599-3611页

作者： Gouveia, Luis Telhada, Joao Univ Lisbon Fac Ciencias DEIO CIO P-1649016 Lisbon Portugal

We propose a new formulation for the multi-weighted Steiner tree (MWST) problem. This formulation is based on the fact that a previously proposed formulation for the problem is non-symmetric in the sense that the corresponding linear programming relaxation bounds depend on the node selected as a root of the tree. The new formulation (the reformulation by intersection) is obtained by intersecting the feasible sets of the models corresponding to each possible root selection for the underlying directed problem. Theoretical results will show that the linear programming relaxation of the new formulation dominates the linear programming relaxation of each of the rooted formulations and is comparable with the linear programming bounds of the best formulation known for the problem. A Lagrangean relaxation scheme derived from the new formulation is also proposed and tested, with quite favourable results, on instances with up to 500 nodes and 5000 edges. (c) 2007 Elsevier Ltd. All rights reserved.

关键词： network design spanning trees and Steiner trees linear programming relaxation reformulation techniques Lagrangean relaxation

来源：评论

学校读者我要写书评

暂无评论

SOLVING LP relaxationS OF SOME NP-HARD PROBLEMS IS AS HARD AS SOLVING ANY linear PROGRAM

引用

SIAM JOURNAL ON OPTIMIZATION 2019年第3期29卷 1745-1771页

作者： Prusa, Daniel Werner, Tomas Czech Tech Univ Fac Elect Engn Karlovo Nam 13 Prague 12135 Czech Republic

We show that the general linear programming (LP) problem reduces in nearly linear time to the LP relaxations of many classical NP-hard combinatorial problems, assuming sparse encoding of instances. We distinguish two types of such reductions. In the first type (shown for set cover/packing, facility location, maximum satisfiability, maximum independent set, and multiway cut), the input linear program is feasible and bounded iff the optimum value of the LP relaxation attains a threshold, and then optimal solutions to the input linear program correspond to optimal solutions to the LP relaxation. In the second type (shown for exact set cover, three-dimensional matching, and constraint satisfaction), feasible solutions to the input linear program correspond to feasible solutions to the LP relaxations. Thus, the reduction preserves objective values of all (not only optimal) solutions. In polyhedral terms, every polytope in standard form is a scaled coordinate projection of the optimal or feasible set of the LP relaxation. Besides nearly linear-time reductions, we show that the considered LP relaxations are P-complete under log-space reductions, and therefore also hard to parallelize. These results pose a limitation on designing algorithms to compute exact or even approximate solutions to the LP relaxations, as any lower bound on the complexity of solving the general LP problem is inherited by the LP relaxations.

关键词： linear programming relaxation combinatorial optimization nearly linear-time reduction log-space reduction convex polytope universality LP-completeness extension complexity

来源：评论

学校读者我要写书评

暂无评论

Universality of the Local Marginal Polytope

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2015年第4期37卷 898-904页

作者： Prusa, Daniel Werner, Tomas Czech Tech Univ Dept Cybernet Prague 12135 Czech Republic

We show that solving the LP relaxation of the min-sum labeling problem (also known as MAP inference problem in graphical models, discrete energy minimization, or valued constraint satisfaction) is not easier than solving any linear program. Precisely, every polytope is linear-time representable by a local marginal polytope and every LP can be reduced in linear time to a linear optimization (allowing infinite costs) over a local marginal polytope. The reduction can be done (though with a higher time complexity) even if the local marginal polytope is restricted to have a planar structure.

关键词： Graphical model Markov random field discrete energy minimization valued constraint satisfaction linear programming relaxation local marginal polytope

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：