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

22nd International Conference on Integer programming and Combinatorial Optimization (IPCO)

作者： 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

ISBN: (纸本)9783030738792;9783030738785

We give the first 2-approximation algorithm for the cluster vertex deletion problem. This is tight, since approximating the problem within any constant factor smaller than 2 is UGC-hard. Our algorithm combines the previous approaches, based on the local ratio technique and the management of true 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

来源：评论

学校读者我要写书评

暂无评论

Shannon Meets von Neumann: A Minimax Theorem for Channel Coding in the Presence of a Jammer

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2020年第5期66卷 2842-2859页

作者： Jose, Sharu Theresa Kulkarni, Ankur A. Indian Inst Technol Syst & Control Engn Grp Mumbai 400076 Maharashtra India Kings Coll London Dept Engn London WC2R 2LS England

We study the setting of channel coding over a family of channels whose state is controlled by an adversarial jammer by viewing it as a zero-sum game between a finite blocklength encoder-decoder team, and the jammer. The encoder-decoder team choose stochastic encoding and decoding strategies to minimize the average probability of error in transmission, while the jammer chooses a distribution on the state-space to maximize this probability. The min-max value of the game is equivalent to channel coding for a compound channel - we call this the Shannon solution of the problem. The max-min value corresponds to finding a mixed channel with the largest value of the minimum achievable probability of error. When the min-max and max-min values are equal, the problem is said to admit a saddle-point or von Neumann solution. While a Shannon solution always exists, the communicating team's problem is nonconvex for finite blocklengths, whereby a von Neumann solution may not exist. Despite this, we show that the min-max and max-min values become equal asymptotically in the large blocklength limit, for all but finitely many rates. We explicitly characterize this limiting value as a function of the rate and obtain tight finite blocklength bounds on the min-max and max-min value. As a corollary we get an explicit expression for the $\epsilon $ -capacity of a compound channel under stochastic codes - the first such result, to the best of our knowledge. Our results demonstrate a deeper relation between the compound channel and mixed channel than was previously known. They also show that the conventional information-theoretic viewpoint, articulated via the Shannon solution, coincides asymptotically with the game-theoretic one articulated via the von Neumann solution. Key to our results is the derivation of new finite blocklength upper bounds on the min-max value of the game via a novel achievability scheme, and lower bounds on the max-min value obtained via the linear programming relaxat

关键词： Channel coding compound channels and mixed channels saddle-point solution finite blocklength bounds linear programming 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

来源：评论

学校读者我要写书评

暂无评论

Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods

引用

JOURNAL OF GLOBAL OPTIMIZATION 2019年第3期75卷 631-654页

作者： Kimizuka, Masaki Kim, Sunyoung Yamashita, Makoto Tokyo Inst Technol Dept Math & Comp Sci Meguro Ku 2-12-1 Oh Okayama Tokyo 1528552 Japan Ewha W Univ Dept Math 52 Ewhayeodae Gil Seoul 03760 South Korea

The pooling problem is an important industrial problem in the class of network flow problems for allocating gas flow in pipeline transportation networks. For the pooling problem with time discretization, we propose second order cone programming (SOCP) and linear programming (LP) relaxations and prove that they obtain the same optimal value as the semidefinite programming relaxation. Moreover, a rescheduling method is proposed to efficiently refine the solution obtained by the SOCP or LP relaxation. The efficiency of the SOCP and the LP relaxation and the proposed rescheduling method is illustrated with numerical results on the test instances from the work of Nishi in 2010, some large instances and Foulds 3, 4 and 5 test problems.

关键词： Pooling problem Semidefinite relaxation Second order cone relaxation linear programming relaxation Rescheduling method Computational efficiency

来源：评论

学校读者我要写书评

暂无评论

Stronger path-based extended formulation for the Steiner tree problem

引用

NETWORKS 2020年第1期75卷 3-17页

作者： Filipecki, Bartosz Van Vyve, Mathieu Tech Univ Chemnitz Fak Math Reichenhainer Str 39 D-09126 Chemnitz Germany Catholic Univ Louvain Ctr Operat Res & Econometr Louvain La Neuve Belgium

The Steiner tree problem (STP) is a classical NP-hard combinatorial optimization problem with applications in computational biology and network wiring. The objective of this problem is to find a minimum cost subgraph of a given undirected graph G with edge costs, that spans a subset of vertices called terminals. We present currently used linear programming formulations of the problem based on two different approaches-the bidirected cut relaxation (BCR) and the hypergraphic formulations (HYP), the former offering better computational performance, and the latter better bounds on the integrality gap. As our contribution, we propose a new hierarchy of path-based extended formulations for STP. We show that this hierarchy provides better integrality gaps on graph instances used to define the worst-case lower bounds on the integrality gap for both BCR and HYP. We prove that each consecutive level of our hierarchy is at least as strong as the previous one. Additionally, we also present numerical results showing that several difficult STP instances can be solved to integer optimality by using this hierarchy. Our approach can be adapted to variants of STP or applied to hypergraphic formulations for further potential improvement on the integrality gap bounds, in exchange for additional computational effort.

