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

Solving MIN ONES 2-SAT as fast as VERTEX COVER

THEORETICAL COMPUTER SCIENCE 2013年 506卷 115-121页

作者： Misra, Neeldhara Narayanaswamy, N. S. Raman, Venkatesh Shankar, Bal Sri Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India Inst Math Sci Madras 600113 Tamil Nadu India Indian Inst Technol Madras 600036 Tamil Nadu India

The problem of finding a satisfying assignment that minimizes the number of variables that are set to 1 is NP-complete even for a satisfiable 2-SAT formula. We call this problem MIN ONES 2-SAT. It generalizes the well-studied problem of finding the smallest vertex cover of a graph, which can be modeled using a 2-SAT formula with no negative literals. The natural parameterized version of the problem asks for a satisfying assignment of weight at most k. In this paper, we present a polynomial-time reduction from MIN ONES 2-SAT to VERTEX COVER without increasing the parameter and ensuring that the number of vertices in the reduced instance is equal to the number of variables of the input formula. Consequently, we conclude that this problem also has a simple 2-approximation algorithm and a 2k - c logk-variable kernel subsuming (or, in the case of kernels, improving) the results known earlier. Further, the problem admits algorithms for the parameterized and optimization versions whose runtimes will always match the runtimes of the best-known algorithms for the corresponding versions of vertex cover. Finally we show that the optimum value of the LP relaxation of the MIN ONES 2-SAT and that of the corresponding VERTEX COVER are the same. This implies that the (recent) results of VERTEX COVER version parameterized above the optimum value of the LP relaxation of VERTEX COVER carry over to the MIN ONES 2-SAT version parameterized above the optimum of the LP relaxation of MIN ONES 2-SAT. (C) 2013 Elsevier B.V. All rights reserved.

关键词： MIN ONES 2-SAT VERTEX COVER linear programming relaxation Parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Optimality Bounds for a Variational relaxation of the Image Partitioning Problem

引用

JOURNAL OF MATHEMATICAL IMAGING AND VISION 2013年第3期47卷 239-257页

作者： Lellmann, Jan Lenzen, Frank Schnoerr, Christoph Univ Cambridge Ctr Math Sci Dept Appl Math & Theoret Phys Cambridge CB3 0WA England Heidelberg Univ Image & Pattern Anal Grp Heidelberg Germany Heidelberg Univ HCI Dept Math & Comp Sci Heidelberg Germany

We consider a variational convex relaxation of a class of optimal partitioning and multiclass labeling problems, which has recently proven quite successful and can be seen as a continuous analogue of linear programming (LP) relaxation methods for finite-dimensional problems. While for the latter several optimality bounds are known, to our knowledge no such bounds exist in the infinite-dimensional setting. We provide such a bound by analyzing a probabilistic rounding method, showing that it is possible to obtain an integral solution of the original partitioning problem from a solution of the relaxed problem with an a priori upper bound on the objective. The approach has a natural interpretation as an approximate, multiclass variant of the celebrated coarea formula.

关键词： Convex relaxation Multiclass labeling Approximation bound Combinatorial optimization Total variation linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

Nonasymptotic Upper Bounds for Deletion Correcting Codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2013年第8期59卷 5115-5130页

作者： Kulkarni, Ankur A. Kiyavash, Negar Univ Illinois Coordinated Sci Lab Urbana IL 61801 USA Univ Illinois Dept Ind & Enterprise Syst Engn Urbana IL 61801 USA

Explicit nonasymptotic upper bounds on the sizes of multiple-deletion correcting codes are presented. In particular, the largest single-deletion correcting code for q-ary alphabet and string length n is shown to be of size at most q(n)-q/(q-1)(n-1). An improved bound on the asymptotic rate function is obtained as a corollary. Upper bounds are also derived on sizes of codes for a constrained source that does not necessarily comprise of all strings of a particular length, and this idea is demonstrated by application to sets of run-length limited strings. The problem of finding the largest deletion correcting code is modeled as a matching problem on a hypergraph. This problem is formulated as an integer linear program. The upper bound is obtained by the construction of a feasible point for the dual of the linear programming relaxation of this integer linear program. The nonasymptotic bounds derived imply the known asymptotic bounds of Levenshtein and Tenengolts and improve on known nonasymptotic bounds. Numerical results support the conjecture that in the binary case, the Varshamov-Tenengolts codes are the largest single-deletion correcting codes.

