排序方式: 共有3条查询结果,搜索用时 15 毫秒
1
1.
Mohammad T. Hajiaghayi Guy Kortsarz Vahab S. Mirrokni Zeev Nutov 《Mathematical Programming》2007,110(1):195-208
Given a graph with costs on the edges, the power of a node is the maximum cost of an edge leaving it, and the power of the
graph is the sum of the powers of the nodes of this graph. Motivated by applications in wireless multi-hop networks, we consider
four fundamental problems under the power minimization criteria: the Min-Power b-Edge-Cover problem (MPb-EC) where the goal is to find a min-power subgraph so that the degree of every node v is at least some given integer b(v), the Min-Power k-node Connected Spanning Subgraph problem (MPk-CSS), Min-Power k-edge Connected Spanning Subgraph problem (MPk-CSS), and finally the Min-Power k-Edge-Disjoint Paths problem in directed graphs (MPk-EDP). We give an O(log4
n)-approximation algorithm for MPb-EC. This gives an O(log4
n)-approximation algorithm for MPk-CSS for most values of k, improving the best previously known O(k)-approximation guarantee. In contrast, we obtain an approximation algorithm for ECSS, and for its variant in directed graphs (i.e., MPk-EDP), we establish the following inapproximability threshold: MPk-EDP cannot be approximated within O(2log1-ε
n) for any fixed ε > 0, unless NP-hard problems can be solved in quasi-polynomial time.
This paper was done when V. S. Mirrokni was at Computer Science and Artificial Intelligence Laboratory, MIT. 相似文献
2.
Grimmer Benjamin Lu Haihao Worah Pratik Mirrokni Vahab 《Mathematical Programming》2023,201(1-2):373-407
Mathematical Programming - Minimax optimization has become a central tool in machine learning with applications in robust optimization, reinforcement learning, GANs, etc. These applications are... 相似文献
3.
Mitra Ghassemzadeh Masomeh Tabatabaee Zohreh Mirrokni Bernhard Neumüller 《无机化学与普通化学杂志》2005,631(5):832-834
The reaction of 4‐Amino‐6‐methyl‐1, 2, 4‐triazine‐3(2H)‐thione‐5‐one (AMTTO, 1 ) with silver nitrate in methanol led to the dimeric complex {[(AMTTO)2Ag]NO3}2 ( 2 ). 2 was characterized by elemental analyses and IR spectroscopy as well as by X‐ray structure analysis. Crystal data for 2 at ?80 °C: crystal system orthorhombic, space group P212121 with a = 1043.6(1), b = 1329.6(1), c = 2358.4(1) pm, Z = 8 and R1 = 0.037. The cation possesses a highly distorted linear coordination sphere in the solid state. 相似文献
1