关键词： extended formulation flow-based formulation integrality gap linear programming relaxation mixed-integer linear programming Steiner tree

来源：评论

学校读者我要写书评

暂无评论

All Colors Shortest Path problem on trees

引用

JOURNAL OF HEURISTICS 2018年第4期24卷 617-644页

作者： Akcay, Mehmet Berkehan Akcan, Huseyin Evrendilek, Cem Izmir Univ Econ Dept Software Engn TR-35330 Izmir Turkey Izmir Univ Econ Dept Comp Engn TR-35330 Izmir Turkey

Given an edge weighted tree T(V, E), rooted at a designated base vertex , and a color from a set of colors assigned to every vertex , All Colors Shortest Path problem on trees (ACSP-t) seeks the shortest, possibly non-simple, path starting from r in T such that at least one node from every distinct color in C is visited. We show that ACSP-t is NP-hard, and also prove that it does not have a constant factor approximation. We give an integer linear programming formulation of ACSP-t. Based on a linear programming relaxation of this formulation, an iterative rounding heuristic is proposed. The paper also explores genetic algorithm and tabu search to develop alternative heuristic solutions for ACSP-t. The performance of all the proposed heuristics are evaluated experimentally for a wide range of trees that are generated parametrically.

关键词： NP-hardness Inapproximability Integer linear programming linear programming relaxation Genetic algorithm Tabu search

来源：评论

学校读者我要写书评

暂无评论

A new methodology for the open-pit mine production scheduling problem

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2018年 81卷 169-182页

作者： Samavati, Mehran Essam, Daryl Nehring, Micah Sarker, Ruhul Univ Sydney Australian Ctr Field Robot Sydney NSW Australia Univ New South Wales Sch Engn & Informat Technol Canberra ACT Australia Univ Queensland Sch Mech & Min Engn Brisbane Qld Australia

The open pit mine production scheduling problem (OPMPSP) consists of scheduling the extraction of a mineral deposit that is broken into a number of smaller segments, or blocks, such that the net present value (NPV) of the operation is maximised. This problem has been formulated as an integer programming (IP) model, involving both knapsack and precedence constraints. However, due to the large number of blocks and precedence constraints, this model has remained impractical in real planning applications. In this paper, we propose a new method to quickly generate near optimum feasible (integer) solutions by using the fractional solutions from the linear programming (LP) relaxation of the IP model. To be applicable to real sized problems, a new heuristic that quickly computes a feasible LP solution is also proposed. Our methodology is tested on a set of both academically designed and real-world mine deposits, and shows better performance than the heuristic used to tackle the same deposits in the literature. Interestingly, the proposed methodology improves the best known solutions for the majority of the instances. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Open pit mining Precedence constrained knapsack problem Large size scheduling problems linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Task assignment in tree-like hierarchical structures

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2017年第2期34卷 631-655页

作者： Evrendilek, Cem Toroslu, Ismail Hakki Hashemikhabir, Seyedsasan Izmir Univ Econ Dept Comp Engn TR-35330 Izmir Turkey Middle East Tech Univ Dept Comp Engn TR-06531 Ankara Turkey

Many large organizations, such as corporations, are hierarchical by nature. In hierarchical organizations, each entity, except the root, is a sub-part of another entity. In this paper, we study the task assignment problem to the entities of a tree-like hierarchical organization. The inherent tree structure introduces an interesting and challenging constraint to the standard assignment problem. Given a tree rooted at a designated node, a set of tasks, and a real-valued function denoting the weight of assigning a node to a task, the Maximum Weight Tree Matching (MWTM) problem aims at finding a maximum weight matching in such a way that no tasks are left unassigned, and none of the ancestors of an already assigned node is allowed to engage in an assignment. When a task is assigned to an entity in a hierarchical organization, the whole entity including its children becomes responsible from the execution of that particular task. In other words, if an entity has been assigned to a task, neither its descendants nor its ancestors can be assigned to any task. In the paper, we formally introduce MWTM, and prove its NP-hardness. We also propose and experimentally validate an effective heuristic solution based on iterative rounding of a linear programming relaxation for MWTM.

关键词： Task assignment Integer programming linear programming relaxation Heuristics NP-hardness

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：