关键词： Deletion channel hypergraphs integer linear programming linear programming relaxation multiple-deletion correcting codes nonasymptotic bounds single-deletion correcting codes Varshamov-Tenengolts codes

来源：评论

学校读者我要写书评

暂无评论

Task-Specific Image Partitioning

引用

IEEE TRANSACTIONS ON IMAGE PROCESSING 2013年第2期22卷 488-500页

作者： Kim, Sungwoong Nowozin, Sebastian Kohli, Pushmeet Yoo, Chang D. Qualcomm Res Korea Seoul 135010 South Korea Microsoft Res Cambridge Cambridge CB3 0FB England Korea Adv Inst Sci & Technol Dept Elect Engn Taejon 305701 South Korea

Image partitioning is an important preprocessing step for many of the state-of-the-art algorithms used for performing high-level computer vision tasks. Typically, partitioning is conducted without regard to the task in hand. We propose a task-specific image partitioning framework to produce a region-based image representation that will lead to a higher task performance than that reached using any task-oblivious partitioning framework and existing supervised partitioning framework, albeit few in number. The proposed method partitions the image by means of correlation clustering, maximizing a linear discriminant function defined over a superpixel graph. The parameters of the discriminant function that define task-specific similarity/dissimilarity among superpixels are estimated based on structured support vector machine (S-SVM) using task-specific training data. The S-SVM learning leads to a better generalization ability while the construction of the superpixel graph used to define the discriminant function allows a rich set of features to be incorporated to improve discriminability and robustness. We evaluate the learned task-aware partitioning algorithms on three benchmark datasets. Results show that task-aware partitioning leads to better labeling performance than the partitioning computed by the state-of-the-art general-purpose and supervised partitioning algorithms. We believe that the task-specific image partitioning paradigm is widely applicable to improving performance in high-level image understanding tasks.

关键词： Correlation clustering image partitioning linear programming relaxation structured support vector machine

来源：评论

学校读者我要写书评

暂无评论

Optimal Residential Load Scheduling in Smart Grid: A Comprehensive Approach

Optimal Residential Load Scheduling in Smart Grid: A Compreh...

引用

9th Asian Control Conference (ASCC)

作者： Chai, Bo Yang, Zaiyue Chen, Jiming Zhejiang Univ State Key Lab Ind Control Technol Hangzhou 310027 Zhejiang Peoples R China

ISBN: (纸本)9781467357692;9781467357678

In this paper, as a fundamental problem in smart grid, the residential load scheduling is studied in a comprehensive way. The main contributions lie in twofold. First, three indices, i.e., the power consumption expense, the robustness of schedule subject to uncertain electricity price and the satisfaction of customer, are taken into full consideration. We propose to optimize simultaneously the three indices via convex optimization. Second, in order to fully characterize the operation states of appliances, both binary and continuous variables are used, which results in a hybrid optimization problem. The relaxation technique is utilized to tackle the hybrid optimization problem. The performance of the proposed approach is illustrated by simulations. Both peak-to- average ratio of power load and variation of power load are reduced.

关键词： Smart grid demand response management residential load scheduling real time price price uncertainty linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

Strong and compact relaxations in the original space using a compact extended formulation

引用

EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION 2013年第1-2期1卷 71-80页

作者： Van Vyve, Mathieu Wolsey, Laurence A. Catholic Univ Louvain CORE Louvain Belgium

For certain integer programs, oneway to obtain a strong dual bound is to use an extended formulation and then solve the associated linear programming relaxation. The classical way to obtain a bound of the same value in the original variable space is through the use of Benders' algorithm. Here, we propose an alternative approach based on a decomposition of the dual optimal solution of the extended formulation linear program. An example of the approach using the multi-commodity formulation of a two-level production/ transportation problem is presented.

关键词： Production Site Extended Formulation Decomposition Algorithm Valid Inequality linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

NP-Completeness and an Approximation Algorithm for Rectangle Escape Problem With Application to PCB Routing

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2012年第9期31卷 1356-1365页

作者： Ma, Qiang Wong, Martin D. F. Univ Illinois Dept Elect & Comp Engn Urbana IL 61801 USA Synopsys Inc Mountain View CA 94043 USA

