본문 바로가기
HOME> 저널/프로시딩 > 저널/프로시딩 검색상세

저널/프로시딩 상세정보

권호별목차 / 소장처보기

H : 소장처정보

T : 목차정보

Mathematical programming 4건

  1. [해외논문]   On the worst case complexity of potential reduction algorithms for linear programming  

    Bertsimas, Dimitris , Luo, Xiaodong
    Mathematical programming v.77 no.2 ,pp. 321 - 333 , 1997 , 0025-5610 ,

    초록

    There are several classes of interior point algorithms that solve linear programming problems in O(√ nL ) iterations. Among them, several potential reduction algorithms combine both theoretical (O(√ nL ) iterations) and practical efficiency as they allow the flexibility of line searches in the potential function, and thus can lead to practical implementations. It is a significant open question whether interior point algorithms can lead to better complexity bounds. In the present paper we give some negative answers to this question for the class of potential reduction algorithms. We show that, even if we allow line searches in the potential function, and even for problems that have network structure, the bound O(√ nL ) is tight for several potential reduction algorithms, i.e., there is a class of examples with network structure, in which the algorithms need at least Θ(√ nL ) iterations to find an optimal solution.

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지
  2. [해외논문]   Two generalizations of Dykstra's cyclic projections algorithm  

    Hundal, Hein , Deutsch, Frank
    Mathematical programming v.77 no.2 ,pp. 335 - 355 , 1997 , 0025-5610 ,

    초록

    There are several classes of interior point algorithms that solve linear programming problems in O(√ nL ) iterations. Among them, several potential reduction algorithms combine both theoretical (O(√ nL ) iterations) and practical efficiency as they allow the flexibility of line searches in the potential function, and thus can lead to practical implementations. It is a significant open question whether interior point algorithms can lead to better complexity bounds. In the present paper we give some negative answers to this question for the class of potential reduction algorithms. We show that, even if we allow line searches in the potential function, and even for problems that have network structure, the bound O(√ nL ) is tight for several potential reduction algorithms, i.e., there is a class of examples with network structure, in which the algorithms need at least Θ(√ nL ) iterations to find an optimal solution.

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지
  3. [해외논문]   Variation of cost functions in integer programming  

    Sturmfels, Bernd , Thomas, Rekha R.
    Mathematical programming v.77 no.2 ,pp. 357 - 387 , 1997 , 0025-5610 ,

    초록

    We study the problem of minimizing c·x subject toA· x =b. x ≥ 0 andx integral, for a fixed matrix A /. Two cost functionsc andc′ are considered equivalent if they give the same optimal solutions for eachb. We construct a polytope St(A) whose normal cones are the equivalence classes. Explicit inequality presentations of these cones are given by the reduced GrObner bases associated withA. The union of the reduced GrObner bases asc varies (called the universal GrObner basis) consists precisely of the edge directions of St(A) . We present geometric algorithms for computing St(A) , the Graver basis, and the universal GrObner basis.

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지
  4. [해외논문]   Wheel inequalities for stable set polytopes  

    Cheng, Eddie , Cunningham, William H.
    Mathematical programming v.77 no.2 ,pp. 389 - 421 , 1997 , 0025-5610 ,

    초록

    We introduce new classes of valid inequalities, called wheel inequalities, for the stable set polytopeP G of a graphG. Each “wheel configuration” gives rise to two such inequalities. The simplest wheel configuration is an “odd” subdivisionW of a wheel, and for these we give necessary and sufficient conditions for the wheel inequality to be facet-inducing forP W . Generalizations arise by allowing subdivision paths to intersect, and by replacing the “hub” of the wheel by a clique. The separation problem for these inequalities can be solved in polynomial time.

    원문보기

    원문보기
    무료다운로드 유료다운로드

    회원님의 원문열람 권한에 따라 열람이 불가능 할 수 있으며 권한이 없는 경우 해당 사이트의 정책에 따라 회원가입 및 유료구매가 필요할 수 있습니다.이동하는 사이트에서의 모든 정보이용은 NDSL과 무관합니다.

    NDSL에서는 해당 원문을 복사서비스하고 있습니다. 아래의 원문복사신청 또는 장바구니담기를 통하여 원문복사서비스 이용이 가능합니다.

    이미지

    Fig. 1 이미지

논문관련 이미지