In this paper, we introduce and study the rectangle escape problem (REP), which is motivated by printed circuit board (PCB) bus escape routing. Given a rectangular region R and a set S of rectangles within R, the REP is to choose a direction for each rectangle to escape to the boundary of R, such that the resultant maximum density over R is minimized. We prove that the REP is NP-complete, and show that it can be formulated as an integer linear programming (ILP). A provably good approximation algorithm for the REP is developed by applying linear programming (LP) relaxation and a special rounding technique to the ILP. In addition, an iterative refinement procedure is proposed as a postprocessing step to further improve the results. Our approximation algorithm is also shown to work for more general versions of REP: weighted REP and simultaneous REP. Our approach is tested on a set of industrial PCB bus escape routing problems. Experimental results show that the optimal solution can be obtained within several seconds for each of the test cases.

关键词： Approximation algorithm linear programming relaxation NP-completeness printed circuit board (PCB) routing

来源：评论

学校读者我要写书评

暂无评论

The multi-resource agent bottleneck generalised assignment problem

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2012年第2期50卷 309-324页

作者： Karsu, Ozlem Azizoglu, Meral Middle E Tech Univ Dept Ind Engn TR-06531 Ankara Turkey

In this study, we consider the multi resource agent bottleneck generalised assignment problem. Our aim is to minimise the maximum load over all agents. We take our motivation from an assignment problem faced in heating, ventilating and air conditioning sector. We study the linear programming (LP) relaxation of the problem. We use the optimal LP relaxation solutions in our branch and bound algorithm while defining bounding and branching schemes. We find that our branch and bound algorithm returns optimal solutions to the problems with up to 60 jobs when the number of agents is 5, and up to 30 jobs when the number of agents is 10, in less than 20 minutes. To find approximate solutions, we define a tabu search algorithm and alpha approximation algorithm. Our computational results have revealed that both algorithms can find high quality solutions to large sized instances very quickly. To the best of our knowledge our study is the first reported attempt to solve the problem. We hope our study fills an important gap in the literature.

关键词： bottleneck generalised assignment problem multi periods branch and bound algorithm linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

Improved Moves for Truncated Convex Models

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2011年 12卷 31-67页

作者： Kumar, M. Pawan Veksler, Olga Torr, Philip H. S. Stanford Univ Dept Comp Sci Stanford CA 94305 USA Univ Western Ontario Dept Comp Sci London ON N6A 5B7 Canada Oxford Brookes Univ Dept Comp Oxford OX33 1HX England

We consider the problem of obtaining an approximate maximum a posteriori estimate of a discrete random field characterized by pairwise potentials that form a truncated convex model. For this problem, we propose two st-MINCUT based move making algorithms that we call Range Swap and Range Expansion. Our algorithms can be thought of as extensions of alpha beta-Swap and alpha-Expansion respectively that fully exploit the form of the pairwise potentials. Specifically, instead of dealing with one or two labels at each iteration, our methods explore a large search space by considering a range of labels (that is, an interval of consecutive labels). Furthermore, we show that Range Expansion provides the same multiplicative bounds as the standard linear programming (LP) relaxation in polynomial time. Compared to previous approaches based on the LP relaxation, for example interior-point algorithms or tree-reweighted message passing (TRW), our methods are faster as they use only the efficient st-MINCUT algorithm in their design. We demonstrate the usefulness of the proposed approaches on both synthetic and standard real data problems.

关键词： truncated convex models move making algorithms range moves multiplicative bounds linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

Effective formulation reductions for the quadratic assignment problem

引用

COMPUTERS & OPERATIONS RESEARCH 2010年第11期37卷 2007-2016页

作者： Zhang, Huizhen Beltran-Royo, Cesar Constantino, Miguel Rey Juan Carlos Univ Madrid Spain Univ Lisbon Fac Ciencias DEIO Ctr Invest Operac Lisbon Portugal

In this paper we study two formulation reductions for the quadratic assignment problem (QAP). In particular we apply these reductions to the well known Adams and Johnson 121 integer linear programming formulation of the QAP. We analyze two cases: In the first case, we study the effect of constraint reduction. In the second case, we study the effect of variable reduction in the case of a sparse cost matrix. Computational experiments with a set of 30 QAPLIB instances, which range from 12 to 32 locations, are presented. The proposed reductions turned out to be very effective. (C) 2010 Elsevier Ltd. All rights reserved.

关键词： Quadratic assignment problem linear integer programming linear programming relaxation Sparse matrix

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：